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

一、应用题

1． 已知一个大小为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

2． 一个循环队列的数据结构描述如下：

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】（1）队空：

（2）队满：

这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。

3． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。

【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。

4． 阅读下列算法，指出算法A 的功能和时间复杂性。

【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。

时间复杂度：0（n ）。

5． 调用下列C 函数f （n ），回答下列问题：

（1）试指出f （n ）值的大小，并写出，f （n ）值的推导过程；

（2）假定n=5，试指出，f （5）值的大小和执行，f （5）时的输出结果。 C 函数：