2021年兰州理工大学计算机与通信学院892数据结构考研核心题库之算法设计题精编

特别说明

本书根据历年考研大纲要求并结合历年考研真题对该题型进行了整理编写，涵盖了这一考研科目该题型常考试题及重点试题并给出了参考答案，针对性强，考研复习首选资料。

版权声明

青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。

因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。

重要提示

本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。一、2021年兰州理工大学计算机与通信学院892数据结构考研核心题库之算法设计题精编

1．假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，loading和being的存储映像如下图所示。

图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为

设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度。

【答案】(1)顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想如下：

①分别求出str1和str2所指的两个链表的长度m和n；

②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若，则使p指向链表中的第m-n+1个结点；若，则使q指向链表中的第n－m＋1个结点，即使指针p和q所指的结点到表尾的长度相等；

③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，则该点即为所求的共同后缀的起始位置。

(2)算法的C语言代码描述：

(3)时间复杂度为或，其中len1、len2分别为两个链表的长度。

2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如下图所示，请写出相应的入队列和出队列算法。

图

【答案】入队列算法描述如下：

出队列算法描述如下：

3．请给出二叉树前序遍历的非递归算法。

【答案】二叉树前序遍历的递归算法如下：

将其转换成非递归算法如下：

4．遍历一棵二叉树的中序序列和后序序列分别为：中序BFDGAEHC，后序FGDBHECA，写出这棵二叉树的逻辑结构和存储结构。已知一棵二叉树的中序序列和后序序列分别由和数据存放，并且假定没有数据域值相同的结点，证明可由此生成一棵唯一的二叉树，

并写出生成的算法。

【答案】这棵二叉树的逻辑结构如下图1所示。存储结构如下图2所示。