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

一、应用题

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

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

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

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

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

成立。

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

2． 假定有下列，，所以结果不变，这就证明当i=n时公式仍成立。证毕。 矩阵（n 为奇数）

, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍

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

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

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

位在B 中的位置公式。

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

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

是

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

中存储的下标是

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

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

3． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。

（1）画出可利用空间表的初始状态。

（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

（3）画出在回收3个占用块之后可利用空间表的状态。

【答案】（1）因为可利用空间表的初始状态图如图1所示：

图1 可利用空间表的初始状态

（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，

故将

的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个

大小为

的块。又将其中大小为的一块挂到可利用空间表上，

另一块再分裂成两个大小为的

块。其中一块的块挂到可利用空间表上，

另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。

图2 每个用户得到的存储空间的起始地址

]

图3 可利用空间表的状态

（3）在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192，也在占用。回收大小为11的占用块时，其伙伴地址是48，可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示：

图4

4． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。

（1）试指出判别给定序列是否合法的一般规则；

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举