ImageVerifierCode 换一换
格式:DOC , 页数:13 ,大小:96KB ,
资源ID:3158362      下载积分:8 金币
验证码下载
登录下载
邮箱/手机:
验证码: 获取验证码
温馨提示:
支付成功后,系统会自动生成账号(用户名为邮箱或者手机号,密码是验证码),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

开通VIP
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.zixin.com.cn/docdown/3158362.html】到电脑端继续下载(重复下载【60天内】不扣币)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  
声明  |  会员权益     获赠5币     写作写作

1、填表:    下载求助     留言反馈    退款申请
2、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
3、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
4、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
5、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
6、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
7、本文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。

注意事项

本文(《数据结构》3套模拟试题综合测试题带答案2.doc)为本站上传会员【人****来】主动上传,咨信网仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知咨信网(发送邮件至1219186828@qq.com、拔打电话4008-655-100或【 微信客服】、【 QQ客服】),核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载【60天内】不扣币。 服务填表

《数据结构》3套模拟试题综合测试题带答案2.doc

1、数据结构模拟试题04一、单项选择题(每题 2 分,共20分)1组成数据的基本单位是( )。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2设数据结构A=(D,R),其中D=1,2,3,4,R=r,r=,则数据结构A是( )。(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合3数组的逻辑结构不同于下列( )的逻辑结构。(A) 线性表(B) 栈 (C) 队列(D) 树4二叉树中第i(i1)层上的结点数最多有( )个。(A) 2i(B) 2i(C) 2i-1(D) 2i-15设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为( )。(A) p-next=

2、p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=p6设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是( )。(A) 6(B) 4(C) 3(D) 27将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为( )。(A) 100(B) 40(C) 55(D) 808设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为( )。(A) 3(B) 4(C) 5(D) 19根据二叉树的定义

3、可知二叉树共有( )种不同的形态。(A) 4(B) 5(C) 6(D) 710. 设有以下四种排序方法,则( )的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(每题2分,共20分)1. 设顺序循环队列Q0:m-1的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =_;。2. 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为_,在链式存储结构上实现顺序查找的平均时间复杂度为_。3. 设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该

4、二叉链表中共有_个指针域,_个空指针域。4. 设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为_。5. 设无向图G中有n个顶点和e条边,则其对应的邻接表中有_个表头结点和_个表结点。6. 设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有_关系。7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为_。8. 设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是_,编号为8的左孩子结点的编号是_。9. 下列程序段的功能实现子串t在主串s中位置的

5、算法,要求在下划线处填上正确语句。int index(char s , char t )i=j=0;while(istrlen(s) & jnext=p-next; s-next=s5. n, 2e6. m=2e7. CBA8. 4,169. i-j+1,010. n-1三、算法简答题(每题 6分,共30分)1. 链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA。2. 哈夫曼树略,WPL=783. (18,5,16,19,21,23),(5,16,21,19,18,23)4. 线性探测:链地址法:5. 深度:125364,广度:123456,最小生成树T的边集为E=(1,4),(

6、1,3),(3,5),(5,6),(5,6)四、算法设计题(每题10分,共30分)1. 设计判断单链表中结点是否关于中心对称算法。typedef struct int s100; int top; sqstack;int lklistsymmetry(lklist *head) sqstack stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p-next) stack.top+; stack.sstack.top=p-data; for(p=head;p!=0;p=p-next) if (p-data=stack.sstack.top) s

7、tack.top=stack.top-1; else return(0); return(1);2. 设计在链式存储结构上建立一棵二叉树的算法。typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt) char ch; scanf(%c,&ch); if(ch=#) bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt-data=ch;createbitree

8、(bt-lchild); createbitree(bt-rchild);3. 设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitree;void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild);数据结构模拟试题05一、单项选择题(每题 3 分,共24分)1下面关于线性

9、表的叙述错误的是( )。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( )个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3设顺序循环队列Q0:M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为( )。(A) R-F(B) F-R(C) (R-F+M)M(

10、D) (F-R+M)M4设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( )。(A) BADC(B) BCDA(C) CDAB(D) CBDA5设某完全无向图中有n个顶点,则该完全无向图中有( )条边。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16设某棵二叉树中有2000个结点,则该二叉树的最小高度为( )。(A) 9(B) 10(C) 11(D) 127设某有向图中有n个顶点,则该有向图对应的邻接表中有( )个表头结点。(A) n-1(B) n(C) n+1(D) 2n-18设一组初始记录关键字序列(5,2,6,3,8

11、),以第一个记录关键字5为基准进行一趟快速排序的结果为( )。(A) 2,3,5,8,6(B) 3,2,5,8,6(C) 3,2,5,6,8(D) 2,3,6,5,8二、填空题(每题2分,共16分)1. 为了能有效地应用HASH查找技术,必须解决的两个问题是_和_。2. 下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack.top=m-1) printf(“overflow”);else _;_;3. 中序遍历二叉排序树所

12、得到的序列是_序列(填有序或无序)。4. 快速排序的最坏时间复杂度为_,平均时间复杂度为_。5. 设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为_;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_个空指针域。6. 设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=_。7. 设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为_。8. 设某无向图G的邻接表为,则从顶点V1开始的深度优先遍历序列为_;广度优先遍历序列为_。三、算法简答题(每题 6 分,共30分)1 设一组初始

13、记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2 设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。3 设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4 设一棵树T中边的集合为(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉链表)表示出

14、该树的存储结构并将该树转化成对应的二叉树。5 设有无向图G(如下图所示),要求给出用普里姆算法构造最小生成树所走过的边的集合。四、算法设计题(每题15分,共30分)1 设有一组初始记录关键字序列(K1,K2,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。2 设有两个集合A和集合B,要求设计生成集合C=AB的算法,其中集合A、B和C用链式存储结构表示。7数据结构模拟试题05参考答案一、单项选择题(每题 3 分,共24分)1.D2.B3.C4.A5.A6.C7.B8.C二、填空题(每小题2分,共16

15、分)1. 构造一个好的HASH函数,确定解决冲突的方法2. stack.top+,stack.sstack.top=x3. 有序4. O(n2),O(nlog2n)5. N0-1,2N0+N16. d/27. (31,38,54,56,75,80,55,63)8. (1,3,4,2),(1,3,2,4)三、算法简答题(每题 6分,共30分)1. (22,40,45,48,80,78),(40,45,48,80,22,78)2. q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25

16、/94. 树的链式存储结构略,二叉树略5. E=(1,3),(1,2),(3,5),(5,6),(6,4)四、算法设计题(每题15分,共30分)1.void quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ij)while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij & rix) i=i+1; if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lkl

17、ist); t-data=p-data;t-next=hc; hc=t;数据结构模拟试题06一、单项选择题(每题 3 分,共30分)1设某数据结构的二元组形式表示为A=(D,R),D=01,02,03,04,05,06,07,08,09,R=r,r=,则数据结构A是( )。(A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构2下面程序的时间复杂为( )for(i=1,s=0; i=n; i+) t=1;for(j=1;jnext;p-data=q-data;p-next=q-next;free(q);(B) q=p-next;q-data=p-data;p-next=q-next;

18、free(q);(C) q=p-next;p-next=q-next;free(q);(D) q=p-next;p-data=q-data;free(q);4设有n个待排序的记录关键字,则在堆排序中需要( )个辅助记录单元。(A) 1(B) n(C) nlog2n(D) n25设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为( )。(A) 10,15,14,18,20,36,40,21(B) 10,15,14,18,20,40,36,21(C) 10,15,14,20,18,40,36,2l(D) 15,10,14,

19、18,20,36,40,216设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为( )。(A) O(1)(B) O(log2n)(C)(D) O(n2)7设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为( )。(A) n,e(B) e,n(C) 2n,e(D) n,2e8. 设某强连通图中有n个顶点,则该强连通图中至少有( )条边。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列( )方法可以达到此目的。(A) 快速排序(B) 堆排序(C) 归

20、并排序(D) 插入排序10.下列四种排序中( )的空间复杂度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序二、填空题(每题2分,共24分)1. 数据的物理结构主要包括_和_两种情况。2. 设一棵完全二叉树中有500个结点,则该二叉树的深度为_;若用二叉链表作为该完全二叉树的存储结构,则共有_个空指针域。3. 设输入序列为1、2、3,则经过栈的作用后可以得到_种不同的输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的_,第i列上所有元素之和等于顶点i的_。5. 设哈夫曼树中共有n个结点,则该哈夫曼树中有_个度数为1的结点。

21、6. 设有向图G中有n个顶点e条有向边,所有的顶点入度数之和为d,则e和d的关系为_。7. _遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。8. 设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_次就可以断定数据元素X是否在查找表中。9. 不论是顺序存储结构的栈还是链式存储结构的栈,其入栈和出栈操作的时间复杂度均为_。10. 设有n个结点的完全二叉树,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为_,右孩子结点的编号为_。11. 设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字7

22、2为基准的一趟快速排序结果为_。12. 设有向图G中有向边的集合E=,则该图的一种拓扑序列为_。三、算法填空题(每题 8 分,共16分)1. 下列算法实现在顺序散列表中查找值为x的关键字,请在下划线处填上正确的语句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_) %m; if (i=j) return(-1); if (_ ) return(j)

23、; else return(-1);2. 下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0)if (t-key=k)_; else if (t-keyk) t=t-lchild; else_;四、算法设计题(每题15分,共30分)1 设计在单链表中删除值相同的多余结点的算法。2 设计

24、一个求结点x在二叉树中的双亲结点算法。13数据结构模拟试题06参考答案一、单项选择题(每题 3 分,共30分)1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D二、填空题(每小题2分,共24分)1. 顺序存储结构、链式存储结构2. 9,5013. 54. 出度,入度5. 06. e=d7. 中序8. 79. O(1)10. i/2,2i+111. (5,16,71,23,72,94,73)12. (1,4,3,2)三、算法填空题(每题 8分,共16分)6. j+1,hashtablej.key=k7. return(t),t=t-rchild四、算法设计题(每题15分,共30分)1

25、. 设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&head) lklist *p,*q,*s; for(p=head;p!=0;p=p-next) for(q=p-next,s=q;q!=0; ) if (q-data=p-data) s-next=q-next; free(q);q=s-next; else s=q,q=q-next; 2. 设计一个求结点x在二叉树中的双亲结点算法。

26、typedef struct node datatype data; struct node *lchild,*rchild; bitree;bitree *q20; int r=0,f=0,flag=0;void preorder(bitree *bt, char x) if (bt!=0 & flag=0)if (bt-data=x) flag=1; return;else r=(r+1)% 20; qr=bt; preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x) int i; preorder(bt,x); for(i=f+1; ilchild-data=x | qi-rchild-data) break; if (flag=0) printf(not found xn); else if (idata); else printf(not parent);

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服