2018年清华大学计算机科学与技术系408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。
【答案】算法如下:
//采用三元组表方式存储，按列序实现矩阵的转置
//行数、列数和非零元素个数
//设置N 中第一个非零元素从下标1开始存储
//按列，共
//在//转置
//三元组表上实现矩阵的快速转置的算法
//矩阵M 每一列非零元初始化为零
//求矩阵M 每一列的非
零元个数
//第1列第一个非零元在转置后的三元组中下标是
1
//求
第j 列第一个非零元在
中的序号
列
个元素中查找
//求转置矩阵N 的三元组表
//同列下一非零元
素位置
2． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。
【答案】算法如下:
层次遍历二叉树，并统计度为1的结点的个数
统计度为1的结点的个数
是以二叉树结点指针为元素的队列
出队，访问结点
度为1的
结点
非空左子女入队
非空右子女入队
返回度为1的结点的个数
3． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
4． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。
【答案】算法如下:
//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表
//本算法将元素x 插入到线性表中，并保持线性表的有序性
//题目要求下标从1开始
//对分査找元素x 的插入位置
//元素后移
//将元素x 插人
算法结束
设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。
时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。
5． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。
【答案】算法如下::
打印从根结点bt 到结点p 之间路径上的所有结点
.
是元素为二叉树结点指针的栈，容量足够大
是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同
步
根结点就是所找结点
左子女入栈，并置标记
找到结点P , 栈中元素均为结点P 的祖先
从根结点到P 结点的路径为
沿左分支向下
本题不要求输出遍历序列，
这里只出栈
沿右分支向下
结束算法
为叶结点
从根结点到P 结点的路径为
输出从根到叶子q 的路径上的所有袓先
相关内容
相关标签