数据结构考试题2教程文件.docx

《数据结构考试题2教程文件.docx》由会员分享，可在线阅读，更多相关《数据结构考试题2教程文件.docx（11页珍藏版）》请在优知文库上搜索。

1、数据结构考试题2要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题(每小题1.5分，20小题，共计30分)1 .以下数据结构中属非线性结构。C.BO(4)D.O(log2n)A.栈B.串队列D.平衡二叉树2 .以下算法的时间更杂度为。voidfunc(intn)inti=0zs=0;while(sprior-next=p-nextp-next-prior=p-prior;B.p-prior=p-prior-prior;p-prior-prior=p;C.p-next-prior=p;p-next=p-next-next;D.p-next=p-

2、prior-prior;p-prior=p-prior-prior;4 .设n个元素进栈序列是1、2、3n,其输出序列是小、p2p11,若p=3,则p2的值为oA.一定是2B.一定是1C.不可能是1D.以上都不对5 .在数据处理过程中常需要保存一些中间数据，如果要实现后保存的数据先处理，则应采用来保存这些数据。A.线性表B.栈C.队列D.单链表6 .中缀表达式a*(b+c)-d的对应的后缀表达式是oC.abc*+d-A.abed*+-B.abc+*d-D.-+*abcd7 .设栈S和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s,一个元素出栈后即进入队列q，若6个元素出队的序列

3、是b、d、c、f、e、a,则栈s的容量至少应该存多少个元素？A.2B.3C.4D.58 .设循环队列中数组的下标是ONT,其队头队尾指针分别为f和r(f指向队首元素的前一位置，r指向队尾元素)，则其元素个数为OA.r-fB.r-f-1C.(rf)%N+lD.(r-f+N)%N9 .若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组Bl.n(n+I)2中，A中第一个非零元素山存于B数组的b中，则应存放到bk中的非零元素知(lm均大于1）,且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。（

4、15分）2 .假设二叉树b采用二叉链存储结构存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间免杂度。（15分）3 .假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10分）四、附加题（10分）说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图G采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。“数据结构”考试试题（八）参考答案要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小

5、题1.5分，共计30分）1.D2.B3.A4.C5.B6.B7.B8.D9.D10.C11.A12.A13.A14.D15.C16.D17.C18.D19.C20.C二、问答题（共3小题，每小题10分，共计30分）1 .解：依题意，设n为总的节点个数，no为叶子节点（即度为0的节点）的个数，则有：n=no+n+n2+,+nm又有：n7二度的总数，即，n-l=nl+n22+nmm两式相减得：l=n（rn2-（m-l）nm则有：n0=1+112+2n3+(m-1)nm=l+(-l)l。2 .答：（1）本题构造的二叉排序树如图10.20所示。2 2）D的有序序列为b的中序遍历次序，即：1、3、5、7

6、、8、9、10、12、13。（3）为了删除节点12,找到其左子树中的最大节点10（其双亲节点为8）,将该节点删除并用10代替12,删除后的树结构如图10.21所示。图10.20一棵二叉排序树图10.21删除12后的二叉排序树3 .答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k11k2%是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有kik2i,kik2i+（inext,*q=B-next;while(p!=NU1.1.&q!=NU1.1.)找两个单链表中第一个值相同的节点if(p-datadata)p=p

7、-next;elseif(p-dataq-data)q=q-next;break;while(!=NU1.1.&q!=NU1.1.&p-data=q-data)(当两者值相等时同步后移p=p-next;q=q-next;)if(q=NU1.1.)当B中节点比较完毕返回1return1;else否则返回Oreturn0;)本算法的时间复杂度为O(m+n),空间复杂度为0(1)。其中m、n分别为A、B单链表的长度。2. (15分)解：由于二叉树中最长路径一定是从根节点到某个叶子节点的路径，可以求出所有叶子节点到根节点的逆路径，通过比较长度得出最长路径，可以采用多种解法。算法中用形参maxpath数

8、组存放最长路径，maxpathlen存放最长路径长度。解法1：对应的算法如下：voidMaxPath(BTNode*b,ElemTypemaxpath,intSmaxpathlen)InaXPathlen的初值为Ostructsnode(BTNode*node;存放当前节点指针intparent;/存放双亲节点在队列中的位置QuMaxSize;定义非循环队列ElemTypepathMaxSize;/存放一条路径intpathlen;/存放一条路径长度intfront,rear,pzi;/定义队头和队尾指针front=rear=-l;置队列为空队列rear+;Qurear.node=b;根节点指

9、针进进队Qurear.parent=-l;根节点没有双亲节点while(frontlchild=NU1.1.&b-rchiId=NU1.1.)*b为叶子节点p=front;pathlen=O;while(Qup.parent!=-l)(pathpathlen=Qup.node-data;pathlen+;P=Qup.parent;)pathpathlen=Qup.node-data;pathlen+;if(pathlenmaxpathlen)通过比较求最长路径for(i=0;ilchild!=NU1.1.)左孩子节点进队rear+;Qurear.node=b-lchild;Qurear.parent=front;if(b-rchild!=