《2022年数据结构考试题.docx》由会员分享，可在线阅读，更多相关《2022年数据结构考试题.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 要求： 全部的题目的解答均写在答题纸上,需写清晰题目的序号；每张答题纸都要写上姓名和学号；一、单项选择题（每道题1.5 分,共计 30 分）1. 数据结构是指；A. 一种数据类型B. 数据的储备结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为；void funint n int i=1; while i=n i+; A. On B. O n C. Onlog 2n D. Olog 2n 3. 在一个长度为 n 的有序次序表中删除元素值为 x 的元素时,在查找元素 x 时采纳二
2、分查找,此时的时间复杂度为；A. On B. Onlog 2n C. On 2 D. O n 4. 在一个带头结点的循环单链表 L 中,删除元素值为 x 的结点,算法的时间复杂度为；A. On B. O n C. Onlog 2n D. On 2 5. 如一个栈采纳数组 s0.n-1 存放其元素, 初始时栈顶指针为 n,就以下元素 x 进栈的正确操作是；A.top+;stop=x; B.stop=x;top+; C.top-;stop=x; B.stop=x;top-; 6. 中缀表达式“2*3+4 - 1” 的后缀表达式是,其中 #表示一个数值的终止；A. 2#3#4#1#*+ -B. 2#
3、3#4#+*1# -C. 2#3#4#*+1# -D. - +*2#3#4#1# 7. 设环形队列中数组的下标为 0N- 1,其队头、队尾指针分别为 front 和 rear（front指向队列中队头元素的前一个位置,rear 指向队尾元素的位置） ,就其元素个数为；A. rear- front B. rear- front- 1 C. rear- front N+1 D. rear- front+N N 名师归纳总结 - - - - - - -8. 如用一个大小为6 的数组来实现环形队列,队头指针front 指向队列中队头元素的前一个位置,队尾指针rear 指向队尾元素的位置；如当前rear
4、 和 front 的值分别为0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为；第 1 页,共 9 页精选学习资料 - - - - - - - - - A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 9. 一棵深度为 h（h1）的完全二叉树至少有 个结点；h-1 hA. 2 B. 2C. 2 h+1 D. 2 h-1+1 10. 一棵含有 n 个结点的线索二叉树中,其线索个数为；A. 2n B. n- 1 C. n+1 D. n 11. 设一棵哈夫曼树中有 1999 个结点,该哈夫曼树用于对 个字符进行编码；A. 999 B. 9
5、98 C. 1000 D. 1001 12. 一个含有 n 个顶点的无向连通图采纳邻接矩阵储备,就该矩阵肯定是；A. 对称矩阵 B. 非对称矩阵C. 稀疏矩阵 D. 稠密矩阵13. 设无向连通图有 n 个顶点 e 条边,如满意,就图中肯定有回路；A. en B. e1）个元素的线性表的运算只有4 种：删除第一个元素；删除最终一个元素；在第一个元素前面插入新元素；在最终一个元素的后面插入新元素,就最好使 用以下哪种储备结构,并简要说明理由；（1）只有尾结点指针没有头结点指针的循环单链表（2）只有尾结点指针没有头结点指针的非循环双链表（3）只有头结点指针没有尾结点指针的循环双链表（4）既有头结点指
6、针也有尾结点指针的循环单链表 0、1、2、3 的结点数分别为 14、4、3、2,求该树 2. 已知一棵度为 4 的树中,其度为 的结点总数 n 和度为 4 的结点个数,并给出推导过程；3. 有人提出这样的一种从图G 中顶点 u 开头构造最小生成树的方法：假设 G=V ,E是一个具有 n 个顶点的带权连通无向图,T=U ,TE是 G 的最小生成树,其中 U 是 T 的顶点集, TE 是 T 的边集,就由 G 构造从起始顶点 u 动身的最小生成树 T 的步骤如下：（1）初始化 U=u ；以 u 到其他顶点的全部边为候选边；（2）重复以下步骤n- 1 次,使得其他n- 1 个顶点被加入到U 中；从候
7、选边中选择权值最小的边加入到TE,设该边在 V-U 中的顶点是 v,将 v 加入 U 中；考查顶点 v,将 v 与 V- U 顶点集中的全部边作为新的候选边；如此方法求得的 T 是最小生成树,请予以证明；如不能求得最小边,请举出反例；4. 有一棵二叉排序树按先序遍历得到的序列为：问题：（1）画出该二叉排序树；（2）给出该二叉排序树的中序遍历序列；12,5,2,8,6,10,16,15,18,20 ；回答以下（3）求在等概率下的查找胜利和不胜利情形下的平均查找长度；三、算法设计题（每道题10 分,共计 30 分）名师归纳总结 1. 设 A 和 B 是两个结点个数分别为m 和 n 的单链表（带头结
8、点） ,其中元素递增有序；第 3 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 设计一个尽可能高效的算法求A 和 B 的交集,要求不破坏A、B 的结点,将交集存放在单链表 C 中；给出你所设计的算法的时间复杂度和空间复杂度；2. 假设二叉树 b 采纳二叉链储备结构,设计一个算法 void findparentBTNode *b,ElemType x,BTNode *&p 求指定值为 x 的结点的双亲结点 p,提示,根结点的双亲为NULL ,如在 b 中未找到值为x 的结点, p 亦为 NULL ；3. 假设一个连通图采纳邻接表 G 储备结构表示； 设
9、计一个算法, 求起点 u 到终点 v 的 经过顶点 k 的全部路径；四、附加题（ 10 分）说明：附加题不计入期未考试总分,但计入本课程的总分；假设某专业有如干个班,每个班有如干同学,每个同学包含姓名和分数,这样构成一棵树,如图1 所示；假设树中每个结点的name 域均不相同,该树采纳孩子兄弟链储备结构,其结点类型定义如下：typedef struct node char name50; / 专业、班号或姓名float score; / 分数struct node *child; / 指向最左边的孩子结点struct node *brother; / 指向下一个兄弟结点 TNode; 完成以下
10、算法：（1）设计一个算法求全部的同学人数；（2）求指定某班的平均分；name:运算机专业 score:0 name:王华name:计科 1 name:张兵name:陈强name:计科 n name:张山score:0 score:0 name:李明name:许源score:86 score:79 score:79 score:85 score:92 score:69 图 1 一棵同学成果树名师归纳总结 - - - - - - -第 4 页,共 9 页精选学习资料 - - - - - - - - - “ 数据结构” 考试试题（A）参考答案要求： 全部的题目的解答均写在答题纸上,需写清晰题目的序号
11、；每张答题纸都要写 上姓名和学号；一、单项选择题（每道题1.5 分,共计 30 分）1. D 2. A 3. A 4. A 5. C 6. B 7. D 8. B 9. A 10. C 11. C 12. A 13. A 14. D 15. D 16. C 17. D 18. A 19. A 20. C 二、问答题（共 4 小题,每道题 10 分,共计 40 分）1. 答：此题答案为（3）,由于实现上述 4 种运算的时间复杂度均为 O1；【评分说明】选择结果占 4 分,理由占 6 分；如结果错误,但对各操作时间复杂度作了分析,可给 25 分；2. 答：结点总数 n=n0+n1+n2+n3+n4
12、,即 n=23+n4,又有：度之和 =n-1=0 n0+1n1+2n2+3 n3+4n4,即 n=17+4 n4,综合两式得：n4=2,n=25；所以,该树的结点总数为 25,度为 4的结点个数为 2；【评分说明】结果为 4 分,过程占 6 分；3. 答：此方法不能求得最小生成树；例如,对于如图5.1（a）所示的带权连通无向图,依据上述方法从顶点0 开头求得的结果为5.1（b）所示的树,明显它不是最小生成树,正确的最小生成树如图5.1（c）所示；在有些情形下,上述方法无法求得结果,例如对于如图5.1（d）所示的带权连通无向图,从顶点 0 动身,找到顶点 1（边（ 0,1）,从顶点 1 动身,找
13、到顶点 3（边（ 1,3）,再从顶点 3 动身,找到顶点 0（边（ 3,0）,这样构成回路,就不能求得最小生成树了；0 0 1 2 1 4 1 3 1 3 3 2 5 3 2 5 （ a）（ b）0 0 1 1 2 1 4 3 1 3 3 3 2 4 2 5 （ c）（d）图 1 求最小生成树的反例说明：只需给出一种情形即可；名师归纳总结 【评分说明】回答不能求得最小生成树得5 分,反例为5 分；如指出可求得最小生成第 5 页,共 9 页树,依据证明过程给12 分；- - - - - - -精选学习资料 - - - - - - - - - 4. 答：（1）先序遍历得到的序列为：12,5,2,8
14、,6,10,16,15,18,20 ,中序序列是一个有序序列,所以为：2,5,6,8,10,12,15,16,18,20 ,由先序序列和中序序列可以构造出对应的二叉树,如图 2 所示；（2）中序遍历序列为：2,5,6,8,10,12,15,16,18,20；（3）ASL 胜利=11+2 2+4 3+3 4/10=29/10 ；ASL 不胜利 =5 3+64/11=39/11；12 2 5 8 10 15 16 18 20 6 图 2 【评分说明】 （1）小题占 6 分,（2）（3）小题各占 2 分；三、算法设计题（每道题10 分,共计 30 分）1. 设 A 和 B 是两个结点个数分别为 m
15、和 n 的单链表（带头结点） ,其中元素递增有序；设计一个尽可能高效的算法求 A 和 B 的交集,要求不破坏 A、B 的结点,将交集存放在单 链表 C 中；给出你所设计的算法的时间复杂度和空间复杂度；解：算法如下：void insertionLinkList *A,LinkList *B,LinkList *&C LinkList *p=A-next,*q=B-next,*s,*t; C=LinkList *mallocsizeofLinkList; t=C; while p.=NULL & q.=NULL if p-data=q-data s=LinkList *mallocsizeofLi
16、nkList; s-data=p-data; t-next=s; t=s; p=p-next; q=q-next; else if p-datadata p=p-next; else q=q-next; t-next=NULL; 名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - 算法的时间复杂度为 Om+n ,空间复杂度为 OMINm,n ；【评分说明】算法为 8 分,算法的时间复杂度和空间复杂度各占 1 分；2. 假设二叉树 b 采纳二叉链储备结构,设计一个算法 void findparentBTNode *b,ElemType
17、x,BTNode *&p 求指定值为 x 的结点的双亲结点 p,提示,根结点的双亲为 NULL ,如未找到这样的结点,p 亦为 NULL ；解：算法如下：void findparentBTNode *b,ElemType x,BTNode *&p if b.=NULL 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 findparentb-lchild,x,p; if p=NULL findparentb-rc
18、hild,x,p; else p=NULL; 【评分说明】此题有多种解法,相应给分；3. 假设一个连通图采纳邻接表 经过顶点 k 的全部路径；解：算法如下：G 储备结构表示； 设计一个算法, 求起点 u 到终点 v 的int visitedMAXV=0; / 全局变量 void PathAll ALGraph *G,int u,int v,int k,int path,int d /d 是到当前为止已走过的路径长度,调用时初值为-1 int m,i; ArcNode *p; visitedu=1; d+; /路径长度增1 pathd=u; /将当前顶点添加到路径中if u=v & Inpath
19、,d,k=l /输出一条路径 printf ; for i=0;iadjlistu.firstarc; /p指向顶点 u 的第一条弧的弧头节点while p.=NULL 名师归纳总结 - - - - - - -第 7 页,共 9 页精选学习资料 - - - - - - - - - m=p-adjvex; /m为 u 的邻接点if visitedm=0 / 如该顶点未标记拜访, 就递归拜访之PathAllG,m,v,l,path,d; p=p-nextarc; / 找 u 的下一个邻接点 visitedu=0; / 复原环境：使该顶点可重新使用 int Inint path,int d,int
20、k /判定顶点k 是否包含在路径中 int i; for i=0;ichild=NULL return 1; return countb-child+countb-brother; 说明：此题可以从链表的角度求解；（2）算法如下：int AverageTNode *b,char class,float &avg int n=0; float sum=0; TNode *p=b-child; /p指向班号结点while p.=NULL & strcmpp-name,class.=0 p=p-brother; if p=NULL return 0; / 没找到该班号,返回 0 p=p-child; /p 指向该班的第一个同学 while p.=NULL n+; / 累计人数 sum+=p-score; / 累计分数 p=p-brother; avg=sum/n; / 求平均分 return 1; 名师归纳总结 【评分说明】两小题各占5 分；第 9 页,共 9 页- - - - - - -