【冲刺】2027 年湖南工业大学 081200 计算机科学 与技术《813 数据结构》考研冲刺模拟五套题及参 考答案

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

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

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

第 2 页 共 60 页

考研专业课模拟试题 目录 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（一） .........................................................................................................................................................................4 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（二） .......................................................................................................................................................................15 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（三） .......................................................................................................................................................................25 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（四） .......................................................................................................................................................................37 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（五） .......................................................................................................................................................................50

第 3 页 共 60 页

考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年湖南工业大学 081200 计算机科学与技术《813 数据结构》考研冲刺模拟五套题及参考答案（一） 一、单项选择题 1． 一个栈的入栈序列为 A，B，C，D，E，则栈的不可能出栈序列是__。 A.ABCDE B.EDCBA C.DECBA D.DCEAB 【答案】D 2． 顺序查找法适合于存储结构为__的线性表。掌ㅕ心博阅⊱电子书 A.散列存储 B.顺序存储或链式存储 C.压缩存储青岛掌ㅠ心博╕阅电子书 D.索引存储 【答案】B 【解析】所谓顺序查找，指从第一个元素开始，依次遍历每个元素，直到找到目的元素为止。对于存 储结构没有要求。 3． 下面关于 B_树和 B+树的叙述中，不正确的结论是__。 A.B_树和B+树都能有效地支持顺序查找； B.B_树和B+树都能有效地支持随机查找； C.B_树和B+树都是平衡的多分树； D.B_树和B+树都可用于文件索引结构。 【答案】A 4． 存放在外存中的数据的组织结构是__。 A.数组 B.表 C.文件 D.链表 【答案】C 5． 设二叉树中有 个度为 2 的结点， 个度为 1 的结点， 个度为 0 的结点，则该二叉树中空指针个数 为__。 A. B. 掌й心博阅Ы电子书 C. D. 【答案】D 【解析】每个度为 1 的结点有 1 个空指针，每个度为 0 的结点有 2 个空指针，度为 2 的结点没有空指 针。

第 4 页 共 60 页

考研专业课模拟试题 6． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是__。 A.直接插入排序 B.起泡排序 C.简单选择排序掌ㅎ心博阅电子书 【答案】A 【解析】对直接插入排序而言，其算时间复杂度为 ，但若待排记录序列为“正序”时，其时间 复杂度可提高至 。若待排记录序列按关键字“基本有序” ，即序列中具有下列特性 的记录较少时，直接插入排序的效率就可大大提高，从另一方面来看，由于直接 插入排序算法简单，则在 n 值很小时效率也较高。 7．在一个具有 n 个节点的有序单链表中插入一个新节点使得仍然有序， 其算法的时间复杂度为__。 A. B. C. D. 【答案】D 8． 判定一个循环队列 Q(存放元素位置为 ，front 为队头指针指向队头元素的前一位置，

rear 为队尾指针指向队尾元素)队满的条件是__。掌㈄心博┲阅电子书 A. B. C. D. 【答案】C

青岛掌ш心博阅电子书

9． 需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是__ A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 【答案】B 二、应用题 10．斐波那契数列 定义如下：掌ㅐ心博阅电子书

请就此斐波那契数列，回答下列问题： ①在递归计算 的时候，需要对较小的 精确计算多少次？ ②若干有关大 O 表示法，试给出递归计算 时递归函数的时间复杂度是多少？ 【答案】①当 n=2 时， 计算 1 次， 计算 1 次。 时，有如下命题： 的计算次数为 计算次数 = 计算次数。以下用数学归纳法来证明。 当 n=3 时， 计算 1 次， 计算 2 次， 计算 1 次，满足。 当 n－4 时， 计算 1 次， 计算 2 次， 计算 3 次， 计算 2 次，满足。 第 5 页 共 60 页

考研专业课模拟试题 假设 时， 当 n＝k+1 时， 故 计算一次， 综上，命题成立。 ②设 的计算时间为 的计算次数为 的计算次数为 ，则有 ，所以时间复杂 计算次数 计算次数。

，故满足。

通过画出该函数的递归树，我们可以发现，该递归树的高度约为 n，结点总数为 度为 。

11 ． 有一个文件 ，请为 F 组织散列表。 散列函数以除留余数法求得，发生冲突时，以开放定地址法中的二次探测再散列解决，设可用于建表的地 址空间为 18 个单元，起始地址的相对地址为零。请设计该表成功查找的平均查找长度。 【答案】因地址空间数 m ＝ 18, 因此，应该选择最接近于 m 的一个素数 17 作为除数，即 ，则 。

各个数的比较次数计算如下：掌ㅜ心博え阅电子书 ，比较 1 次。 ，比较 1 次。 ，比较 1 次。 ，比较 1 次。 ，比较 1 次。 ,冲突； ，比较 2 次。 ，冲突； ，冲突； ，比较 1 次。青岛掌щ心博阅电子书 ,冲突； ，冲突； ,冲突； ，冲突； ，比较 4 次。 ，比较 1 次。 ,冲突； ，比较 2 次。 ，冲突； ，比较 2 次。 ，比较 1 次。 平均查找长度计算如下：青岛掌ъ心博♩阅电子书

，比较 3 次。 ，比较 3 次。 ，冲突；

12．模式匹配算法是在主串中快速寻找模式的一种有效的方法。如果设主串的长度为 m,模式的长度为 n， 则在主串中寻找模式的 KMP 算法的时间复杂度是多少？如果某一模式 ，请给出它的 next 函数值及 next 函数的修正值 nextval 之值。 【答案】KMP 算法的时间复杂度为 。 模式 的 next 函数值及 next 函数的修正值 nextval 之值如下表所示:

第 6 页 共 60 页

考研专业课模拟试题

18．已知一个递增有序表 ，并且表中没有关键字相同的记录。按如下方法查找一个关键字为 k 的 记录：先在编号为 4,8,12,…，4n 的记录中进行顺序查找，或者查找成功，或者由此确定一个继续进行折 半查找的范围。 (1)设计满足上述过程的查找算法。 (2)分析成功查找情况下的平均查找长度，和对整个表进行折半查找相比哪个算法较好？ (3)为了提高效率，对本算法可以做何改进。 【答案】(1)先在编号为 4，8，12,…，4n 的记录中进行顺序查找，若没有找到，找到大于 k 的位置 i,然后在 的范围内进行折半查找。对应的算法如下。

(2)在成功查找情况下，顺序查找中平均关键字比较次数为 ，然后在 3 个元素的范围内进行折 半查找，其平均关键字比较次数为 ，所以总的平均查找长度为 。若对整个表进 行折半查找，平均查找长度为 ，显然折半查找更好些。 (3)对本算法可做这样的改进：由于编号为 4，8，12,…，4n 的记录是递增有序的，可以将顺序查找 改为折半查找，然后在确定范围内再进行折半查找。

第 21 页 共 60 页

考研专业课模拟试题

第 36 页 共 60 页

考研专业课模拟试题 【答案】D 【解析】C 语言中对字符串(常量)的定义是:用一对双引号括起来的字符序列。字符串的子串当然也必 须符合这个定义。 7． 对有 3600 个记录的索引顺序表进行查找，最理想的块长是__。 A.1800 B.60 C.1200 D.1000 【答案】B 【解析】索引顺序表的查找方式为先按顺序来查找块，然后按顺序在块中查找，设块长为 k，则平均 查找长度为 ，对其求导，得到最佳的 k 值为 ，题目中 n=3600,所以，最佳的 为 60。 8． 求字符串 T 在字符串 S 中首次出现的位置的操作称为__。 A.求串的长度 B.求子串 C.串的模式四配 D.串的连接 【答案】C 【解析】 子串的定位操作通常称为串的模式匹配， 即求字符串 T 在字符串 S 中首次出现的位置的操作。 9． 用直接插入排序对下面 4 个序列进行递增排序，元素比较次数最少的是__。 A. B. 掌ё心博阅❤电子书

C. D. 【答案】C 【解析】 对于要排序的数序， 从第 2 个元素开始统计每个元素前面有多少个大于它的元素， 将其累加， 该累加值越大时采用直接插入排序时需要的元素比较次数越多，反之越少。选项 A 对应的累加值为 17,选 项 B 对应的累加值为 5,选项 C 对应的累加值为 2,选项 D 对应的累加值为 18。本题答案为 C。 二、应用题 10．求出图中 AOE 网中的关键路径(要求给出每个顶点的最早发生时间和最迟发生时间，并画出关键路 径 )。

【答案】见表。

第 51 页 共 60 页

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