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

一、应用题

1． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：

造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较？

（3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

【答案】（1）哈希表示意图如表所示：

表 哈希示意图

（2）查找关键字63时，由于

63比较。

（3）查找关键字60时，由于

（4） 哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，为关键字，用线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）

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

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

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

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

C 函数：