2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题
● 摘要
目录
2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题（一） .... 2 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题（二） .. 14 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题（三） .. 23 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题（四） .. 34 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化模拟题（五） .. 43
一、算法设计题
1． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下：
和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作
成功返回1, 否则返回0表示失败
2． 设单链表的表头指针为h , 结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc （h , n ）, 判断该链表的前n 个字符是否中心对称。例如xyx , xyyx 都是中心对称。
【答案】算法如下：
3． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture , 否则返回false 。
【答案】算法如下：
4． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“notfind ”信息。请编写出算法并简要说明算法思想。
【答案】算法如下：
5． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于算法的时间复杂度为
【答案】算法如下：
6． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下：
现要求将
的数据元素。要求你的
其中，2为排序树中所含结点数，m 为输出的关键字个数。
放在将元素排序后的
正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n （注：用程序实现）。
7． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，
将线性表
改造为
【答案】算法如下：