2017年南通大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？
（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，
成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公
，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
2． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。
（1）按次序构造一棵二叉排序树BS 。
（2）依此二叉排序树，如何得到一个从大到小的有序序列？
（3）画出在此二叉排序树中删除“66”后的树结构。
【答案】（1）构造的二叉排序树如图1所示：
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
图1 二叉排序树
（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
（3）如图2所示：
图2
3． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。
【答案】各种排序算法稳定性的归纳如图所示：
图
4． 某文件系统空间的最大容量为4TB 以磁盘块为基本分配单位，磁盘块大小为1KB 。文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。
【答案】
（1）文件系统存储空间共有块数可存放
（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：块号占6字节，块数占2字节的情形下，最大文件长度
：
理由：合理的起始块号和块数所占字节数分别为
块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。
5． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
6． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法