2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研导师圈点必考题汇编
● 摘要
一、算法设计题
1． 已知递增有序的单链表A , B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差，并以同样的形式存储，同时集A-B （即仅由在A 中出现而不在B 中出现的元素所构成的集合）返回该集合的元素个数。
【答案】算法如下：
2． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设
用
表示辅助地址表。初始时
非递减序）算法的语句序列。
【答案】算法如下：
在树中查找值为的结点，若找到，则记
表示n 个结点的值，
用
在排序中，凡需对结点交换就用它的地址来
进行。例如当n=3时，对K （31，11，19）则有T （2，3，1）。试编写实现辅助地址表排序（按
3． 已知二叉树丁的结点形式为
【答案】算法如下：
数（count ）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
4． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA （P ，q ）, 该算法寻找结点 P 的父亲结点q ，设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG , LLINK , INFO , RL1NK , RTAG ）, 且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下：
在中序线索树t 上，求结点p 的双亲结点q
{q=p; //暂存
//找P 的中序最右下的结点
//顺右线索找到q 的后继（P 的袓先结点）
//若后继是头结点，则转到根结点
根结点无双亲
}//找最右结点的过程中回找到
P
5． 设从键盘输入一整数的序列：当
﹣1时，将入找；当【答案】算法如下：
//准备到左子树中找
P
试编写算法实现：用栈结构存储输入的整数，
时，输出栈顶整数并出找。算法应对异常情况（入栈满等）给出
相应的信息。
6． 给定
矩阵并设
设计一算法判定x 的值是否在A 中，
要求时间复杂度为
【答案】算法如下：
7． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下：
和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作
成功返回1, 否则返回0表示失败