2018年西安科技大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 试编写一算法对二叉树按前序线索化。
【答案】算法如下:
设置前驱
对以线索链表为存储结构的二叉树BT 进行前序线索化
设置左线索
设置前驱的右线索
为建立右链做准备
前驱后移
左子树前序线索化
右子树前序线索化
结束
2． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。
【答案】算法如下:
//采用三元组表方式存储，按列序实现矩阵的转置
//行数、列数和非零元素个数
//设置N 中第一个非零元素从下标1开始存储
//按列，共
//在//转置
第 2 页，共 40 页
列
个元素中查找
//三元组表上实现矩阵的快速转置的算法
//矩阵M 每一列非零元初始化为零
//求矩阵M 每一列的非
零元个数
//第1列第一个非零元在转置后的三元组中下标是
1
//求
第j 列第一个非零元在
中的序号
//求转置矩阵N 的三元组表
//同列下一非零元
素位置
3． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
访问根结点
找被访问结点的双亲
结束
第 3 页，共 40 页
向右
4． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下:
在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回
确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情
况
返回第一邻接点，
和
中必有一个等于
i
取第一个边结点
5． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。
【答案】算法如下::
打印从根结点bt 到结点p 之间路径上的所有结点
.
是元素为二叉树结点指针的栈，容量足够大
是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同
步
根结点就是所找结点
左子女入栈，并置标记
找到结点P , 栈中元素均为结点P 的祖先
从根结点到P 结点的路径为
沿左分支向下
本题不要求输出遍历序列，
这里只出栈
沿右分支向下
结束算法
为叶结点
从根结点到P 结点的路径为
输出从根到叶子q 的路径上的所有袓先
二、应用题
第 4 页，共 40 页