【冲刺】2027 年湖南工业大学 0812Z1 低空技术与 工程《813 数据结构》考研冲刺模拟五套题及参考 答案

考研专业课模拟试题 模拟试题简介 试题名称： 【冲刺】2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案 试题题型： 单项选择题+应用题+算法设计题 参考书目： 《数据结构》(C 语言版)，严蔚敏，吴伟民著，清华大学出版社 适用院系： （006）计算机与人工智能学院 （009）空天技术学院 （008）交通与电气工程学院

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

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

第 2 页 共 56 页

考研专业课模拟试题 目录 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（一） ..4 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（二） 16 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（三） 26 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（四） 38 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（五） 46

第 3 页 共 56 页

考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年湖南工业大学 0812Z1 低空技术与工程《813 数据结构》考研冲刺模拟五套题及参考答案（一） 一、单项选择题 1 ． 字符串 S 满足下式，其中 Head 和 Tail 的定义同广义表类似，如 S=__。 , A.abed B.acbd 掌м心博阅╋电子书 C.aedb D.adeb 【答案】D 【解析】单项选择题可用代入法求解，把答案一个个代入即可验证。 2． 若一棵哈夫曼树共有 9 个结点，则其叶子结点的个数为__。 A.4 B.5 C.6 D.7 【答案】B 3． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟 排序结束时都至少能够确定一个元素最终位置的方法是__。 Ⅰ.简单选择排序 Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排序 Ⅴ.二路归并排序 A.仅Ⅰ、Ⅲ、Ⅳ B.仅Ⅰ、Ⅲ、Ⅴ C.仅Ⅱ、Ⅲ、Ⅳ D.仅Ⅲ、Ⅳ、Ⅴ 【答案】A 【解析】凡是每趟产生的有序区为全局有序区的排序方法，则每一趟排序结束时都至少能够确定一个 元素的最终位置，这样的排序方法有简单选择排序和堆排序，快速排序尽管不是每趟产生有序区，但它也 将基准元素放到最终位置上。本题答案为 A。 4． 一棵完全二叉树上有 768 个节点，则该二叉树中叶子节点的个数是__。 A.257 B.258 C.384 D.385 【答案】C 【解析】对于完全二叉树，n=768 为偶数，所以 m=l，而 ，即有： 题答案为 C

，

，则

。本

第 4 页 共 56 页

考研专业课模拟试题 5． 下列选项中，不可能是快速排序第二趟排序结果的是__ A. B. C. D. 【答案】C 【解析】快排的阶段性排序结果的特点是:第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现 的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在 2 个这 样的数的选项。A 选项中 2、3、6、7、9 均符合，所以 A 排除；B 选项中，2、9 均符合，所以 B 排除;D 选 项中 5、9 均符合，所以 D 选项排除；最后看 C 选项，只有 9 一个数符合，所以 C 不可能是快速排序第二 趟的结果。 6 ． 若无向图 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是 __。 A.6 B.15 C.16 D.21 【答案】C 【解析】(1)若题目改为无向图 中含有 7 个顶点，则保证连通的的最少边数是 6,比较容易。 (2)本题要求保证图 G 在任何情况下均连通。所以要考虑最坏的情况，即图中的边分布极端不均匀。 比如其中有 6 个结点是两两连接(无向完全图，含 6×(6-1)/2=15 条边)，为确保第 7 个顶点也连通，且边 数最少，需要增加一条边，共 16 条，如图所示。

图 7． 若一棵二叉树的前序遍历序列为 ，后序遍历序列为 ，则根节点的孩子节点 __。 A.只有 e B.有 e、b C.有 e、c D.无法确定 【答案】A 【解析】根节点一定是 a，e 一定是 a 的孩子，因为先序序列中 e 刚好在 a 的后面且后序序列中 e 刚 好在 a 的前面，这样可以判断选项 D 错误。如果 b 或 c 是 a 的孩子，那一定是右孩子，在后序序列中 a 的 右孩子刚好出现在 a 的前面，与题中的后序序列不符，所以 a 只有一个孩子 e。本题答案为 A。

第 5 页 共 56 页

考研专业课模拟试题 8． 对一组数据( )进行排序，前 3 趟的排序结果如下。

则所采用的排序方法是__。 A.简单选择排序 B.希尔排序 C.二路归并排序 D.快速排序 【答案】D 【解析】考虑简单选择排序，其第 1 趟应将 84 与 20 交换(递增排序且每趟归位最大元素)，其他元素 位置不变，显然本题的排序过程不是这样做的。考虑希尔排序，元素个数 ， ，分为 4 组，25、 15、20 为一组，将其排序，第 1 趟的结果应为 显然本题的排序过程不是这样做的。 考虑二路归并排序，第 1 趟的结果应为 显然本题的排序过程不是这样做的。考虑快速排序， 第 1 趟将第一个元素 25 归位， 第 2 趟将 中元素 20 归位， 中元素 35 归位， 所以可 以推导出采用的是快速排序方法。本题答案为 D。 9． 链表不具有的特点是__。 A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 【答案】B 【解析】链表不能随机访问任一元素，必须从头结点开始通过指针域 next 逐个访问，直至到达指定 元素。 二、应用题 10．以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。

【答案】(1)第一个循环体…处应是赋值语句: (2)printf 的…处应该输出倒序的字符串: (3)函数类型是 void,不应有返回值，要删除

； ；

11．现有一文件 F 含有 1000 个记录，其中只有少量记录次序不对，且它们距离正确位置不远；如果以比 较和移动次数作为度量，那么将其排序最好采用什么方法？为什么？ 【答案】采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于少量 次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接插入排序算法。

第 6 页 共 56 页

考研专业课模拟试题

(1)阅读此算法，说明它的功能。 (2)对于下面给出的整数数组，追踪第一趟 内的 for 循环结束时数组中数据的变化(为清楚 起见，本次循环未涉及的不移动的数据可不写出，每行仅写出一个 for 循环的变化)。 (3)以上各次循环的数据移动次数分别是多少？ 【答案】(1)此算法为 Shell 排序算法。 (2)、(3)A 中数据的变化以及移动次数如表所示。

表 15．简述直接插入排序、简单选择排序和 2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的 差别。 【答案】直接插入排序的基本思想是在插入第 i 个记录时， 已经排好序。这时将关 键字 依次与关键字 进行比较，从而找到应该插入的位置，然后将 插入，原位置上的记 录向后顺推。直接插入排序是稳定的排序方法，其时间复杂度为 。掌ы心博阅电子书 选择排序的基本思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列 的最后，直至全部记录排完为止。也就是说每一趟在 个记录中选取关键字最小的记 录作为有序表中的第 i 个记录。选择排序是不稳定的排序方法，其时间复杂度为 。 2-路归并排序：归并是将两个或两个以上的有序文件合并成一个新的有序文件。利用归并的思想来进 行 2-路归并排序是将一个 n 个记录的无序文件看成是由 n 个长度为 1 的有序子文件组成的文件， 然后进行 两两归并，得到 个长度为 2 或 1 的有序子文件，再两两归并……如此重复，直至最后形成包含 n 个记 。

录的有序文件为止。2-路归并排序是稳定的排序方法，其时间复杂度为 三、算法设计题

第 21 页 共 56 页

考研专业课模拟试题

22．假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法，判别表达式中 括号是否正确配对。掌г心博阅┚电子书 【答案】算法如下：

23．假设以链式结构存储一个串 s。设计一个算法判断给定串是否具有对称性，并要求算法的时间复杂度 为 O(n),其中 n 为串 s 的长度。 【答案】假设串用带头节点的单链表存储串 s,用不带头节点的单链表表示链栈。先将 s 的所有节点复 制后进栈，然后依次比较字符是否相等，若都相等，则 s 具有对称性，否则不具有对称性。对应的算法如 下。

第 36 页 共 56 页

考研专业课模拟试题

所以，关键活动为 0、2、3、5,关键路径如图所示，长度 13。

图 三、算法设计题 16．设有一组关键字 ，采用散列函数 H ，采用 开放地址法的线性探测再散列方法解决冲突，试在 0〜18 的散列地址空间中对该关键字序列构造散列表。 【答案】根据题意，m=19,线性探测解决冲突的下一地址计算公式为 具体计算如下：

因此，各关键的记录对应的哈希表分配如下：

第 51 页 共 56 页

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