2017年数据结构复习题集答案.docx

《2017年数据结构复习题集答案.docx》由会员分享，可在线阅读，更多相关《2017年数据结构复习题集答案.docx（8页珍藏版）》请在优知文库上搜索。

1、复习一一、选择题1 .下面关于线性表的表达错误的选项是(D)。A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储不必占用一片连续的存储空间C、线性表采用链式存储便于插入和删除操作的实现D、线性表采用顺序存储便于插入和删除操作的实现2 .设哈夫曼树中的叶子结点总数为m,假设用二叉链表作为存储构造，那么该哈夫曼树中总共有(B)个空指针域。A、2m-lB、2mC、2m+lD、4m3 .设顺序循环队列Q0：MT的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，那么该循环队列中的元素个数为(CJ0A.R-FB、F-RC、(R-F+M

2、)%MD、(F-R+M)%M4 .设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,那么后序遍历该二叉树得到序列为（八）。A、BADCB、BCDACCDABD、CBDA5 .设某完全无向图中有n个顶点，那么该完全无向图中有(A)条边。A、n(n-l)2B、n(11-l)C、n2D、n2-l6 .设某数据构造的二元组形式表示为A=(D,R),D=01,02,03,04,05,06,07,08,09),R=r,r=,),那么数据构造A是(BA、线性构造B、树型构造C、物理构造D、图型构造7 .下面程序的时间复杂为(B)for(i=l,s=0；i=n；i+)t=l;for(j=l；jne

3、xt;p-data=q-data;p-next=q-next;free(q)；B、 q=p-next;q-data=p-data;p-next=q-next；free(q)；C、 q=p-next;p-next=q-next；free(q)；D、 q=p-next;p-data=q-data;free(q)；9.设有n个待排序的记录关键字，那么在堆排序中需要(A)个辅助记录单元。A、 1B、nC、nlog211Dn10.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),那么以20为基准记录的一趟快速排序完毕后的结果为（八）oA、10,15,14,18,20,36,

4、40,21B、 10,15,14,18,20,40,36,21C、 10,15,14,20,18,40,36,21D、 15,10,14,18,20,36,40,21二、填空题1 .为了能有效地应用HASH查找技术，必须解决的两个问题是(构造一个好的HASH函数)和确定解决冲突的方法。2 .下面程序段的功能实现数据X进栈，要求在括号处填上正确的语句。typedefstructints100;inttop;)sqstack;voidpush(sqstack&stack,intx)(if(stack.top=m-l)Printfroverflow)；else(stack,sstack,top=x)

5、;(stack,top+);)3 .中序遍历二叉排序树所得到的序列是(有序)序列(填有序或无序)。4 .快速排序的最坏时间复杂度为(0(n2),平均时间复杂度为(0(nlog2n)05 .设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,那么该二叉树中度数为2的结点数为(No-1)；假设采用二叉链表作为该二叉树的存储构造，那么该二叉树中共有(2No+N1)个空指针域。6 .设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,那么e和d的关系为Ie=d)。7 .中序)遍历二叉排序树中的结点可以得到一个递增的关键字序列填先序、中序或后序)。8 .设查找表中有100个元素，如果用

6、二分法查找方法查找数据元素X,那么最多需要比较(7)次就可以断定数据元素X是否在查找表中。9 .不管是顺序存储构造的栈还是链式存储构造的栈，其入栈和出栈操作的时间复杂度均为(O(I)o10 .设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开场顺序编号，那么第i个结点的双亲结点编号为(i2),右孩子结点的编号为(2i+l)o三、应用题11 设一组初始记录关键字序列为(45,80,48,40,22,78),那么分别给出第4趟简单项选择择排序和第4趟直接插入排序后的结果。参考答案：(22,40,45,48,80,78),(40,45,48,80,22,78)12 设指针变量p指向双向链表

7、中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为Ilink和rlink)。参考答案：q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;13 设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。参考答案X2,ASL=(l*l+2*2+3*4+4*2)=25/914 设一棵树T中边的集合为(A,B),(A,C),(A,D),(B,E),(C,F),(C,G

8、),要求用孩子兄弟表示法(二叉链表)表示出该树的存储构造并将该树转化成对应的二叉树。参考答案：树的链式存储构造二叉树15 待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为06,假定选用的散列函数是H(K)=Kmod7,假设发生冲突采用线性探查法处理，试：(1)计算出每一个元素的散列地址并在以以下列图中填写出散列表：、0123456(2)求出在查找每一个元素概率相等情况下的平均查找长度。H(36)=36 mod 7=1;Hi(22)=(1+1) mod 7=2;.冲突 H2(22)=(2+l) mod 7=3;参考答案IH(15)=15mod7=;冲突H(15)=(l+l

9、)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;冲突=1.65.设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。参考答案IE=(l,3),(1,2),(3,5),(5,6),(6,4)(四、算法设计题1 .设有一组初始记录关键字序列(KK2,Kn),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两局部，其中左半局部的每个关键字均小于K,右半局部的每个关键字均大于等于Ki.参考答案：voidquickpass(intr,ints,intt)inti=sj=t,x=rs;while(ij)while(ix)j=

10、j-l;if(ij)ri=rj;i=i+l;while(ij&r11x)i=i+l;if(inext)for(q=hb;q!=0;q=q-next)if(q-data=p-data)break;if(q!=O)t=(lklist*)malloc(sizeof(lklist);t-data=p-data;t-next=hc;hc=t;(二)复习(二一、选择题1 .设一维数组中有n个数组元素，那么读取第i个数组元素的平均时间复杂度为(C)oA、 0(n)B、 0(nlog2n) C、 0(1)D、0(n2)2 .设一棵二叉树的深度为k,那么该二叉树中最多有(D)个结点。A、2k-1B、2kC、2k

11、,D、2k-l3 .设某无向图中有n个顶点e条边，那么该无向图中所有顶点的入度之和为(DA、nBeC、2nD、2e4 .在二叉排序树中插入一个结点的时间复杂度为(B)。A、O(I)B、0(n)C、O(log2n)D、0(n2)5 .设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有(C)条有向边。A、nB、n-lC、mD、m-l6.设一组初始记录关键字序列为(345,253,674,924,627),那么用基数排序需要进展(A)趟的分配和回收才能使得初始关键字序列变成有序序列。A、3B、4C、5D、87 .设用链表作为栈的存储构造那么退栈操作(B)。A、必须判别栈是否为满B、必须判别

12、栈是否为空C、判别栈元素的类型D、对栈不作任何判别8 .以下四种排序中(A)的空间复杂度最大。A、快速排序B、冒泡排序C、希尔排序D、堆9 .设某二叉树中度数为0的结点数为N。，度数为1的结点数为N,度数为2的结点数为4,那么以下等式成立的是(C)。A、No=NMBNo=N1+N2CNo=N2+1DNo=2N1+110 .设有序顺序表中有n个数据元素，那么利用二分查找法查找数据元素X的最多比较次数不超过(AA、Iog211+1Blog211-lCl0g2nD、log2(n+l)二、填空题1 .设有n个无序的记录关键字，那么直接插入排序的时间复杂度为(0(一),快速排序的平均时间复杂度为(0(n

13、log2n)o2 .设指针变量p指向双向循环链表中的结点X,那么删除结点X需要执行的语句序列为(pl1ink-r1ink=p-rlink;p-rlink-l1ink=p-rlink)(设结点中的两个指针域分别为Ilink和riink).3 .根据初始关键字序列(19,22,01,38,10)建设的二叉排序树的高度为(3)。4 .深度为k的完全二叉树中最少有(2i)个结点。5 .设初始记录关键字序列为(M,K2,-SKa),那么用筛选法思想建堆必须从第(n2)个元素开场进展筛选。6 .设哈夫曼树中共有99个结点，那么该树中有(50)个叶子结点；假设采用二叉链表作为存储构造，那么该树中有(51)个空指针域。7 .设有一个顺序循环队列中有M个存储单元，那么该循环队列中最多能够存储(mT)个队列元素；当前实际存储(R-F+M)%M)个队列元素(设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置)。8 .设顺序线性表中有n个数据元素，那么第i个位置上插入一个数据元素需要移动表中(n+1-i)个数据元素；删除第i个位置上的数据元素需要移动表中(n-i)个元素。9 .设一组初始记录关键字序列为(20,18,22,16,30,19),那么以20为中轴的一趟快速排序结果为(19,18,16,20,30,22)10 .设一组初始记录关键字序列为(20,18,2