2018年北京市培养单位遗传与发育生物学研究所864程序设计之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
2． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
3． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
4． 当一棵有n(
；
中时，试写一个算法，求
当前叶结点链入双链表
树中的所有叶结点链成带头结点的双链表
) 个结点的二叉树按顺序存储方式存储在
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
整型
，值是
设元素类型为
5． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
b 中连续的相等元素构成的子序列称为平台。试设计算法，
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
在b 数组中起始下标为
”，1，
k)
二、应用题
6． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】(1)动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为(k为大于等于0的正整数) 。若内存容量为
，则空闲块大小只能是
。由同一大块分裂而得的两个小块互称“伙伴空间”，
(
若
)
或
109
如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。
起始地址为P ，
大小为的内存块，其伙伴的起始地址为
:
(若
(2)和边界标识法的不同
) 。
边界标识法在每块的首尾均有“占用”/ “空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
7． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问:
当n=7时，在最好情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最好情况的初始排序的实例。 当n=7时，在最坏情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最坏情况的初始排序的实例。
【答案】(1)在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为以此类推，总共进行
的子文件，第二趟划分得到4个长度均为
，
的子文件，
(n+1)趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在
最好情况下，第一需比较6次，第二趟分别对两个子文件(长度均为3，k=2)进行排序，各需2次，
相关内容
相关标签