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

一、算法设计题

1． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

2． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

3． 已知关键字序列(

试写出一算法将(

利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:

''

假设

是大堆，本算法把

(2)

4． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。

【答案】算法如下:

//设工作指针pa 和pb ；

//结果表中当前合并结点的前驱的指针

//交集并入结果表中

//释放结点空

间

//释放结点空间

//释放结点空间

//置链表尾标记

//注:本算法中也可对B 表不作释放空间的处理

5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下:

以后序遍历算法求以二叉树表示的算术表达式的

) 是大根堆。

) 调整为大根堆；

调成大堆

值

.

求左子树表示的子表达式的值

求右子树表示的子表达式的值

二、应用题

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

(1)画出可利用空间表的初始状态。

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

(3)画出在回收3个占用块之后可利用空间表的状态。 【答案】(1)因为

，可利用空间表的初始状态图如图1所示:

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

(2)当用户申请大小为23的内存块时，因

9

8

7

7

，但没有大小为2的块，只有大小为2的

5

9

6

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

6

5

的块。其中一块2的块挂到可利用空间表上，另一块分裂成两个大小为2的块，其中一块挂到可利用空间表上，另一块分给用户(地址0〜31) 。如此下去，最后每个用户得到的存储空间的起始地

址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。