2018年广西民族大学软件学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点
f
从结点c 的双亲结点直到根结点，
路径上所有结点均为祖先结点
逆序输出，最老的祖先最后输出
结束
2． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。
【答案】算法如下:
第 2 页，共 38 页
//采用三元组表方式存储，按列序实现矩阵的转置
//行数、列数和非零元素个数
//设置N 中第一个非零元素从下标1开始存储
//按列，共
//在//转置
//三元组表上实现矩阵的快速转置的算法
//矩阵M 每一列非零元初始化为零
//求矩阵M 每一列的非
零元个数
//第1列第一个非零元在转置后的三元组中下标是
1
//求
第j 列第一个非零元在
中的序号
列
个元素中查找
//求转置矩阵N 的三元组表
//同列下一非零元
素位置
3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
改造为
第 3 页，共 38 页
) 。
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
//暂存后继
//对称放置
//恢复待处理结点
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． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
第 4 页，共 38 页
相关内容
相关标签