2018年北京市培养单位空间科学与应用研究中心408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
2． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
第 2 页，共 36 页
。现要求将K n 放在将元素排序后
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
3． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
4． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。
【答案】算法如下:
判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论
第 3 页，共 36 页
//
中序遍历左子树
中序遍历的第一个结点不必判断
前驱指针指向当前结点
不是完全二叉树
中序遍历右子树
算法结束
判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回
false
若左右子树均为二叉
排序树
左子树中的最大值和右子树中
的最小值
不是二叉排序树
结束
求二叉树左子树的最大值
返回机器最小整数
求二叉树右子树的最小值
返回机器最大整数
5． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
第 4 页，共 36 页
相关内容
相关标签