2017年曲阜师范大学信息科学与工程学院858数据结构与操作系统之数据结构考研题库
● 摘要
一、算法设计题
1． 已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如：
第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：
1，4，7……第一个数组
9，12，28，29，45……第二个数组 【答案】算法如下：
2． 假设以I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（1）下面所示的序列中哪些是合法的？
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true , 否则返回false （假定被判定的操作序列已存入一维数组中）。
【答案】（1）A 和D 是合法序列，B 和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A 中，算法如下：
判断字符数组A 中的输入输出序列是否是合法序列。
为下标
3． 设从键盘输入一整数的序列：当
﹣1时，将入找；当【答案】算法如下：
4． 结点类型和存储结构如下：
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下：
试编写算法实现：用栈结构存储输入的整数，
时，输出栈顶整数并出找。算法应对异常情况（入栈满等）给出
相应的信息。
5． 试设计一个C 语言算法（或C 语言程序）：用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”（正向读和反向读时，串值相同的字，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如： 符串称为“回文”）
若输入若输入
是回文，则输出“Yes”； 不是回文，则输出“NO”。
要求：定义相关数据类型，不得使用数组（顺序表）做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。
【答案】算法如下：
6． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类复杂度为O 述所用结构。
【答案】算法如下：
语言编写时间
的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描
相关内容
相关标签