【冲刺】2027 年湖南工业大学 085400 电子信息 《813 数据结构》考研冲刺模拟五套题及参考答案

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

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

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

第 2 页 共 56 页

考研专业课模拟试题 目录 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（一） .............4 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（二） ...........14 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（三） ...........23 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（四） ...........33 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（五） ...........44

第 3 页 共 56 页

考研专业课模拟试题 2027 年考研专业课模拟试题-冲刺阶段使用 2027 年湖南工业大学 085400 电子信息《813 数据结构》考研冲刺模拟五套题及参考答案（一） 一、单项选择题 1． 下面关于树和二叉树的叙述中，正确的是__。 A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序 遍历结果序列的最后一个结点 B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序 遍历结果序列的最后一个结点 C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的 前序遍历结果序列的最后一个结点 D.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的 中序遍历结果序列的最后一个结点 【答案】C 【解析】因为中序遍历和前序遍历都是最后遍历右子树，所以，它们对应的遍历序列的最后一个结点 是一样的，且是树空间结构上最右边的一个结点。 2． 给定 n 个元素，逐个输入这些元素，建立一个有序单链表的时间复杂度是__。 A. B. 掌ㅏ心博阅く电子书

C. D. 【答案】C 【解析】对于有序单链表，最坏情况下需要遍历整个链表才能找到当前新结点需要插入的位置。也就 是说，第 1 个元素直接插入，第 2 个元素的比较次数为 1，第 3 个元素的比较次数为 2，以此类推，第 n 个元素的比较次数为 n-1，总共的比较次数为 。 3． 以下关于算法的说法正确的是__。 A.算法最终必须由计算机程序实现 B.算法等同于程序 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 【答案】D 【解析】算法最终不一定由计算机程序实现。算法具有有穷性，而程序不必具有有穷性。算法的确定 性是指指令不能有二义性。 4． 下面__算法可用于求无向图的所有连通分量。掌ъ心博阅电子书 A.广度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 【答案】A 【解析】从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了 该顶点所在的连通分量，因此广度优先遍历可以求出无线图的所有连通分量。

第 4 页 共 56 页

考研专业课模拟试题 5． 关于下面的程序段，不正确的说法是__。

A.其时间复杂性为 B.它将数组 A 中的正数放到数组 B 中，将负数放在数组 C 中 C.如果数组 A 中没有负数，程序执行后 D.如果数组 A 中没有正数，程序执行后 【答案】A 6． 在构造哈希表方面，下面的说法__是正确的。 A.再散列在处理冲突时不会产生“聚集” B.散列表的装载因子越大，说明空间利用率越好，因此应使装载因子尽量大 C.散列函数选得好可减少冲突现象 D.对于任何具体关键字都不可能找到不产生冲突的散列函数 【答案】C 7． 数据序列 只能是下列排序算法中的__进行两趟排序后的结果。 A.快速排序 B.冒泡排序 C.选择排序 D.插入排序 【答案】A 【解析】对于后三种排序方法，两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而 给定的序列不满足。 8． 对 个权值均不同的字符构成哈夫曼树，关于该树的叙述中，错误的是__。 A.该树一定是一棵完全二叉树掌й心博阅电子书 B.该树中一定没有度为 1 的节点 C.树中两个权值最小的节点一定是兄弟节点 D.树中任一非叶子节点的权值一定不小于下一层任一节点的权值 【答案】A 【解析】构成的哈夫曼树不一定是一棵完全二叉树。本题答案为 A。 9． 将 10 个元素散列到 100000 个单元的散列表中，则__产生冲突。 A.不可能 B.一定会 C.有可能 D.不知道 【答案】C 【解析】 散列函数的选取是一件很重要也很困难的事情。 理想的情况是散列函数值均匀列在散列表中， 最好别发生冲突。但是实际情况为冲突可以减少但很难避免。对于本题来说，如果选择了一个不合适的散 列函数，发生冲突的可能性也很大。

第 5 页 共 56 页

考研专业课模拟试题 二、应用题 10．二叉树中两个结点 m，n 的关系，如下表所示可能者打“√” 。

【答案】填表如下：

表 11．数组 以行为主序存储，设第一个元素的首地址是 78,每个元素的长度为 4，试求元素 的存储首地址。 【答案】元素 的存储首地址为 958。三维数组以行为主序存储，其元素地址公式为: 其中， 是各维的下界和上界， 是各维元素个数，L 是一个元素所占的存储单元数。

12．线性表的顺序存储结构具有三个弱点：其一，在做插入或删除操作时，需移动大量元素；其二，由于 难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线 性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 【答案】链式存储结构克服了顺序存储结构的三个弱点：首先，链式存储结构在进行插入和删除操作 时不需移动元素，只需要修改指针即可，其时间复杂度为 ； 其次，链式存储结构不需要预先分配空间， 可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。 13．下面给出一个算法，其中 n 是数组 A[]中元素总数。掌ш心博☺阅电子书

第 6 页 共 56 页

考研专业课模拟试题

22．可用一个数组 S(设大小为 MAX)作为两个堆栈的共享空间。请说明共享方法、栈满/栈空的判断条件， 并用 C 或 Pascal 语言设计公用的入栈操作 ，其中 为 0 或 1，用于表示桟号，x 为入栈值。 【答案】栈满条件为： (其中 表示低端栈栈顶， 表示高端栈栈顶)； 栈空条件为： (表示低端栈为空)， (表示高端栈为空)。 PUSH 函数为：

23．设将 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 个位置，即将 R 中的数据由 变换为 。要求：掌и心博阅电с子书 (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 或 Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 【答案】(1)算法的基本设计思想 ： 可以将这个问题看成是把数组 ab 转换成数组 ba(a 代表数组的前 p 个元素， b 代表数组中余下的 n-p 个元素)， 先将 a 逆置得到 ， 再将 b 逆置得到 ， 最后将整个 逆置得到 。 设 Reverse 函数执行将数组元素逆置的操作， 对 abcdefgh 向左循环移动 个位置的过程如下： 得到 cbadefgh。 得到 cbahgfed。 得到 defghabc。 (2)使用 C 语言描述算法如下：

第 21 页 共 56 页

考研专业课模拟试题 二、应用题 10．已知一个单链表中每个结点存放一个整数，并且结点数不少于 2,请设计算法以判断该链表中第二项起 的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回 true,否则返回 false。 【答案】判断结点的元素值是否等于其序号的平方减去其前驱的值，主要技术问题是结点的序号和前 驱及后继指针的正确指向。核心语句段如下：

11．对于右图所示的带权图，利用算法求出源点到其余各顶点的最短路径及其长度，并写出在算法执行过 程中，每求得一条最短路径后，当前从源点到其余各顶点的最短路径及其长度的变化情况。

【答案】对于这个图，在 Dijkstra 算法执行过程中，每求得一条从源点到某个顶点的最短路径后， 当前从到其余各顶点的最短路径及其长度的变化情况如下表所示：掌й心博阅♨电子书

因此，利用 Dijkstra 算法求得从 到其余各顶点的最终的最短短径及其长度分别为： 到 ：路径为 ，长度为 10; 到 ：路径为 ，长度为 12; 到 ：路径为 ，长度为 22; 到 ：路径为 ，长度为 29; 到 ：路径为 ，长度为 20。 12．已知广义表 ，运用求表头和表尾运算 head 和 tail 提取出 GL 中原子 e 的运算是什 么？ 【答案】取出 GL 中原子 e 的运算是 。计算过程如下:

掌и心博✌阅电子书

第 36 页 共 56 页

考研专业课模拟试题

19．某有向图如图所示，要求: (1)给出拓扑排序算法代码描述； (2)给出图的算法执行结果。

图 【答案】(1)拓扑排序的算法描述如下。

第 51 页 共 56 页

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