2018年同济大学电子与信息工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。
【答案】算法如下:
//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和
C
//为C 申请结点空间
//C初始化为空表
//P为工作指针
//B表初始化
//暂存P 的后继
//小于0的放入B 表
//将小于0的结点链人B 表
//P指向新的待处理结点
//算法结束
2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上，求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点，则转到根结点
根结点无双亲
找最右结点的过程中回找到
P
结束FFA
3． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
本句的有无不影响査找结果
4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
准备到左子树中找
P
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
访问根结点
找被访问结点的双亲
向右
结束
5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
求左子树表示的子表达式的值
求右子树表示的子表达式的值
二、应用题
6． 已知图的邻接矩阵为:
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出: (1)以顶点VI 为出发点的唯一的深度优先遍历序列； (2)以顶点VI 为出发点的唯一的广度优先遍历序列； (3)该图唯一的拓扑有序序列。 【答案】(1)(2)(3)