数据结构考试及答案.doc

该【数据结构考试及答案 】是由【雨林书屋】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【数据结构考试及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构考试及答案———————————————————————————————— 作者:———————————————————————————————— 日期:2数据结构试卷(二)一、选择题(24分)( )。,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。(A)2m-1(B)2m(C)2m+1(D)[0:M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D),则该完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-,则该二叉树的最小高度为()。(A)9(B)10(C)11(D),则该有向图对应的邻接表中有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-(5,2,6,3,8),以第一个记录关键字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二、填空题(24分),必须解决的两个问题是____________________和__________________________。,要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(==m-1)printf(“overflow”);}else{____________________;_________________;}(填有序或无序)。,平均时间复杂度为__________。,度数为1的结点数为N,则该二叉树01中度数为2的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。,所有顶点的度数之和为d,则e=_______。(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为___________________________。,则从顶点V1开始的深度优先遍历序列为___________;广度优先遍历序列为____________。三、应用题(36分)(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。. 设指针变量 p指向双向链表中结点 A,指针变量 q指向被插入结点 B,要求给出在结点A的后面插入结点 B的操作序列(设双向链表中结点的两个指针域分别为 llink和rlink)。. 设一组有序的记录关键字序列为 (13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字 62时的比较次数并计算出查找成功时的平均查找长度。. 设一棵树 T中边的集合为 {(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。. 设有无向图 G(如右图所示),要求给出用普里姆算法构造最小生成树所走过的边的集合。. 设有一组初始记录关键字为 (45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。4数据结构试卷(二)参考答案一、 、,++,[]=(n2),O(nlog2n)-1,2N+.(31,38,54,56,75,80,55,63)8.(1,3,4,2),(1,3,2,4)三、应用题1.(22,40,45,48,80,78),(40,45,48,80,22,78)->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;,ASL=91*1+2*2+3*4+4*2)=25/,={(1,3),(1,2),(3,5),(5,6),(6,4)}(三)一、选择题(30分)=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},则数据结构 A是( )。(A) 线性结构 (B)树型结构 (C)物理结构 (D)( )for(i=1,s=0;i<=n;i++){t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A)O(n) (B)O(n2) (C)O(n3) (D)O(n4) p指向单链表中结点 A,若删除单链表中结点 A,则需要修改指针的操作序列为( )。q=p->next;p->data=q->data;p->next=q->next;free(q);q=p->next;q->data=p->data;p->next=q->next;free(q);q=p->next;p->next=q->next;free(q);q=p->next;p->data=q->data;free(q);,则在堆排序中需要()个辅助记录单元。(A)1(B)n(C)nlog2n(D)(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为()。10,15,14,18,20,36,40,2110,15,14,18,20,40,36,2110,15,14,20,18,40,36,2l15,10,14,18,20,36,40,,则在二叉排序树的平均平均查找长度为()。(A)O(1)(B)O(log2n)(C)(D)O(n2),则其对应的邻接表中的表头结点和表结点的个数分别为()。(A)n,e(B)e,n(C)2n,e(D)n,,则该强连通图中至少有()条边。(A)n(n-1)(B)n+1(C)n(D)n(n+1),如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。(A)快速排序(B)堆排序(C)归并排序(D)()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(48分,其中最后两小题各6分)。,则该二叉树的深度为__________;若用二叉链表作为该完全二叉树的存储结构,则共有___________个空指针域。、2、3,则经过栈的作用后可以得到___________种不同的输出序列。[n][n]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的________,第i列上所有元素之和等于顶点i的________。,则该哈夫曼树中有________个度数为1的结点。,所有的顶点入度数之和为d,则e和d的关系为_________。(填先序、中序或后序)。,如果用二分法查找方法查找数据元素X,则最多需要比较________次就可以断定数据元素X是否在查找表中。,其入栈和出栈操作的时间复杂度均为____________。,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为____________,右孩子结点的编号为___________。(72,73,71,23,94,16,5),则以记录关键字72为基准的一趟快速排序结果为___________________________。={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的一种拓扑序列为____________________。,请在下划线处填上正确的语句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j; j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);},请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;elseif(t->key>k)t=t->lchild;else_____________;}7数据结构试卷(三)参考答案一、 :首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B。第9小题分析:9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为O(log2n)。二、、,,=(1),2i+111.(5,16,71,23,72,94,73)12.(1,4,3,2)+1,hashtable[j].key==(t),t=t->rchild第8小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。}8数据结构试卷(四)一、选择题(30分),则读取第i个数组元素的平均时间复杂度为()。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2),则该二叉树中最多有()个结点。(A)2k-1(B)2k(C)2k-1(D)2k-,则该无向图中所有顶点的入度之和为()。(A)n(B)e(C)2n(D)()。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2),则该图中有()条有向边。(A)n(B)n-1(C)m(D)m-(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。(A)3(B)4(C)5(D)()。(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)()的空间复杂度最大。(A)快速排序(B)冒泡排序(C)希尔排序(D),度数为1的结点数为Nl,度数为2的结点数为N,则下列等式成立的是()。2(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+,则利用二分查找法查找数据元素X的最多比较次数不超过()。(B)logn-1(C)logn(D)log(n+1)(A)log2n+1222二、填空题(42分),则直接插入排序的时间复杂度为________,快速排序的平均时间复杂度为_________。,则删除结点X需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。. 根据初始关键字序列 (19,22,01,38,10)建立的二叉排序树的高度为 ____________。. 深度为k的完全二叉树中最少有 ____________个结点。. 设初始记录关键字序列为 (K1,K2,,Kn),则用筛选法思想建堆必须从第 ______个元素开始进行筛选。. 设哈夫曼树中共有 99个结点,则该树中有 _________个叶子结点;若采用二叉链表作为存储结构,则该树中有 _____个空指针域。. 设有一个顺序循环队列中有 M 个存储单元,则该循环队列中最多能够存储________个队列元素;当前实际存储 ________________个队列元素(设头指针 F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置) 。. 设顺序线性表中有 n个数据元素,则第 i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第 i个位置上的数据元素需要移动表中 _______个元素。. 设一组初始记录关键字序列为 (20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为 ______________________________。 (20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为 ________________________。 G中有n个顶点,用邻接矩阵 A作为该图的存储结构,则顶点 i和顶点j互为邻接点的条件是 ______________________。 A,则A中第i上非0元素的个数_________第i列上非0元素的个数(填等于,大于或小于) 。 ABCD,中序遍历该二叉树的序列为 BADC,则后序遍历该二叉树的序列为 _____________。(k)=kmodp,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点,成功时返回指向关键字的指针,不成功时返回标志 0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k; lklist*s;for(i=0;i<m;i++)_____________________;for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];_______________________;}}10