2018年辽宁省培养单位沈阳自动化研究所408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
2． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
第 2 页，共 36 页
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
；
3． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
4． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中，删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)
释放空间
沿链表继续査找
5． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
【答案】算法如下:
//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回
第 3 页，共 36 页
//在类C 中，一维数组下标从零开始
//两串相等
//算法结束
二、应用题
6． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除时间复杂度都是O(1)。 7． 已知有6个顶点(顶点编号为0--5) 的有向带权图G , 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。
要求:
(1)写出图G 的邻接矩阵A 。 (2)画出有向带权图G 。
(3)求图G 的关键路径, 并计算该关键路径的长度。
【答案】(1)由题可以画出待定上三角矩阵的结构图如下(图中？为待定元素) :
可以看出, 第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个, 由此可以画出压缩存储数组中的元素所属行的情况, 如下图所示:
将各元素填入各行即得邻接矩阵:
(2)根据第一步所得矩阵A 容易做出有向带权图G , 如下:
第 4 页，共 36 页