2021年河南工业大学信息科学与工程学院830数据结构考研核心题库之算法设计题精编

特别说明

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

版权声明

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

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

重要提示

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

1．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

【答案】采用顺序存储结构求串s和串t的最大公共子串。串s用i指针。串t 用j指针。算法思想是对每个i(，即程序中第一个while循环)，来求i开始的连续字符串与从j(，即程序中第二个while循环)开始的连续字符串的最大匹配。程序中第三个(即最内层的)while循环，是当s中某字符与t中某字符相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为0),则最长公共子串的长度要修改。

(1)

(2)

(3)

(4)

(5)

2．(描述)假设函数

是结点类Node的成员函数，执行该函数后，p指向的链表中的结点变为:第一个结点是原来的倒数第一个结点，第二个结点是原来的倒数第二个结点……最后一个结点是原来的第一个结点。写出该函数，要求不改变链表占用的内存空间，且使用最少的临时变量。

【答案】

3．已知线性表中的元素以值递增有序排列，并以单链表作为存储结构。编写算法，删除表中所有值相同的元素，同时释放被删的结点空间。

【答案】程序如下。

4．自由树(即无环连通图)的直径是树中所有点对间最短路径长度的最大值，即T的直径定义为，这里表示顶点u到顶点v的最短路径长度(路径长度为路径中所含的边数)。试写一算法来求T的直径，并分析算法的时间复杂度(时间复杂度越小，得分越高) 【答案】求树的直径的时间复杂度可为，和。

解法一：先调用求所有点对间最短路径算法(每边权值为1)，如Floyd算法，然后对指代矩阵求最大的作为直径。

解法二：修改BFS算法，使之遍历时记录当前访问结点的深度(离根的边数)，用存在的度为1的结点作起点调用BFS,求出其它非根结点的深度，在各次调用BFS算法中求最大深度，即为树的直径。时间，这里是一次外部调用BFS的运行时间，调用BFS的最多次数(指外部调用)不超过(存储结构为邻接表时)。

解法三：用邻接表作为存储结构依次删去树叶(度为一的结点)，将与树叶相连的结点度数减1。设在第一轮删去原树T的所有树叶后，所得树为T1;再依次做第二轮删除，即删除所有T1的叶子；如此反复，若最后剩下一个结点，则树直径应为删除的轮数乘以2。具体算法描述如下：

5．设有一对刚出生的小兔子，假定两个月以后每个月便可繁殖雌雄各一的k对小兔子，请输出计算第n个月后兔子数目的递推公式，并写出计算F(n)的程序。

【答案】递推公式为：

C程序如下：