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

一、应用题

1． 写出下面算法中带标号语句的频度。

设k 的初值等于1。

【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。

（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。

（3）这是循环体语句，共执行了n 次，所以频度是n 。

，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）

一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。

（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。

（6）这是循环体语句，共执行了n －1次，所以频度是n －1。

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． 下面程序段的时间复杂度是什么？

【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。