【冲刺】2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题 及参考答案
考研专业课模拟试题 模拟试题简介 试题名称： 【冲刺】2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参 考答案 试题题型： 单项选择题+应用题+算法设计题 参考书目： 《数据结构(c 语言版)》 ，严蔚敏、吴伟民编，清华大学出版社 适用院系： （000）不区分院系所
版权说明 编写组依法对本书享有专有著作权，由本机构组织编写与报考院校无关，同时我们尊重知识产权， 对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数 据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容 来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何 异议请直接联系我们，我们会在第一时间与您沟通处理。 因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生 读者批评指正。
温馨提示 考研资料产品为在线阅读使用，不支持下载，考生可以根据自身学习需要自行到指定打印店打印邮寄 到家。 根据《消费者权益保护法》第二十五条规定，数字产品一经激活和拆封，其具有无形性和可复制性， 不支持退款退货，请先预览内容确认无误后再购买。
第 2 页 共 53 页
考研专业课模拟试题 目录 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （一） ..............................................................................................................................................................4 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （二） ............................................................................................................................................................15 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （三） ............................................................................................................................................................25 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （四） ............................................................................................................................................................36 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （五） ............................................................................................................................................................45
第 3 页 共 53 页
考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （一） 一、单项选择题 1． 由权值为 的 4 个叶子结点构造一棵哈夫曼树，该树的带权路径长度为__。 A.23 B.37 C.44 D.46 【答案】C 【解析】首先构造这棵哈夫曼树，如图下所示。带权路径长度为： 。
图 2． 下面哪一个方法可以判断出一个有向图中是否有环(回路)？__ A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 【答案】A、B 均可 3． 在长度为 n 的顺序表中删除一个元素的时间复杂度为__。 A. 掌р心博阅电子书 B. C. D. 【答案】C 【解析】在长度为 n 的顺序表中删除一个元素平均需要移动 ，该算法的主要时间花在移动元素上。
个元素，对应的时间复杂度为
4． 在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多的是__。 A.5 B.6 C.10 掌ㅡ心博阅电子书
第 4 页 共 53 页
考研专业课模拟试题 D.15 【答案】D 【解析】关键字数量不变，要求结点数量最多，即每个结点中含关键字的数量最少。根据 4 阶 B 树的 定义，根结点最少含 1 个关键字，非根结点中最少含个关键字 ，所以每个结点中，关键字数 量最少都为 1 个， 即每个结点都有 2 个分支， 类似于排序二叉树， 而 15 个结点正好可以构造一个 4 层的 4 阶 B 树，使得叶子结点全在第四层，符合 B 树定义，因此选 D。 5． 为提高散列(Hash)表的查找效率，可以采取的正确措施是__。 Ⅰ.增大装填(载)因子 Ⅱ.设计冲突(碰撞)少的散列函数 Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象 A.仅Ⅰ B.仅Ⅱ C.仅Ⅰ、Ⅱ D.仅Ⅱ、Ⅲ 【答案】D 【解析】装填(载)因子 a 越大，发生冲突的可能性越大，所以Ⅰ错误。因为哈希表是由散列函数和处 理冲突两部分组成的，查找效率与这两部分有关，所以Ⅱ和Ⅲ是正确的。本题答案为 D。 6． 要连通具有 n 个顶点的有向图，至少需要__条边。 A.n-1 B.n C.n+1 D.2n 【答案】B 7． 二叉树的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序__。 A.都不相同 B.完全相同 C.先序和中序相同而与后序不同 D.中序和后序相同而与先序不同 【答案】B 【解析】(1)叶子结点没有左子树和右子树。 (2)对于叶子结点所在子树的遍历，仅有根结点，三种遍历顺序相同。 (3)叶子结点存在于子树，而三种遍历中左子树和右子树的相对位置不变。 8． 对一组数据 进行排序，若前三趟的结果如下。 第一趟： 第二趟： 第三趟： 则采用的排序方法可能是__。 A.起泡排序 B.希尔排序 C.归并排序 D.基数排序 【答案】A
第 5 页 共 53 页
考研专业课模拟试题 【解析】希尔排序第一趟会将( )分为一组，将其排序，从第一趟结果可以看出不可能是希尔排 序。归并排序会将( )分为一组，将其排序，从第一趟结果可以看出不可能是归并排序。基数排序第一 趟的结果会将个位数或十位数排在相邻位置，也就是第一趟会将 2、5 相邻或 12、16、10 相邻，从第一趟 结果可以看出不可能是基数排序，而且由于所有关键字最多两位，只能进行两趟基数排序。本题答案为 A 9． 若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 至少有__个顶点。 A.11 B.10 C.9 D.8 【答案】B 【解析】因为 G 为非连通图，所以，G 中至少含有两个连通子图，而且该图不含有回路和多重边。题 目问的是至少有多少个顶点，因此，一个连通图可看成是只有 1 个顶点，另一个连通图可看成是一个完全 图(因为完全图在最少顶点的情况下能得到的边数最多)，这样，该问题就转化为“36 条边的完全图有多少 个顶点” ，因为具有 n 个顶点的无向完全图的边的条数为 ，可以算出 n=9 满足条件。再加上另一 个连通图(只有一个点)，则图 G 至少有 10 个顶点。 二、应用题 10．假设二叉树采用二叉链存储结构存储，设计一个算法，利用节点的右孩子指针 rchild 将一棵二叉树的 叶子节点按从左往右的顺序串成一个单链表。掌р心博阅Р电子书 【答案】采用先序遍历的递归算法求解，在遍历过程中采用尾插法构建叶子节点的单链表，head 指向 建立的单链表的首节点(初值为 NULL),tail 指向单链表的尾节点。对应的算法如下。
11．设某文件中待排序记录的排序码为 (1)试画图表示出树形选择排序(增序)过程的前三步。 (2)试说明树形选择排序的基本思想。 (3)树形选择排序与直接选择排序相比较，优缺点是什么？ (4)堆排序是如何改进树形排序方法的？优点是什么？
第 6 页 共 53 页
考研专业课模拟试题
18． 假设以链式存储结构表示串。 设计一个将串 t 插入到串 s 中某个字符 c(第一次出现)之前的算法(若串 s 中不存在此字符，则将串 t 连接在串 s 的末尾)。要求算法的空间复杂度为 O(1)。 【答案】假设串用带头节点的单链表存储串 s。先找到 t 的尾节点 ，再在串 s 中查找字符 c， 由 p 指向该节点，pre 指向其前驱节点。若节点 存在，将 t 插入到 和 节点之间，否则，将 t 插入到 节点之后。对应的算法如下。
第 21 页 共 53 页
考研专业课模拟试题 2027 年中国航空研究院(601 所)082501 飞行器设计《802 数据结构》考研冲刺模拟五套题及参考答案 （四） 一、单项选择题 1． 广义表 ，则表尾为__。 A.空表 B.a C.（ ） D.(a) 【答案】D 【解析】 2． 下列关于无向连通图特征的叙述中，正确的是__。 I.所有顶点的度之和为偶数 II.边数大于顶点个数减 1 III.至少有一个顶点的度为 1 A.只有 I B.只有 II C.I 和 II D.I 和 III 【答案】A 【解析】在无向图中，一条边在度之和中计为 2,所以度之和为边数的 2 倍，I 正确。无向连通图边数 最少时为树图的情况，此时边数为顶点个数减 1，II 错误。一个顶点数为 3,边数为 3 的无向连通图中所有 顶点度为 2,III 错误。 3． 以上答案都不对 【答案】D 4． 下面说法错误的是__。 (1)算法原地工作的含义是指不需要任何额外的辅助空间； (2)在相同的规模n下，复杂度 的算法在时间上总是优于复杂度 的算法； (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界； (4)同一个算法，实现语言的级别越高，执行效率就越低。 A.(l) B.(l)、(2) C.(l)、(4) D.(3) 【答案】C 5． 分别以下列序列构造二叉排序树，与众不同的是__。 A. B. 掌к心博阅Р电子书 C. D. 【答案】A 【解析】b、c、d 三项中构成的二叉排序树都是平衡二叉树也是完全二叉树
第 36 页 共 53 页
考研专业课模拟试题
21．下面的算法将一个带头结点的单链表 la 分解为两个链表 la，lb,使得 la 表中含有原表中的奇数项的结 点，而 lb 表中含有偶数项的结点，且保持结点间原有的相对顺序。
【答案】(1) (2) (3) (4) 22．已知 Ackermann 函数定义如下：
(1)写出 (2)写出计算 【答案】(1)
的计算过程。 的非递归算法。
的计算过程：
第 51 页 共 53 页
试读已结束 激活后可查看剩余未读页数！
考研找高分直系学长学姐，请点个链接：⎝⎛联系高分学长⎞⎠
