2018年北京市培养单位空间应用工程与技术中心408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 试编写一算法对二叉树按前序线索化。
【答案】算法如下:
设置前驱
对以线索链表为存储结构的二叉树BT 进行前序线索化
设置左线索
设置前驱的右线索
为建立右链做准备
前驱后移
左子树前序线索化
右子树前序线索化
结束
2． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。
【答案】算法如下:
判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论
中序遍历左子树
中序遍历的第一个结点不必判断
前驱指针指向当前结点
不是完全二叉树
中序遍历右子树
算法结束
判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回
false
若左右子树均为二叉
排序树
左子树中的最大值和右子树中
的最小值
不是二叉排序树
结束
求二叉树左子树的最大值
返回机器最小整数
求二叉树右子树的最小值
返回机器最大整数
3． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
4． 设记录
的关键字为
。
算法
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
5． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中，删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)