【冲刺】2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结 构》考研冲刺模拟五套题及参考答案

考研专业课模拟试题 模拟试题简介 试题名称： 【冲刺】2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考 研冲刺模拟五套题及参考答案 试题题型： 单项选择题+应用题+算法设计题 参考书目： 严蔚敏《数据结构(C 语言版)》 适用院系： （001）航空学院

版权说明 编写组依法对本书享有专有著作权，由本机构组织编写与报考院校无关，同时我们尊重知识产权， 对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数 据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容 来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何 异议请直接联系我们，我们会在第一时间与您沟通处理。 因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生 读者批评指正。

温馨提示 考研资料产品为在线阅读使用，不支持下载，考生可以根据自身学习需要自行到指定打印店打印邮寄 到家。 根据《消费者权益保护法》第二十五条规定，数字产品一经激活和拆封，其具有无形性和可复制性， 不支持退款退货，请先预览内容确认无误后再购买。

第 2 页 共 53 页

考研专业课模拟试题 目录 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（一） ............................................................................................................................4 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（二） ..........................................................................................................................15 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（三） ..........................................................................................................................24 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（四） ..........................................................................................................................33 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（五） ..........................................................................................................................42

第 3 页 共 53 页

考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年中国航空研究院(640 所)083500 软件工程《885 软件工程专业基础综合：数据结构》考研冲刺模 拟五套题及参考答案（一） 一、单项选择题 1． 下面关于 B_树和 B+树的叙述中，不正确的结论是__。 A.B_树和B+树都能有效地支持顺序查找； B.B_树和B+树都能有效地支持随机查找； C.B_树和B+树都是平衡的多分树； D.B_树和B+树都可用于文件索引结构。 【答案】A 2． 循环队列存储在数组 A. B. C. D. 【答案】D 3． 一组记录关键码为 中，则入队时的操作为__。

，则利用快速排序的方法，以第一个记录为基准得到的一次

划分结果为__。掌й心博阅☇电子书 A. B. C. D. 【答案】C 【解析】以 46 为基准的划分过程如下:

4． 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度 为 1 的结点，则树 T 的叶结点个数是__。 A.41 B.82 C.113 D.122 【答案】B 【解析】(1)树的度为树中结点度的最大值。 (2)由己知，树中结点的度值不大于 4。 (3)度为 i 的结点有 1 个孩子结点。 (4)设叶子结点个数为 X，

第 4 页 共 53 页

考研专业课模拟试题 树的结点数 树的边数 由树的性质： 。 。 ，求解得 。

5． 下列说法正确的是。__ A. B. C. D. _ 【答案】D 6． n 个顶点的无向图用邻接矩阵 A 表示时，顶点 Vi 的度为__。 A. B. C. D. 【答案】A 【解析】无向图的邻接矩阵存储结构中，顶点的度为第 i 行或第 i 列的非 0 元素个数之和。本题中 A 为第 i 行非 0 元素个数之和，B 为第 j 列非 0 元素个数之和，C 为第 j 行非 0 元素个数之和，D 为第 j 列和 第 i 列非 0 元素个数之和。 7． __不是栈的基本运算。 A.删除栈顶元素 B.删除栈底元素 C.判断栈是否为空 D.将栈置为空栈 【答案】B 【解析】栈是一个“先进后出”的数据结构，操作的时候只有两种操作，进栈和出栈，都是对栈顶元 素而言的 8． 若一个具有 N 个顶点 K 条边的无向图是一个森林 ，则该森林中必有__棵树。 A.K B.N C.N-K D.1 【答案】C 【解析】一棵具有 N 个顶点的树有 N-1 条边，因此设此森林中有 M 棵树，每棵树具有的顶点数为 ，则： 掌б心博阅电〼子↑书

上面两式相减可得

。

第 5 页 共 53 页

考研专业课模拟试题 9． 广义表 ，则下面式子 的值为__。(Head 与 Tail 分别

是取表头和表尾的函数。)掌ㅠ心博┨阅电子书 A. B.d C.f D. 【答案】A 二、应用题 10．给定 n 个村庄之间的交通图。若村庄 i 与村庄 j 之间有路可通，则将顶点 i 与顶点 j 之间用边连接， 边上的权值 表示这条道路的长度。 现打算在这 n 个村庄中选定一个村庄建一所医院。 编写一个算法求出 该医院应建在哪个村庄，才能使距离医院最远的村庄到医院的路程尽可能最短。掌щ心┯博阅电子书 【答案】先要建立应用问题的数据结构，将 n 个村庄的交通图用邻接矩阵 A 表示；再用弗洛伊德算法 计算每对顶点之间的最短路径；然后找出从每一个顶点到其他各顶点的最短路径中最长的路径：最后在这 n 条最长路径中找出最短的一条。算法描述如下：

11．设有序列： (1)建成二叉排序树；掌ㅗ心博阅┲电子书 (2)对d=3执行一次shell排序的结果； (3)建成堆顶最大的初始堆； (4)建成三叉哈夫曼树； (5)执行一遍快速排序的结果。 【答案】(1)建成的二叉排序树如下图1所示。

，给出如下结果：

第 6 页 共 53 页

考研专业课模拟试题

19．试写出在含有 n 个元素的小顶堆中增加一个新元素 X，且调整为堆的算法。 【答案】首先，把新元素添加到堆尾部的位置，如果该元素的 key 值小于其直接祖先结点，则交换该 元素与其祖先的位置，一直到该元素不小于其直接祖先或者该元素为根结点为止。算法描述如下：

20．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双向链表，算法返 回头结点的地址。掌㈄心博阅电子书 【答案】采用递归算法来实现，首先生成双向链表的头结点，对于二叉树中每一个叶子结点，都要 建立该叶子结点和双向链表中最后一个结点的关联，这需要修改两个指针来完成，所以，要时刻记录双 向链表的头结点和最后一个结点的位置，这里定义全局变量 head 和 pre。算法代码如下：

第 21 页 共 53 页

考研专业课模拟试题 (假设 1 个对象的序列所用递归栈的深度为 0)。 如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再 对较短的子序列进行排序，可用表示最坏情况的大 O 表示法表示。此时其递归栈的深度不一定正好是 ，其最坏情况为 。掌ч心博阅电子书 13．现有一文件 F 含有 1000 个记录，其中只有少量记录次序不对，且它们距离正确位置不远；如果以比 较和移动次数作为度量，那么将其排序最好采用什么方法？为什么？ 【答案】采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于少量 次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接插入排序算法。 14．给定序列 (1)按表中元素的顺序依次插入一棵初始为空的二叉排序树。画出插入完成后的二叉排序树，并求其 在等概率情况下查找成功的平均查找长度。 (2)按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与(1)比 较，可得出什么结论？ 【答案】(1)按输入顺序进行插入后的二叉排序树如下图 1 所示。其在等概率下查找成功的平均查找 长度为 。

(2) 构 造 的 一 棵 平 衡 二 叉 树 如 下 图 2 所 示 。 其 在 等 概 率 下 查 找 成 功 的 平 均 查 找 长 度 为 。与(1)相比，可见在同样序列的查找中，二叉平衡树比二叉排序树的 平均查找长度要小，查找效率较高。

图1

图2

第 36 页 共 53 页

考研专业课模拟试题 【答案】利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。核心语句段如下:

23．写出和下列递归过程等价的非递归过程：掌ъ心博阅电子书

【答案】

第 51 页 共 53 页

试读已结束 激活后可查看剩余未读页数！