2022年数据结构考试题8 .pdf

《2022年数据结构考试题8 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考试题8 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、要求： 所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（选择最准确的一项，共15 小题，每小题 2 分，共计 30 分）1. 数据结构是指。A. 一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为。void fun(int n) int i=1,s=0; while (i=n) s+=i+100; i+; A. O(n) B. O(n) C. O(nlog2n) D. O(log2n) 3. 在一个长度为n 的有序顺序表中删除其中第一个元素值为x 的

2、元素时，在查找元素x时采用二分查找方法，此时删除算法的时间复杂度为。A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 4. 若一个栈采用数组s0.n- 1存放其元素，初始时栈顶指针为n，则以下元素x 进栈的正确操作是。A.top+;stop= x; B.stop= x;top+; C.top- ;stop=x; B.stop= x;top- ; 5. 设环形队列中数组的下标为0N- 1，其队头、队尾指针分别为front 和 rear（front指向队列中队头元素的前一个位置，rear 指向队尾元素的位置） ，则其元素个数为。A. rear- front B. rear

3、- front- 1 C. (rear- front) N+1 D. (rear- front+N) N 6. 若用一个大小为6 的数组来实现环形队列，队头指针front 指向队列中队头元素的前一个位置，队尾指针rear 指向队尾元素的位置。若当前rear 和 front 的值分别为0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为。A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页7. 一棵高度为h（h1）的完全二叉树至少

4、有个结点。A. 2h-1B. 2hC. 2h+1 D. 2h-1+1 8. 设一棵哈夫曼树中有999 个结点，该哈夫曼树用于对个字符进行编码。A. 999 B. 499 C. 500 D. 501 9. 一个含有n 个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是。A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 稠密矩阵10. 设无向连通图有n 个顶点 e 条边，若满足，则图中一定有回路。A. enB. e1000）个元素数据序列，某人采用了一种排序方法对其按关键字递增排序，该排序方法需要关键字比较，其平均时间复杂度接近最好的情况，空间复杂度为 O(1)，该排序方法可能是。A.快速排序B.

5、堆排序C.二路归并排序D.都不适合15. 对一个线性序列进行排序，该序列采用单链表存储，最好采用排序方法。A.直接插入排序B.希尔排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页C.快速排序D.都不适合二、问答题（共 3 小题，每小题 10 分，共计 30 分）1. 如果对含有n（n1）个元素的线性表的运算只有4 种：删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构，并简要说明理由。（1）只有尾结点指针没有头结点指针的循环单链表（2）只有尾结点指针没有头结

6、点指针的非循环双链表（3）只有头结点指针没有尾结点指针的循环双链表（4）既有头结点指针也有尾结点指针的循环单链表2. 对于一个带权连通无向图G， 可以采用 Prim 算法构造出从某个顶点v 出发的最小生成树，问该最小生成树是否一定包含从顶点v 到其他所有顶点的最短路径。如果回答是，请予以证明；如果回答不是，请给出反例。3. 有一棵二叉排序树按先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20) 。回答以下问题：（1）画出该二叉排序树。（2）给出该二叉排序树的中序遍历序列。（3）求在等概率下的查找成功和不成功情况下的平均查找长度。三、算法设计题（共3 小题，共计 40 分

7、）1.（15 分）假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p) 求指定值为x 的结点的双亲结点p。提示，根结点的双亲为NULL ，若在二叉树b 中未找到值为x 的结点， p 亦为 NULL 。2. （10 分）假设一个有向图G 采用邻接表存储。设计一个算法判断顶点i 和顶点 j（ij）之间是否相互连通，假设这两个顶点均存在。3.（15 分）有一个含有n 个整数的无序数据序列，所有的数据元素均不相同，采用整数数组 R0.n- 1存储，请完成以下任务：（1）设计一个尽可能高效的算法，输出该序列中第k（1

8、k n）小的元素，算法中给出适当的注释信息。提示：利用快速排序的思路。（2）分析你所设计的求解算法的平均时间复杂度，并给出求解过程。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页“数据结构”考试试题（A）参考答案要求： 所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（共15 小题，每小题 2 分，共计 30 分）1.D 2.B 3.A 4. C 5. D 6. B 7. A 8. C 9. A 10. A 11. B 12. D 13.C 14.B 15.A 二、问答题（共 3

9、小题，每小题 10 分，共计 30 分）1. 答：本题答案为（3） ，因为实现上述4 种运算的时间复杂度均为O(1)。2. 答：不是。如图1 所示的图G 从顶点 0 出发的最小生成树如图2 所示，而从顶点0到顶点的 2 的最短路径为02，而不是最小生成树中的012。6 8 4 0 1 2 6 4 0 1 2 图 1 一个带权连通无向图G 图 2 图 G 的一棵最小生成树3. 答： （1）先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20) ，中序序列是一个有序序列，所以为：(2,5,6,8,10,12,15,16,18,20) ，由先序序列和中序序列可以构造出对应的二叉

10、树，如图 3 所示。 4 分（2）中序遍历序列为：2,5,6,8,10,12,15,16,18,20。4 分（3）ASL成功=(1 1+2 2+4 3+3 4)/10=29/10 。1 分ASL不成功=(5 3+6 4/11=39/11。1 分12 5 2 8 6 10 16 15 18 20 图 3 三、算法设计题（共3 小题，共计 40 分）1.（15 分）解：算法如下：void findparent(BTNode *b,ElemType x,BTNode *&p) if (b!=NULL) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4

11、页，共 6 页 if (b-data=x) p=NULL; else if (b-lchild!=NULL & b-lchild-data=x) p=b; else if (b-rchild!=NULL & b-rchild-data=x) p=b; else findparent(b-lchild,x,p); if (p=NULL) findparent(b-rchild,x,p); else p=NULL; 2. （10 分）解：算法如下：int visitedMAXV; void DFS(ALGraph *G,int v) /深度优先遍历算法 ArcNode *p; visitedv=1

12、; /置已访问标记p=G-adjlistv.firstarc; /p指向顶点 v的第一个邻接点while (p!=NULL) if (visitedp-adjvex=0) /若p-adjvex顶点未访问 ,递归访问它DFS(G,p-adjvex); p=p-nextarc; /p指向顶点 v的下一个邻接点 bool DFSTrave(ALGraph *G,int i,int j) int k; bool flag1=false,flag2=false; for (k=0;kn;k+) visitedk=0; DFS(G,i); /从顶点 i开始进行深度优先遍历if (visitedj=1) f

13、lag1=true; for (k=0;kn;k+) visitedk=0; DFS(G,j); /从顶点 j开始进行深度优先遍历if (visitedi=1) flag2=true; if (flag1 & flage2) return true; else return false; 3.（15 分）（ 1）采用快速排序的算法如下：（12 分）int QuickSelect(int R,int s,int t,int k) /在Rs.t序列中找第 k小的元素精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页 int i=s,j=

14、t; int tmp; if (si & Rj=tmp) j-; /从右向左扫描 ,找第 1个小于 tmp的Rj Ri=Rj; /将Rj 前移到 Ri的位置while (ij & Ri=tmp) i+; /从左向右扫描 ,找第 1个大于 tmp的Ri Rj=Ri; /将Ri 后移到 Rj 的位置 Ri=tmp; if (k-1=i) return Ri; else if (k-1=1 & k=n) printf(%dn, QuickSelect( R,0,n-1,k); （2）对于求 R 中第 k 小元素的算法Mink( R， n，k)，设其算法平均执行时间为T(n)，有以下递推式： （3 分）T(1)=1 T(n)=T( n/2)+O( n) 则： T(n)= T(n/2)+O( n)= T(n/22)+O(n)+O(n/2)=T( n/2m)+O(n)+O(n/2)+ +O(n/2m) /m=log2n=O(1)+O( n)+O(n) =O(n) 所以，该算法的平均时间复杂度为O(n)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页