当前位置：问答库＞考研试题

一、应用题

1． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。

【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：

图1

（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：

图2

2． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？

（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。

（2）证明：当i=l时，

成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公

，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为

3． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的

是否总有a ≤b ≤c? 为什么？

【答案】该结论不成立。例如，本题中对于任一

f 的左子树上。对于从a 到根结点路径上的所有

均有a

4． 阅读下面的算法，说明算法实现的功能。

【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。 ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b , 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍的右子树上，这时a>b，因此a

5． 假定有下列，矩阵（n 为奇数）

如果用一维数组B 按行主次序存储A 的非零元素，问：

（1）A 中非零元素的行下标与列下标的关系；

（2）给出A 中非零元素的下标

位在B 中的位置公式。

【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有

所以A 中非零元素的行下标和列下标的关系是或 的关系，与B 中的下标R 的关系； 给出利用的下标定（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标

是

副对角线上的元素，在中心元素前，在向量B

中存储的下标是

在中心元素后，其下标如下：

（3）在B 中的位置如下：

6． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。

【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。