2018年第二军医大学基础医学部408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
2． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。
【答案】算法如下::
打印从根结点bt 到结点p 之间路径上的所有结点
.
是元素为二叉树结点指针的栈，容量足够大
是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同
步
根结点就是所找结点
左子女入栈，并置标记
找到结点P , 栈中元素均为结点P 的祖先
从根结点到P 结点的路径为
沿左分支向下
本题不要求输出遍历序列，
这里只出栈
沿右分支向下
结束算法
为叶结点
从根结点到P 结点的路径为
输出从根到叶子q 的路径上的所有袓先
3． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
对存储在带头结点的双向链表head 中的元素进行双向起泡排序
设标记
双向链表尾，算法过程中是向上起泡的开始结点
是工作指针，指向当前结点
假定本趟无交换
向下(右) 起泡，一趟有一个最大元素沉底
交换两结点指针，涉及6条链
有交换
先将结点从链表上摘下
将temp 插到p 结点前
无交换，指针后移
准备向上起泡
向上(左) 起泡，一趟有一个最小元素冒
出
交换两结点指针，涉及6条链
有交换
先将temp 结点从链表上摘
下
将temp 插到p 结点后(右
)
无交换，指针前移
准备向下起泡
算法结束
4． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。
【答案】算法如下:
//本算法将无符号十进制整数m 转换为十六进制整数
本算法的递归描述如下:
//本算法将无符号十进制整数m 转换为十六进制整数
相关内容
相关标签