2022年数据结构试题及答案 .pdf

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

1、工程硕士：数据结构试题及答案一、判断下列叙述的对错。（1）线性表的逻辑顺序与物理顺序总是一致的。（2）线性表的顺序存储表示优于链式存储表示。（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（4）二维数组是其数组元素为线性表的线性表。（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。二、设单链表中结点的结构为typedef struct node file:/链表结点定义ElemType data；file:/数据struct node*Link；file:/结点后继指针 ListNode；（1）已知指针p 所指结点不是尾结点，若在*p 之后插入结点*s，则应执

2、行下列哪一个操作？A.s-link=p；p-link=s；B.s-link=p-link；p-link=s；C.s-link=p-link；p=s；D.p-link=s；s-link=p；（2）非空的循环单链表first 的尾结点（由p 所指向）满足：A.p-link=NULL；B.p=NULL；C.p-link=first；D.p=first；三、设有一个顺序栈S，元素 s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为多少？四、一棵具有 n 个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层

3、有若干结点）有多少层？若设根结点在第0 层，则树的高度h 如何用 n 来表示（注意n 可能为 0）？五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。（1）对于一个具有n 个结点和 e 条边的无向图，若采用邻接表表示，则顶点表的大小为（A），所有边链表中边结点的总数为（B）。（2）采用邻接表存储的图的深度优先遍历算法类似于树的（C）。（3）采用邻接表存储的图的广度优先遍历算法类似于树的（D）。（4）判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（E）。供选择的答案A：nn+1n-1n+e B：e/2e2en+e CD：中根遍历先根遍历后根

4、遍历按层次遍历E：求关键路径的方法求最短路径的Dijkstra 方法深度优先遍历算法广度优先遍历算法六、填空题（1）在用于表示有向图的邻接矩阵中，对第i 行的元素进行累加，可得到第i 个顶点名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -的（）度，而对第j 列的元素进行累加，可得到第j 个顶点的（）度。（2）一个连通图的生成树是该图的（）连通子图。若这个连通图有n 个顶点，则它的生成树有（）条边。（3）给定序列 100，86，48，73，35，39，42，57，66，21，按堆结构的定义，则它一定（）堆。（4）在进行直接插入排序时，其数据比较次数与数据的初始排列（）关；

5、而在进行直接选择排序时，其数据比较次数与数据的初始排列（）关。（5）利用关键码分别为10，20，30，40 的四个结点，能构造出（）种不同的二叉搜索树。七、设带表头结点的双向链表的定义为typedef int ElemType；typedef struct dnode file:/双向链表结点定义ElemType data；file:/数据struct dnode*lLink，*rLink；file:/结点前驱与后继指针DblNode；typedef DblNode*DblList；file:/双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLi

6、nk 中，并利用左链域lLink 把所有结点按照其值从小到大的顺序连接起来。八、设有一个关键码的输入序列 55，31，11，37，46，73，63，02，07 （1）从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。九、下面是求连通网络的最小生成树的Prim 算法的实现，中间有5 个地方缺失，请阅读程序后将它们补上。const int MaxInt=INT_MAX；file:/INT_MAX的值在中const int n=6；file:

7、/图的顶点数，应由用户定义typedef int AdjMatrixnn；file:/用二维数组作为邻接矩阵表示typedef struct file:/生成树的边结点int fromVex，toVex；file:/边的起点与终点int weight；file:/边上的权值TreeEdgeNode；typedef TreeEdgeNode MSTn-1；file:/最小生成树定义void PrimMST（AdjMatrix G，MST T，int rt）file:/从顶点 rt 出发构造图G 的最小生成树T，rt 成为树的根结点TreeEdgeNode e；int i，k=0，min，minp

8、os，v；for（i=0；i.fromVex=rt；Tk.toVex=I；Tk+.weight=Grt；for（k=0；k n-1；k+）file:/依次求 MST 的候选边min=MaxInt；for（i=k；i n-1；i+）file:/遍历当前候选边集合名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -if（T.weight ；Tminpos=Tk；Tk=e；v=Tk.toVex；for（i=k+1；i T.toVex T.toVex；T.fromVex=v；参考答案：一、（1）错（2）错（3）对（4）错（5）对二、（1）B（2）C 三、3 四、h=log2（n+1

9、）-1 五、A.B.C.D.E.六、出入极小n-1 是（最小）有无14 七、算法如下void sort（DblNode*L）DblNode*s=L-rlink；file:/指针 s指向待插入结点，初始时指向第一个结点while（s！=NULL）file:/处理所有结点pre=L；p=L-lLink；file:/指针 p 指向待比较的结点，pre 是 p 的前驱指针while（p！=NULL&s-data data）file:/循 lLink 链寻找结点*s 的插入位置 pre=p；p=p-lLink；pre-lLink=s；s-lLink=p；s=s-rLink；file:/结点*s 在 lLink 方向插入到*pre 与*p 之间 八、关键码的输入序列 55，31，11，37，46，73，63，02，07 在等概率下查找成功的平均查找长度在等概率下查找不成功的平均查找长度九Tk.toVex=i min=MaxInt minpos=i exit（1）T.fromVex=v名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -