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

《上海大学数据结构考研试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海大学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、2分）组成循环链表的可利用空间表当附加了条件（A）和（B）时，首次拟合法即为最佳拟合法。2、（2分）二进制地址为0，大小为（4）10和（16）10块的伙伴地址分别为：（C）、（D）。3、（8分）假设利用边界标识法，并已首次拟合策略分配，已知在某个时刻可利用空间表的状态如图1所示：pav802213462604012205301170560000图1：可利用空间表的状态图（注：存储块头部size域的值和申请分配的存储量均包括头部和尾部的存储空间。）请画出：（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；（2）

3、系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。三、（10分）请写出应填入下列叙述中（）内的正确答案。某一工程作业的网络图如图2所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。101148307

4、926512322745434753316图2：工程作业的网络图四、（10分）按下列要求构造二叉数。1、（4分）已知一棵二叉树的前序序列为ABDEGCF，中序序列为DBGEACF，请写出该二叉树后序序列。2、（6分）设数据集合D={1，12，5，8，3，10，7，13，9}，1）依次取D中的数据构造一棵二叉树AVL；2）如何依据此平衡二叉树AVL得到D的一个有序序列；3）画出在AVL中删除“5”后的平衡二叉树。五、（10分）阅读下列说明和流程图（图3）。①—⑤在该图中处填入合适的字句，使之成为完整的流程图[说明]流程图（图3）用来

5、求满足下列条件的最小自然数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的最

6、大整数.六、（30分）完善下列程序，每小题在PASCAL语言（A）和C语言（B）中任选一题。若都做，按（A）记分，每小题10分。1、下面的程序将数列1、2、3…….n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即：(a)算法的PASCAL语言程序描述：PROGRAMEX1（INPUT，OUTPUT）；CONSTNMAX=10；VARA：ARRAY[1N..jMAX，1N..MAX]OFINTEGERBEGINREADLN(N);M:=1;FORK:=1TO（1）DOBEGINIFK

7、）FORP:=1TOQDOBEGINIF（3）THENBEGINI:=Q-P+1;J:=P;END;ELSEBEGINI:=P;J:=Q-P+1;END;IF（4）THENBEGINI:=I+N-Q;J:=J+N-Q;END;A[I,J]:=N;（5）END;END;FORI:=1TONDOBEGINFORJ:=1TONDOWRITE([I][j]:4);writelnEND;END;(a)算法的C语言程序描述：#DEFINENMAX10#INCLUDE“STDIO.H”MAIN(){INTI,J,N,K,P,Q,M;INTA[N

8、MAX][NMAX];SCANF(“%D”,&N);M=1;FOR(K=1；（1）；K++);{IF（K〈N〉Q=K；ELSE（2）FOR（P=1；P〈=Q；P++〉{IF（3）{I=Q-P+1；J=P；}ELSE{I=P；J=Q-P+1；}IF（