【冲刺】2027 年甘肃政法大学 085410 人工智能 《808 数据结构》考研冲刺模拟五套题及参考答案

考研专业课模拟试题 模拟试题简介 试题名称： 【冲刺】2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案 试题题型： 单项选择题+应用题+算法设计题 参考书目： 《数据结构(C 语言版)》严蔚敏 适用院系： （006）人工智能学院

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

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

第 2 页 共 56 页

考研专业课模拟试题 目录 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（一） .............4 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（二） ...........15 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（三） ...........26 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（四） ...........35 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（五） ...........46

第 3 页 共 56 页

考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年甘肃政法大学 085410 人工智能《808 数据结构》考研冲刺模拟五套题及参考答案（一） 一、单项选择题 1． 表长为 n 顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需 移动元素的平均个数为__，删除一个元素需要移动元素的平均个数为__。 A. B.n C.n+1 D.n-1 E. F. G. 【答案】E、A 【解析】在等概率的前提下，每插入一个元素所需移动的平均个数为： 删除一个元素所需移动元素的平均个数为：

2． 设 H 是带头结点的单循环链表的头指针，结点的指针域为 next，数据域为 data，则指针 p 指向链表 尾的条件是__。 A. B. C. D. 【答案】D 3． 设广义表 L=(a，b，c),则 L 的长度和深度分别为__。 A.1 和 1 掌㈄心博阅电子书 B.3 和 1 C.1 和 2 D.2 和 3 【答案】B 掌ㅎ心博阅电子书

第 4 页 共 56 页

考研专业课模拟试题 4． 如下图所示，在下面的 5 个序列中符合深度优先遍历的序列有__个。

图

A.5个 B.4个 C.3个青岛掌㈄心博阅电子书 D.2个 【答案】B 5． 在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是__。 A. B. C. D. 【答案】B 6． 下列数据中哪些是非线性结构__。掌㈄心博☼阅Ы电子书 A.栈 B.队列 C.完全二叉树 D.堆 【答案】C 【解析】根据堆的定义，堆是指 n 个元素的序列 一个堆。

，当且仅当满足下述关系时，称之为

堆可看成元素大小关系受限制的线性表，因此堆结构本身是线性结构，而堆排序是在完全二叉树的存 储结构上实现的。 7． 已知序列 25，13，10，12，9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过 程中元素之间进行的比较次数是__。掌ъ心博阅电子书 A.1 B.2 C.4 D.5 青岛掌р心博阅电子书 【答案】B 【解析】插入新元素 18 时，只须和它的所有祖先节点进行比较，它有两个祖先节点。本题答案为 B。

第 5 页 共 56 页

考研专业课模拟试题 8． 线性表是具有 n 个__的有限序列。掌й心博Т阅电子书 A.表元素 B.字符 C.数据元素 D.数据项 【答案】C 【解析】线性表是有限个数据元素的序列。 9． 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为__。

A. B. C. D. 【答案】A 【解析】基本算法是语句 答案为 A。

，设其执行时间为

，则有 ：

，即

。本题

二、应用题 10．设某文件经内部排序后获得初始廳串为 100 个。试问:掌ё心博阅电子书 (1)若要使多赂归并三趟完成排序，则应取归并的路数至少为多少? (2)若操作系统宴求一个程序賴雜可使用的 文件数不超过13个，则依多路归并法至少需几趟完成排 序？如果限定这个趟数，则可取的最低归并路数是多少？ 【答案】(1)当文件的初始归并段 个时，其k路归并的趟数s可由下式决定，即

现若限定归并趟数 ，则有 若取 ，则 ；取 ，则 。因此，至少取5路进行归并排序。 (2)若每次可取12路进行归并(因操作系统同时可用的 文件为13个，用12个文件作输入文件，1个作 输出文件)，则 归并排序至少需用2趟完成。如果限定这个趟数，设可取的归并路数至少为 所以可取的最低归并路数是10。 ，则由 得 ，

11．简述外部排序的基本过程和排序过程中的时间耗费。 【答案】外部排序基本上有两个相对独立的阶段组成。首先，按可用内存大小，将外存上含有 个记 录的文件分成若干长度为I的子文件或段(segment)，依次读入内存并利用有效的内部排序方法对它们进行 排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run);然后， 对这些归并段进行逐趟归并，使归并段(有序的子文件)逐渐由小到大，直至得到整个有序文件为止。 一般情况下，外部排序所需总的时间= 其中: 是为得到一个初始归并段进行内部排序所需时间的均值 ； 是进行一次外存读/写时间的均值 ； 是对 个记录进行内部归并所需的时间； 为经过内部排序之后得到的初始归并段的个数；s为归并的 趟数； 为总的读/写次数。

第 6 页 共 56 页

考研专业课模拟试题

对应的哈希表如表所示。

在等概率情况下查找成功的平均查找长度： 在等概率情况下查找不成功的平均查找长度： 。

。

三、算法设计题 16．设计一个算法，将含有 n 个元素的数组 A 的元素 循环右移 m 位。要求算法的空间复杂度为 。 【答案】先将数组 A 的后 m 位依次与前 m 位进行交换，这样后 m 位己循环移动到前面，如果 ， 结果即为所求，否则再将后 m 位通过交换移动到前 m 位之后(每个元素前移 n-2m 个位置)。对应算法如下。

第一个 while 循环执行 m 次，两重 for 循环执行 空间复杂度为 。

次(当

)，算法的时间复杂度为

，

第 21 页 共 56 页

考研专业课模拟试题 【解析】由于赫夫曼树中没有度为 1 的结点，所以结点的个数=度为 0 的结点数+度为 2 的结点数。根 据二叉树的性质 3,度为 2 的结点个数是度为 1 的结点个数-1， 所以可知一棵含 n 个叶子结点的赫夫曼树共 有 2n-1 个结点。 6． 下列程序段的时间复杂度是__。掌з心博阅电д子书

A. B. C. D. 【答案】C 7． 广义表 ，则表尾为__。 A.空表 B.a C.（ ） D.(a) 【答案】D 【解析】 8． 执行__操作时，需要使用队列做辅助存储空间。 A.查找散列(Hash)表 B.广度优先搜索图 C.先序(根)遍历二叉树 D.深度优先搜索图 【答案】B 【解析】查找散列表和先序遍历二叉树不需要用到额外的空间(辅助存储空间)；深度优先搜索图可以 利用递归的方法，使用栈，而不使用队列做辅助空间 ； 只有广度优先搜索图需要用到队列做辅助存储空间。 9． 两个栈 S1 和 S2 及一个输入序列 ABCD，每个输入元素只能选择其中一个栈入栈，则不可能的输出序 列为__。 A.ABCD; B.BADC; C.CABD;青岛掌ы心博➷⋛阅电子书 D.DABC; 【答案】 二、应用题 10．设某二叉树的前序遍历序列为：ABCDEFGHI,中序遍历序列为：BCAEDGHFI。 (1)试画出该二叉树。掌ю心博阅电┢子书 (2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。 (3)设具有 4 个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由 a，b,c，d 排列构成的字 符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出 具有 4 个结点二叉树的全部形态及相应的中序遍历序列。 【答案】(1)如下图所示 第 36 页 共 56 页

考研专业课模拟试题

♦

【答案】

【解析】根据题目所说，该程序完成了集合相减的功能，且集合以链表的形式表示。在链表中结点的 递增存储减小了该题的复杂性。给出了分情况的标准。所以很容易看出程序的结构。两个 while 的循环， 说明只需要处理两种情况。一种是 A 和 B 都不为空，另外一种是 A 不为空 B 为空的情况。所以 A 为 ，D 为 ，由典型的 结构，可 以很容易的推导出 B 为 ，C 为 。由整个程序的结构可知， E 为 last-〉link=NULL。 17．若仅需知道某数据量很大的序列中前 i 个最大或最小者，不要求完全排序，试给出一种较快速的解决 方法。 【答案】每次选取一个数据，并将序列调整为 ，根据数量需要考虑 可以对大于 j 的元素(或者小于 j 的元素)进行递归调用，直到正好某个元素的左右划分符合需要。算法描 述如下：

第 51 页 共 56 页

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