2018年北京市培养单位光电研究院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。
【答案】算法如下:
判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论
中序遍历左子树
中序遍历的第一个结点不必判断
前驱指针指向当前结点
不是完全二叉树
中序遍历右子树
算法结束
判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回
false
若左右子树均为二叉
排序树
左子树中的最大值和右子树中
的最小值
不是二叉排序树
结束
求二叉树左子树的最大值
返回机器最小整数
求二叉树右子树的最小值
返回机器最大整数
2． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
3． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
。现要求将K n 放在将元素排序后
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
4． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。
【答案】算法如下:
在二叉树t 中査找结点值等于x 的结
点
结束
统计以t 为根结点的子树的叶结点数
n0
. 叶结点
输出并计数
结束
:
5． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
对存储在带头结点的双向链表head 中的元素进行双向起泡排序
设标记
双向链表尾，算法过程中是向上起泡的开始结点
是工作指针，指向当前结点
假定本趟无交换
向下(右) 起泡，一趟有一个最大元素沉底
交换两结点指针，涉及6条链
有交换
先将结点从链表上摘下
将temp 插到p 结点前
无交换，指针后移
准备向上起泡
向上(左) 起泡，一趟有一个最小元素冒
出
相关内容
相关标签