上海大学数据结构考研试题.doc

上海大学2002数据结构考研试题
一、(8分)请写出应填入下列叙述中()内的正确答案。
排序有各种各样的方法,如插入排序、快速排序、堆排序等。设一数组中原有数据如下:15,13,20,18,12,60下面是一组有不同排序方法进行一遍排序后的结果。
( )排序的结果为:12,13,15,18,20,60
( )排序的结果为:13,15,18,12,20,60
( )排序的结果为:13,15,20,18,12,60
( )排序的结果为:12,13,20,18,15,60
二、(12分)请写出应填入下列问题1和2的叙述中()内的正确答案,并解答问题3。
1、(2分)组成循环链表的可利用空间表当附加了条件(A)和(B)时,首次拟合法即为最佳拟合法。
2、(2分)二进制地址为0**********,大小为(4)10和(16)10块的伙伴地址分别为:(C)、(D)。
3、(8分)假设利用边界标识法,并已首次拟合策略分配,已知在某个时刻可利用空间表的状态如图1所示:
pav
802 213 462 604
0 122
0 53
0 117
0 56
0
0
0
0

图1:可利用空间表的状态图
(注:存储块头部size域的值和申请分配的存储量均包括头部和尾部的存储空间。)
请画出:
当系统回收一个起始地址为559,大小为45的空闲块之后的链表状态;
系统继而在接受存储块大小为100的请求后,又回收一个起始地址为515,大小为44的空闲块之后的链表状态。
三、(10分)请写出应填入下列叙述中()内的正确答案。
某一工程作业的网络图如图2所示,其中箭头表示作业,箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件,圆圈中的数字表示事件的编号。用事件编号的序列(例如0-2-7-9-11)表示进行作业的路径。
完成此工程的关键路径是(A)完成此工程所需的最少天数为(B)天,此工程中具有最大充裕天数的事件是(C),充裕天数是(D)。关键路径上的事件的充裕天数是(E)。

10
11
4
8
3
0
7
9
2
6
5
1
2 3 2

2 7 4
5
4 3 4 7
5 3
3 1
6

图2: 工程作业的网络图
四、(10分)按下列要求构造二叉数。
1、(4分)已知一棵二叉树的前序序列为ABDEGCF,中序序列为DBGEACF,请写出该二叉树后序序列。
2、(6分)设数据集合D={1,12,5,8,3,10,7,13,9},
依次取D中的数据构造一棵二叉树AVL;
如何依据此平衡二叉树AVL得到D的一个有序序列;
画出在AVL中删除“5”后的平衡二叉树。
五、(10分)阅读下列说明和流程图(图3)。①—⑤在该图中处填入合适的字句,使之成为完整的流程图
[说明] 流程图(图3)用来求满足下列条件的最小自然数N:对于两个给定的素数X、Y,从N开始的每个自然数都能表示成X的倍数和Y的倍数之和,即表示成m1*X+m2*Y,其中m1,m2均为自然数。
(图在后面)
寻找N的过程如下:首先取X和Y中的较小者为K,然后从X+Y开始逐个检查每个自然数,看它是否能表示成X的倍数和Y的倍数之和,一旦找到K个连续的自然数都符合