2018年北京市培养单位遗传与发育生物学研究所864程序设计之数据结构考研核心题库
● 摘要
一、算法设计题
1． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
2． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数
，按" 蛇形M 填入n 阶方阵A 中
//i，j 是矩阵元素的下标，k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ，j 坐标
//副对角线以下的新的i ，j 坐标
//从左下向右上
//最外层
while
3． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
4． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
5． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
二、应用题
6． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示:
相关内容
相关标签