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

东南大学98考研题

一。简要回答下列问题。

1。设胜者树由k 各记录缓冲区和k-1个非叶结点构成，概念上非叶结点表示两个子女中观键字较小者，而实际上非叶结点存放的是什末？

2。索引顺序存储方法中，主文件已按关键字排序，为何还需要主关键字索引？

3。一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的中序序列为1，2，3，4，5，6，7，8，9。其中序序列为2，3，1，5，4，7，8，6，9，试画出该树。

4。构造最佳二叉检索树的条件是何？再动态情况下，一般 AVL树的查询性能不如完全二叉检索树的，为何人却采用AVL 树呢？

5．将两个栈存入数组V[1。。。m]应如何安排最好？这时栈空栈满的条件是何？

6。已知无向图G ，V （G ）={1，2，3，4}，E （G ）={（1，2），（1，3）（2，3），（2，4），（3，4）}试画出G 的邻接多表，并说明，若已知点i ，与和根据邻接多表找到与i 相临的点j ？

二。写出用堆排序算法对文件F=（12，3，15，30，9，28）进行排序是，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个重要区别。

三。设组A 存放一位二进制数，试说明下列算法X 的功能，假设无溢出，算法的X 最坏时间复杂性是何？分析她的平均时间复杂性。 （8分）

type Num-array[1..n] of [0..1];

procedure x (var a:num);

var i:integer;

begin

i:=n;

while A[i]=1 do

begin A[i]:=0; i:=i-1;

end; A[i]:=1;

end;

四。下面是一改进了的快速分类算法

1.procedure qsort1(var list:afile;m,n:integer);

2(设list[m].keky

3var i,j,k:integer;

4 begin

5 while m

6 begin

7 i:=m;j:=n+1; k:=list[m].key;

8 repeat

9 repeat i:=i+1 until list[i].key>=k;

10 repeat j:=j-1 until list[j].key<=k;

11 if i

12 until i>=j;

13 interchange( list[m],list[j]);

14 if n-j>=j-m

15 then begin qsort1(list.m.j+1);m:=j+1;end

16 else begin qsort1(list.j+1.n);n:=j-1;end

17 end;(of while)

18 end.

问： (共 20分)

1将第9.10行中的＞=，＜=分别改成＞＜行吗？为什么？ （5分）

2该排序算法稳定否，举例说明 （5分）

3 对输入文件（22，3，30，4，60，11，58，18，40，16）列表表示该文件再每次调用qsort1时的状态及相应m 〈n 值 （5分）

4若输入文件有n 个记录，简要说明支持qsort1递归所需最大栈空间用量设一曾递归用一个单位栈空间）。（5分）