数据结构考试题18979.pdf

.要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每答题纸都要写上和*。一、单项选择题每题 1.5 分，20 小题，共计 30 分 1.以下数据构造中属非线性构造。A.栈 B.串 C.队列 D.平衡二叉树 2.以下算法的时间复杂度为。void func(int n)int i=0,s=0;while(sprior-ne*t=p-ne*t;p-ne*t-prior=p-prior;B.p-prior=p-prior-prior;p-prior-prior=p;C.p-ne*t-prior=p;p-ne*t=p-ne*t-ne*t;D.p-ne*t=p-prior-prior;p-prior=p-prior-prior;4.设 n 个元素进栈序列是 1、2、3、n，其输出序列是 p1、p2、pn，假设 p1=3，则 p2的值为。A.一定是 2 B.一定是 1C.不可能是 1D.以上都不对 5.在数据处理过程中常需要保存一些中间数据，如果要实现后保存的数据先处理，则应采用来保存这些数据。A.线性表 B.栈 C.队列 D.单链表 6.中缀表达式 a*(b+c)-d 的对应的后缀表达式是。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd 7.设栈 s 和队列 q 的初始状态都为空，元素 a、b、c、d、e 和 f 依次通过栈 s，一个元素出栈后即进入队列 q，假设 6 个元素出队的序列是 b、d、c、f、e、a，则栈 s 的容量至少应该存多少个元素？A.2 B.3 C.4 D.5 8.设循环队列中数组的下标是 0N-1，其队头队尾指针分别为 f 和 rf 指向队首元.素的前一位置，r 指向队尾元素，则其元素个数为。A.r-f B.r-f-1 C.(r-f)N+1 D.(r-f+N)N 9.假设将 n 阶上三角矩阵 A 按列优先顺序压缩存放在一维数组 B1.n(n+1)/2中，A中第一个非零元素 a1,1存于 B 数组的 b1中，则应存放到 bk中的非零元素 ai,j1in，1ji的下标 i、j 与 k 的对应关系是。A.jii2)1(B.jii2)1(C.ijj2)1(D.ijj2)1(10.一棵节点个数为 n 的 mm3次树中，其分支数是。A.nhB.n+h C.n-1 D.h-1 11.设森林 F 对应的二叉树为 B，B 中有 m 个节点，其根节点的右子树的节点个数为 n，森林 F 中第一棵树的节点个数是。A.m-n B.m-n-1 C.n+1 D.条件缺乏，无法确定 12.一棵二叉树的先序遍历序列为 ABCDEF，中序遍历序列为 CBAEDF，则后序遍历序列为。A.CBEFDA B.FEDCBAC.CBEDFA D.不确定 13.在一个具有 n 个顶点的有向图中，构成强连通图时至少有条边。A.n B.n+l C.n-1D.n/2 14.对于有 n 个顶点的带权连通图，它的最小生成树是指图中任意一个。A.由 n-1 条权值最小的边构成的子图 B.由 n-l 条权值之和最小的边构成的子图 C.由 n-l 条权值之和最小的边构成的连通子图 D.由 n 个顶点构成的极小连通子图，且边的权值之和最小 15.对于有 n 个顶点 e 条边的有向图，求单源最短路径的 Dijkstra 算法的时间复杂度为。A.O(n)B.O(n+e)C.O(n2)D.O(ne)16.一棵深度为 k 的平衡二叉树，其每个非叶子节点的平衡因子均为 0，则该树共有个节点。A.2k-1-1B.2k-1C.2k-1+1D.2k-1 17.对线性表进展折半查找时，要求线性表必须。A.以顺序方式存储 B.以方式存储 C.以顺序方式存储，且节点按关键字有序排序 D.以链表方式存储，且节点按关键字有序排序.18.假设有 k 个关键字互为同义词，假设用线性探测法把这 k 个关键字存入哈希表中，至少要进展次探测。A.k-1 B.kC.k+1 D.k(k+1)/2 19.以下排序算法中，*一趟排序完毕后未必能选出一个元素放在其最终位置上的是。A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 20.以下排序方法中，不需要进展关键字的比拟。A.快速排序 B.归并排序 C.基数排序 D.堆排序 二、问答题共 3 小题，每题 10 分，共计 30 分 1.一棵度为 m 的树中有 n1个度为 1 的节点，n2个度为 2 的节点，nm个度为 m 的节点，问该树中有多少个叶子节点 2.设数据集合 D=1,12,5,8,3,10,7,13,9，试完成以下各题：1依次取 D 中各数据，构造一棵二叉排序树 bt；2如何依据此二叉树 bt 得到 D 的一个有序序列；3画出在二叉树 bt 中删除 12 后的树构造。3.一个有 n 个整数的数组 R1.n，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？假设不是，请给一个反例，假设是，请说明理由。三、算法设计题共计 40 分 1.设 A=(a1,a2,an)，B=(b1,b2,bm)是两个递增有序的线性表其中 n、m 均大于1，且所有数据元素均不一样。假设 A、B 均采用带头节点的单链表存放，设计一个尽可能高效的算法判断 B 是否为 A 的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。15 分 2.假设二叉树 b 采用二叉链存储构造存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。15 分 3.假设一个无向图是非连通的，采用邻接表作为存储构造，试设计一个算法，输出图中各连通分量的节点序列。10 分 四、附加题10 分 说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图 G 采用邻接表作为存储构造，设计一个算法，判断该图中是否存在回路。数据构造考试试题A参考答案.要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每答题纸都要写上和*。一、单项选择题每题 1.5 分，共计 30 分 1.D 2.B 3.A4.C 5.B 6.B 7.B 8.D 9.D 10.C 11.A 12.A 13.A 14.D 15.C 16.D 17.C 18.D19.C 20.C 二、问答题共 3 小题，每题 10 分，共计 30 分 1.解：依题意，设 n 为总的节点个数，n0为叶子节点即度为 0 的节点的个数，则有：n=n0+n1+n2+nm 又有：n-1=度的总数，即，n-1=n11+n22+nmm 两式相减得：1=n0-n2-2n3-(m-1)nm 则有：n0=1+n2+2n3+(m-1)nm=miini2)1(1。2.答：1此题构造的二叉排序树如图 10.20 所示。2D 的有序序列为 bt的中序遍历次序，即：1、3、5、7、8、9、10、12、13。3为了删除节点 12，找到其左子树中的最大节点 10其双亲节点为 8，将该节点删除并用 10 代替 12，删除后的树构造如图 10.21 所示。图 10.20 一棵二叉排序树图 10.21 删除 12 后的二叉排序树 3.答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为 k1、k2、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素 ki，有 kik2i，kik2i+1i 个两者值相等的节点，然后在两者值相等时同步后移，如果 B 扫描完毕返回 1，否则返回 0。对应的算法如下：int SubSeq(LinkList*A,LinkList*B)LinkList*p=A-ne*t,*q=B-ne*t;while(p!=NULL&q!=NULL)/找两个单链表中第一个值一样的节点 if(p-datadata)p=p-ne*t;else if(p-dataq-data)q=q-ne*t;else break;while(p!=NULL&q!=NULL&p-data=q-data)/当两者值相等时同步后移 p=p-ne*t;q=q-ne*t;if(q=NULL)/当 B 中节点比拟完毕返回 1 return 1;else /否则返回 0 return 0;本算法的时间复杂度为 O(m+n)，空间复杂度为 O(1)。其中 m、n 分别为 A、B 单链表的长度。2.15 分解：由于二叉树中最长路径一定是从根节点到*个叶子节点的路径，可以求出所有叶子节点到根节点的逆路径，通过比拟长度得出最长路径，可以采用多种解法。算法中用形参 ma*path数组存放最长路径，ma*pathlen 存放最长路径长度。解法 1：对应的算法如下：void Ma*Path(BTNode*b,ElemType ma*path,int&ma*pathlen)/ma*pathlen的初值为0 struct snode BTNode*node;/存放当前节点指针 int parent;/存放双亲节点在队列中的位置 QuMa*Size;/定义非循环队列 ElemType pathMa*Size;/存放一条路径 int pathlen;/存放一条路径长度 int front,rear,p,i;/定义队头和队尾指针 front=rear=-1;/置队列为空队列 rear+;Qurear.node=b;/根节点指针进进队 Qurear.parent=-1;/根节点没有双亲节点 while(front b=Qufront.node;/队头出队列 if(b-lchild=NULL&b-rchild=NULL)/*b为叶子节点 p=front;pathlen=0;while(Qup.parent!=-1)pathpathlen=Qup.node-data;pathlen+;p=Qup.parent;pathpathlen=Qup.node-data;pathlen+;if(pathlenma*pathlen)/通过比拟求最长路径 for(i=0;ilchild!=NULL)/左孩子节点进队 rear+;Qurear.node=b-lchild;Qurear.parent=front;if(b-rchild!=NULL)/右孩子节点进队 rear+;Qurear.node=b-rchild;Qurear.parent=front;本算法的时间复杂度为 O(n)，空间复杂度为 O(n)。解法 2：对应的算法如下：void Ma*Path1(BTNode*b,ElemType path,int pathlen,ElemType ma*path,int&ma*pathlen)/pathlen和ma*pathlen的初值均为0 int i;if(b=NULL)if(pathlenma*pathlen)/通过比拟求最长路径 for(i=pathlen-1;i=0;i-)ma*pathi=pathi;ma*pathlen=pathlen;else pathpathlen=b-data;/将当前节点放入路径中 pathlen+;/路径长度增1.Ma*Path1(b-lchild,path,pathlen,ma*path,ma*pathlen);/递归扫描左子树 Ma*Path1(b-rchild,path,pathlen,ma*path,ma*pathlen);/递归扫描右子树 本算法的时间复杂度为 O(n)，空间复杂度为 O(n)。解法 3：对应的算法如下：void Ma*Path2(BTNode*b,ElemType ma*path,int&ma*pathlen)/ma*pathlen的初值为0 BTNode*StMa*Size;BTNode*p;ElemType pathMa*Size;/存放一条路径 int pathlen;/存放一条路径长度 int i,flag,top=-1;/栈顶指针置初值 if(b!=NULL)do while(b!=NULL)/将*b的所有左节点进栈 top+;Sttop=b;b=b-lchild;p=NULL;/p指向栈顶节点的前一个已的节点 flag=1;/设置b的标记为已过 while(top!=-1&flag)b=Sttop;/取出当前的栈顶元素 if(b-rchild=p)/右孩子不存在或右孩子已被,之 if(b-lchild=NULL&b-rchild=NULL)/*b 为叶子节点 pathlen=0;for(i=top;i=0;i-)pathpathlen=Sti-data;pathlen+;if(pathlenma*pathlen)/通过比拟求最长路径 for(i=0;irchild;/b指向右孩子节点 flag=0;/设置未被的标记.while(top!=-1);printf(n);本算法的时间复杂度为 O(n)，空间复杂度为 O(n)。3.10 分解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：int visitedMA*V=0;DFSGraph(AGraph*G)int i,j=1;/用j记录连通分量的序号 for(i=0;in;i+)if(visitedi=0)printf(第%d个连通分量节点序列:,j+);DFS(G,i);/调用前面的深度优先遍历算法 采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：int visitedMA*V=0;BFSGraph(AGraph*G)int i,j=1;/用j记录连通分量的序号 for(i=0;in;i+)if(visitedi=0)printf(第%d个连通分量节点序列:,j+);BFS(G,i);/调用前面的广度优先遍历算法 四、附加题10 分 说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个连通图采用邻接表作为存储构造，试设计一个算法，判断其中是否存在回路。解：采用深度优先遍历方法，从顶点 v 出发，对每个的顶点 w 做标记 visitedw=1。假设顶点 w先和 i后均已过，表示从顶点 w 到顶点 i 存在一条路径。当从顶点 i 出发遍历，发现顶点 i 到顶点 w 有一条边时，表示存在一个回路 该回路上包含顶点 w 和 i。算法 Cycle(G,v,has)从顶点 v 出发判断图 G 中是否存在回路，has 是布尔值，初始调用时置为 false，执行后假设为 true 表示有回路，否则表示图 G 中没有回路。对应的算法如下：void Cycle(AGraph*G,int v,bool&has)/调用时has置初值false Arode*p;.int w;visitedv=1;/置已标记 p=G-adjlistv.firstarc;/p指向顶点v的第一个邻接点 while(p!=NULL)w=p-adjve*;if(visitedi=0)/假设顶点w未,递归它 Cycle(G,w,has);else /又找到了已过的顶点说明有回路 has=true;p=p-ne*tarc;/找下一个邻接点