2017年湘潭大学信息工程学院870数据结构(二)[专业硕士]考研题库
● 摘要
一、填空题
1． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
2． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
3． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
4． 设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15
【解析】当时，而
，时，
5．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
6． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
7． 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】（n －1）/2
其中队头和队尾指针分别为front 和rear , 则此循
要使前者快于后者，n 至少为
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时
，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
10．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）链表未到尾就一直进行
（2）
将当前结点作为头结点后的第一元素结点插入
的地址是：_____。
二、选择题
11．下列选项中，用于提高RAID 可靠性的措施有（ ）
I. 磁盘镜像 II. 条带化 III. 奇偶校验 IV . 增加Cache 机制 A. 仅 I 、II B. 仅 I 、III C. 仅 I 、III 和IV D. 仅II 、III 和IV 【答案】B
【解析】能够提高RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。
12．在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
13．下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 尚响应比优先调度算法 【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
14．有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。