2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题
● 摘要
目录
2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题（一） ... 2 2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题（二） ... 9 2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题（三） . 15 2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题（四） . 23 2018年北京市培养单位生命科学学院864程序设计之数据结构考研强化五套模拟题（五） . 29
一、算法设计题
1． 试编写一算法对二叉树按前序线索化。
【答案】算法如下:
设置前驱
对以线索链表为存储结构的二叉树BT 进行前序线索化
设置左线索
设置前驱的右线索
为建立右链做准备
前驱后移
左子树前序线索化
右子树前序线索化
结束
2． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
算法
) 区分在遍
3． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
访问根结点
找被访问结点的双亲
结束
4． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。
【答案】算法如下:
判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论
中序遍历左子树
中序遍历的第一个结点不必判断
向右
前驱指针指向当前结点
不是完全二叉树
中序遍历右子树
算法结束
判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回
false
若左右子树均为二叉
排序树
左子树中的最大值和右子树中
的最小值
不是二叉排序树
结束
求二叉树左子树的最大值
返回机器最小整数
求二叉树右子树的最小值
返回机器最大整数
5． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
二、应用题
相关内容
相关标签