《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)个
14、空指针域。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,22,16,30,19),
15、那么根据这些初始关键字序列建成的初始堆为(16,18,19,20,32,22)。三、计算题1、画出广义表LS=(),(e),(a,(b,c,d)的头尾链表存储构造。参考答案：2、以以下列图所示的森林：(1)求树(a)的先根序列和后根序列；(2)求森林先序序列和中序序列；(3)将此森林转换为相应的二叉树；参考答案：(I)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG(3)转换为相应的二叉树四、算法设计题1 .设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。参考答案Ityp
16、edefchardatatype;typedefstructnodedatatypedata;structnode*next;)Iklist;voidsplit(lklist*head,Iklist*&ha,Iklist*&hb,Iklist*&hc)(Iklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head)(head=p-next;p-next=0;if(p-data=A,&p-datanext=ha;ha=p;)elseif(p-data=*O,&p-datanext=hb;hb=p;)else(p-next=hc;hc=p;)2 .设计在链式存储构造
17、上交换二叉树中所有结点左右子树的算法。参考答案：typedefstructnodeintdata;structnode*1ChildJrchild;bitrcc;voidswapbitree(bitree*bt)(bitree*p;if(bt=O)return;swapbitree(bt-lchild);swapbitree(bt-rchild);p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;)3 .在链式存储构造上建设一棵二叉排序树。参考答案：#definen10typedefstructnodeintkey;structnode*lchild,*r
18、child;)bitree;voidbstinsert(bitree*&bt,intkey)if(bt=O)(bt=(bitree*)malloc(sizeof(bitree);bt-key=key;bt-lchild=bt-rchild=O;elseif(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);voidcreatebsttree(bitree*&bt)inti;for(i=l;i=n;i+)bstinsert(bt,random(100);4、设计将所有奇数移到所有偶数之前的算法。参考答案：voidqui
19、ckpass(intrl,ints,intt)(inti=sj=t,x=rsj;while(ij)while(ij&rj%2=0)j=j-l;if(Kj)r(i=rO;i=i+l;数据构造试卷(三)一、选择题1 .数据的最小单位是(AA、数据项B、数据类型C、数据元素D、数据变量2 .设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),那么以增量d=4的一趟希尔排序完毕后前4条记录关键字为(B)。A、40,50,20,95B、15,40,60,20C、15,20,40,45D、45,40,15,203 .设一组初始记录关键字序列为(25,50,15,35,80,85,
20、20,40,36,70),其中含有5个长度为2的有序子表，那么用归并排序的方法对该记录关键字序列进展一趟归并后的结果为(A)。A、 15,25,35,50,20,40,80,85,36,70B、 15,25,35,50,80,20,85,40,70,36C、 15,25,35,50,80,85,20,36,40,70D、 15,25,35,50,80,20,36,40,70,854 .函数SUbStr(“Datastructure,5,9)的返回值为(AA、aSTRUCTUREB、DATA”C、rtASTRUCTURwD、“DATASTRUCTURE5 .设一个有序的单链表中有n个结点，现要求
21、插入一个新结点后使得单链表仍然保持有序,那么该操作的时间复杂度为(D)。A、0(log2n)B、0(1)C、0(n2)D、0(n)6 .设一棵m叉树中度数为。的结点数为N。，度数为1的结点数为M,度数为In的结点数为Nnb那么NO=1BA、Ni+N2+NmB、l+N2+2N3+3M+(In-DNlnC、N2+2N3+3N4+(m-l)NmD、2N+3N2+(m+l)Nm7 .设有序表中有100O个元素，那么用二分查找查找元素X最多需要比较(B)次。A、25B、10C、7D、18 .设连通图G中的边集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),那么从顶
22、点a出发可以得到一种深度优先遍历的顶点序列为(B)oA、abedfcacfebdCaebdfcD、aedfcb9 .设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素是n,那么输出序列中第i个输出元素是(CA、n-iB、n-l-iC、n+l-iD、不能确定10设一组初始记录关键字序列为(45,80,55,40,42,85),那么以第一个记录关键字45为基准而得到一趟快速排序的结果是(CA、40,42,45,55,80,83B、42,40,45,80,85,88C、42,40,45,55,80,85D、42,40,45,85,55,80二、填空题1 .设有一个顺序共享栈S0：nT,其
23、中第一个栈项指针topi的初值为-L第二个栈顶指针top2的初值为n,那么判断共享栈满的条件是(topl+l=top2)2 .在图的邻接表中用顺序存储构造存储表头结点的优点是(可以随机访问到任一个顶点的简单链表)。3 .设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素包括对角线上元素)存放在n(n+l)个连续的存储单元中，那么Aij与A00之间有(i(i+l)2+j-l)个数据元素。4 .栈的插入和删除只能在栈的栈顶进展,后进栈的元素必定先出栈,所以又把栈称为(FlLO)表；队列的插入和删除运算分别在队列的两端进展，先进队列的元素必定先出队列，所以又把队列称为(FlFo)表。5
24、 .设一棵完全二叉树的顺序存储构造中存储数据元素为ABCDEF,那么该二叉树的前序遍历序列为(ABDECF),中序遍历序列为(DBEAFC),后序遍历序列为(DEBFCA)。6 .设一棵完全二叉树有128个结点，那么该完全二叉树的深度为(8),有(64)个叶子结点。7 .设有向图G的存储构造用邻接矩阵A来表示，那么A中第i行中所有非零元素个数之和等于顶点i的(出度)，第i列中所有非零元素个数之和等于顶点i的(入度)。8 .设一组初始记录关键字序列(k“k2,，kJ是堆，那么对i=l,2,，n/2而言满足的条件为(ki=k2i&ki2i+l)O9 .下面程序段的功能是实现冒泡排序算法，请在下划线
25、处填上正确的语句。voidbubble(intrnj)for(i=l;i=n-l;i+fr(exchange=0,j=0;jrj+1)temp=rj+1;(rj+l=rj);rj=temp;exchange=l;if(exchange=0)return；三、应用题1 .设某棵二叉树的中序遍历序列为DBEAC,前序遍历序列为ABDEC,要求给出该二叉树的的后序遍历序列。参考答案：DEBCA2 .设无向图G(如右图所示)，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。参考答案：E=(1,5),(5,2),(5,3),(3,4),W=103 .设一组初始记录关键字序列为(15,17
26、,18,22,35,51,60),要求计算出成功查找时的平均查找长度。参考答案：ASL=(1*1+2*2+3*4)7=17/74 .设散列表的长度为度散列函数H(k)=kmod7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。参考答案】ASL1=7/6,ASL2=43四、算法设计题1 .设计判断两个二叉树是否一样的算法。参考答案Itypedefstructnodedatatypedata;structnode*Ichild,*rchild;)bitree;intjudgebitree(bitree*btl,bitr
27、ee*bt2)if(btl=O&bt2=0)return(l);elseif(btl=Obt2=0btl-data!=bt2-data)retrn(0);elsereturn(judgebitree(btl-lchild,bt2-lchild)*judgcbitrcc(btl-rchild,bt2-rchild);2 .设计两个有序单链表的合并排序算法。参考答案：voidmergelklist(lklist*ha,lklist*hb,Iklist*&hc)(Iklist*s=hc=0;while(ha!=0&hb!=O)if(ha-datadata)if(sO)hc=s=ha;elses-next=ha;s=ha;ha=ha-next;elseif(s=O)hc=s=hb;elses-next=hb;s=hb;(;hb=hb-ncxt;)if(ha=O)s-next=hb;elses-next=ha;五、1、设计计算二叉树中所有结点值之和的算法。参考答案：voidsum(bitree*bt,i11t&s)if(bt!=O)s=s+bt-data;sum(bt-lchild,s);sum(bt-rchild,s);)
