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

数据结构考试题2要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题(每小题1.5分，20小题，共计30分)1 .以下数据结构中属非线性结构。C.BO(4)D.O(log2n)A.栈B.串队列D.平衡二叉树2 .以下算法的时间更杂度为。voidfunc(intn)inti=0zs=0;while(s<=n)i+;s=s+i;A.O(n)C.O(nlog211)3 .在一个双链表中，删除P所指节点(非首、尾节点)的操作是A.p->prior->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->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个元素出队的序列是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中的非零元素知(l<in,lji)的下标i、j与k的对应关系是一。A小久.rA.+jB.2+j2C.7+0+fD.23+i210 .一棵节点个数为n的m(m3)次树中，其分支数是。A.nhB.n+hC.n-lD.h-111 .设森林F对应的二叉树为B,B中有m个节点，其根节点的右子树的节点个数为n,森林F中第一棵树的节点个数是_。A.m-nB.m-11-1C.n+1D.条件不足，无法确定12 .一棵二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBAEDF,则后序遍历序列为oA.CBEFDAB.FEDCBAC.CBEDFAD.不确定13 .在一个具有n个顶点的有向图中，构成强连通图时至少有一条边。A.nB.n+1C.n-lD.n/214 .对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个oA.由n-1条权值最小的边构成的子图B.由nT条权值之和最小的边构成的子图C.由nT条权值之和最小的边构成的连通子图D.由n个顶点构成的极小连通子图，且边的权值之和最小15 .对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra算法的时间发杂度为一。A.O(n)B.O(n÷e)C.O(n2)D.O(ne)16 .一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0,则该树共有个节点。A.2k',-1B.2k,C.2k',+1D.2k-117 .对线性表进行折半查找时，要求线性表必须oA.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链表方式存储，且节点按关键字有序排序18 .假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行一次探测。A.k-1B.kC.k+1D.k(k+1)219 .以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是OA.堆排序B.冒泡排序C.直接插入排序D.快速排序20 .以下排序方法中，不需要进行关犍字的比较。A.快速排序B.归并排序C.基数排序D.堆排序二、问答题(共3小题，每小题10分，共计30分)1 .已知一棵度为m的树中有n个度为1的节点，m个度为2的节点，小个度为m的节点，问该树中有多少个叶子节点？2 .设数据集合D=1,12,5,8,3,10,7,13,9,试完成下列各题：(1)依次取D中各数据，构造一棵二叉排序树bt；(2)如何依据此二叉树bt得到D的一个有序序列；(3)画出在二叉树bt中删除12后的树结构。3 .一个有n个整数的数组Rl.n,其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给一个反例，若是，请说明理由。三、算法设计题(共计40分)1 .设A=(a,a2,an),B=(bM,bm)是两个递增有序的线性表(其中11>m均大于1）,且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。（15分）2 .假设二叉树b采用二叉链存储结构存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间免杂度。（15分）3 .假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10分）四、附加题（10分）说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图G采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。“数据结构”考试试题（八）参考答案要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题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=n×l+n2×2+nm×m两式相减得：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、8、9、10、12、13。（3）为了删除节点12,找到其左子树中的最大节点10（其双亲节点为8）,将该节点删除并用10代替12,删除后的树结构如图10.21所示。图10.20一棵二叉排序树图10.21删除12后的二叉排序树3 .答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k11k2%是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有ki<k2i,ki<k2i+（i<n2）,这正好满足小根堆的特性，所以构成一个小根堆。4 .有一棵二叉排序树按先序遍历得到的序列为：（12,5,2,8,6,10,16,15,18,20）。回答以下问题：（1）画出该二叉排序树。（2）给出该二叉排序树的中序遍历序列。（3）求在等概率下的查找成功和不成功情况下的平均查找长度。三、算法设计题（共计40分）1.（15分）解：采用二路归并思路，用p、q分别扫描有序单链表A、B,先找到第一个两者值相等的节点，然后在两者值相等时同步后移，如果B扫描完毕返回1,否则返回0。对应的算法如下：intSubSeq(1.ink1.ist*A,1.ink1.ist*B)1.ink1.ist*p=A->next,*q=B->next;while(p!=NU1.1.&&q!=NU1.1.)找两个单链表中第一个值相同的节点if(p->data<q->data)p=p->next;elseif(p->data>q->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数组存放最长路径，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;根节点指针进进队Qurear.parent=-l;根节点没有双亲节点while(front<rear)(front+;/队列不为空b=Qufront.node;/队头出队列if(b->lchild=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(pathlen>maxpathlen)通过比较求最长路径for(i=0;i<athlen;i+)maxpathi=athi;maxpathlen=pathlen;)if(b->lchild!=NU1.1.)左孩子节点进队rear+;Qurear.node=b->lchild;Qurear.parent=front;if(b->rchild!=NU1.1.)右孩子节点进队rear+;Qurear.node=b->rchild;Qurear.parent=front;)本算法的时间复杂度为O(n),空间复杂度为O(n)。解法2：对应的算法如下：voidMaxPathl(BTNode*bzElemTypepath,intpathlen,ElemTypemaxpath,int&maxpathlen)PathIen和InaXPathlen的初值均为Ointi;if(b=NU1.1.)if(pathlen>maxpathlen)通过比较求最长路径(for(i=pathlen-l;i>=0;i)maxpathi=pathi;maxpathlen=pathlen;)else(pathpathlen=b->data;将当前节点放入路径中pathlen+;路径长度增1MaxPathl(b->lchild,path,pathlen,maxpath,maxpathlen);递归扫描左子树MaxPathl(b->rchildzpath,pathlenrmaxpath,maxpathlen);递归扫描右子树)本算法的时间复杂度为0(n),空间复杂度为0(n).解法3：对应的算法如下：voidMaxPath2(BTNode*b,ElemTypemaxpath,intSmaxpathlen)“maxpathlen的初值为OBTNode*StMaxSize;/存放一条路径/存放条路径长度/栈顶指针置初值BTNode*p;ElemTypepathMaxSize;intpathlen;inti,flag,top=-l;if(b!=NU1.1.)do(while(b!=NU1.1.)将*b的所有左节点进栈top+;Sttop=b;b=b->lchild;p=NU1.1.;/p指向栈顶节点的前一个已访问的节点flag=l;设置b的访问标记为己访问过while(top!=-l&&flag)b=Sttop;/取出当前的枝顶元素if(b->rchild=p)/右孩子不存在或右孩子已被访问，访问之if(b->lchild=NU1.1.&&b->rchild=NU1.1.)*b为叶子节点pathlen=O;for(i=top;i>=0;i)pathpathlen=Sti->data;pathlen+;)if(pathlen>maxpathlen)/通过比较求最长路径for(i=0;i<pathlen;i+)maxpathi=pathi;maxpathlen=pathlen;)top一;p=b;/p指向刚才访问的节点elseb=b->rchild;1)指向右孩子节点fIag=O;/设置未被访问的标记)while(top!=-1);printf(,n');本算法的时间更杂度为0(n),空间兔杂度为O(n).3. (10分)解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：intvisitedMAXV=0;DFSGraph(AGraph*G)inti,j=l;用j记录连通分量的序号for(i=0;i<G->n;i+)if(visitedi=0)(Printf("第Sd个连通分量节点序列：j+);DFS(G,i);/调用前面的深度优先遍历算法)采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：intvisitedMAXV=0;BFSGraph(AGraph*G)inti,j=l;用j记录连通分量的序号for(i=0;i<G->n;i+)if(visitedi=0)Printf(“第%d个连通分量节点序列：j+);BFS(G,i);/调用前面的广度优先遍历算法)四、附加题GO分)说明：附加题不计入木次期未考试总分，但计入本课程的总分。假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在回路。解：采用深度优先遍历方法，从顶点V出发，对每个访问的顶点W做标记(visitedw=1)o若顶点W(先访问)和i(后访问)均已访问过，表示从顶点W到顶点i存在一条路径。当从顶点i出发遍历，发现顶点i到顶点W有一条边时，表示存在一个回路(该回路上包含顶点W和i)。算法CyCIe(GV,has)从顶点V出发判断图G中是否存在回路，has是布尔值，初始调用时置为false,执行后若为InIe表示有回路，否则表示图G中没有回路。对应的算法如下：voidCycle(AGraph*Gzintv,bool&has)调用时has置初值falseArcNode*p;intw;visitedv=1;p=G->adjlistv.firstarc;while(p!=NU1.1.)w=p->adjvex;if(visitedi=0)Cycle(G,w,has);else明有回路has=true;p=p->nextarc;)/置已访问标记/P指向顶点V的第一个邻接点/若顶点W未访问，递归访问它又找到了已访问过的顶点说找下一个邻接点)