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

上海大学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分）二进制地址为011011110000，大小为（4）10和（16）10块的伙伴地址分别为：（C）、

（D）。

3、（8分）假设利用边界标识法，并已首次拟合策略分配，已知在某个时刻可利用空间表的状态如图1所示：

pav802

pav

802

213

462

604

0 56

0 117

0 53

0 122

0

0

0

0

（注：存储块头部size域的值和申请分配的存储量均包括头部和尾部的存储空间。）请画出：

当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。

三、（10分）请写出应填入下列叙述中（）内的正确答案。

某一工程作业的网络图如图2所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。2

1

3

5

2

0

2

2

7

6

4

5

4

3

4

3

7

9

7

5

3

3 1

11

4

8

10

6

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个连续的自然数都符合该条件，则这K个数中的第一个即为所求的N的值。

对每个数的检查方法：将该数看作U、V两数之和（即N=U+V），取U为X的倍数，然后检查V是否能被Y整除。

本题假设输入的X、Y是两个素数。图中表示└W┘不超过W的最大整数.

六、（30分）完善下列程序，每小题在PASCAL语言（A）和C语言（B）中任选一题。若都做，按（A）

记分，每小题10分。

1、下面的程序将数列1、2、3…….n*n依,

算法的PASCAL语言程序描述：

次按蛇型方式存放在二维数组A[1..n,1..n]中。即：

PROGRAM EX1（INPUT，OUTPUT）；CONST NMAX=10；

VAR

A：ARRAY[1N..jMAX，1N..MAX]OFINTEGERBEGIN

READLN(N); M:=1;

FOR K:=1 TO （ 1 ） DOBEGIN

IF KN THEN Q:=K

ELSE（

ELSE

（

2

FOR

P:=1

TO Q

DO

BEGIN

IF （ 3 ）THENBEGIN

I:=Q-P+1;J:=P;END;

ELSEBEGIN

I:=P;J:=Q-P+1;END;

IF （ 4 ）

BEGIN

I:=I+N-Q;J:=J+N-Q;END;

A[I,J]:=N;

（ 5 ）

END;

END;

FORI:=1 TO N DOBEGIN

FORJ:=1 TO N DO

WRITE