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

参考答案(A)

一、选择题（10小题，每题2分，共20分）

1. D 2. D 3. C 4. C 5. B 6. B 7. A 8. A 9. A 10. C

二、填空题（10小题，每题2分，共20分）

1. s->next=p->next; p->next=s; 2. (n-1)/2 3. 312 4. 2h-1 5. [log2i]=[log2j]

2

6. 深度 7. O(n) 8. k(k+1)/2 9. [log2i]+1 10.2

三、综合应用题（7小题，每题10分，共70分）

1.

根据完全二叉树的性质，A[i]的双亲是A[i/2]，双亲的双亲是A[i/2/2]，... 同理，A[j]的双亲是A[j/2]，双亲的双亲是A[j/2/2]，... if(i==j) A[i]和A[j]的最近的共同祖先就是A[i/2]; else

while(i!=j) { if(i>j) i=i/2; else j=j/2; } 2.

设总结点数为n，度为1和2的结点数分别为n1和n2 n=B+1=n0+n1+n2 n1=0 n2=n0-1 B=2n0-2 3.

（1）i

（1） 15627384 15627834 15672384 15672834 15678234 （2）

事件

最早发生时间Ve 最迟发生时间Vl

（3）

活动 最早开始时间e 最迟开始时间l

活动 最早开始时间e 最迟开始时间l

<1-2> 0 0 <6-2> 17 27

<1-5>0 5 <6-3>17 34

<1-4>0 5 <6-7>17 36

<2-3>30 30 <7-3>25 44

<3-4>50 50 <7-4>25 62

<5-2> 10 15 <7-8> 25 49

<5-6> 10 20 <8-4> 35 59

V10 0

V23030

V35050

V46565

V51015

V61727

V72544

V8 35 59

A[i]和A[j]的最近的共同祖先就是A[i];

（4）给出其关键路径: <1-2> <2-3> <3-4> 5.

（1）线性探测法

key num

1 4 1

2

3

4 491

5 382

6 131

7 242

8 321

9 21 2

10 10 3

等概率下查找成功时的平均查找长度ASL succ =(1+1+2+1+2+1+2+3)/8=13/8 等概率下查找失败时的平均查找长度ASL unsucc =(1+2+1+1+8+7+6+5+4+3+2)/11=40/11