2018年西南科技大学计算机科学与技术学院814程序综合设计之数据结构教程考研强化五套模拟题
● 摘要
一、算法设计题
1． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素
在C 中的存放位置下标的公式。
//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置
//算法结束
2． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
输入顶点信息
题目要求两顶点之一为0表示结束
第 2 页，共 31 页
和B 的
【答案】算法如下:
3． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
向右
访问根结点
找被访问结点的双亲
结束
4． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
第 3 页，共 31 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
5． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
b 中连续的相等元素构成的子序列称为平台。试设计算法，
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
6． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
在b 数组中起始下标为
”，1，
k)
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
7． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
第 4 页，共 31 页
相关内容
相关标签