习题参考答案(7-8)

一 判断题 3V 4X 7V 二 选择题 1B 2A 4(1)B (2)D 三 填空题

1 0, n(n-1)/2, 0, n(n-1) 2 n(n-1)/2, n(n-1) 3 顶点 四 简答题

1 (1) ID(1)=2; ID(2)=2; ID(3)=1; ID(4)=3; ID(5)=2; ID(6)=1; OD(1)=1; OD(2)=2; OD(3)=3; OD(4)=0; OD(5)=3; OD(6)=2 (2) 邻接矩阵 (3)邻接表

序号 vertex firstedge

0 0 0 1 0 0 v1 0 3 Λ 1 0 1 0 0 0 v2 0 1 0 0 0 1 1 1 v3 3 4 2 0 0 0 0 0 0 3 v4 Λ 1 1 0 1 0 0 v5 0 1 4 0 1 0 0 1 0 5 v6 1 (4) 逆邻接表 序号 vertex firstedge

v1 1 0 4 Λ

v2 4 1 5 Λ

v3 2 1 Λ

v4 0 2 3 4 Λ

v5 2 4 5 Λ

5 v6 2 Λ

2 (1) 邻接矩阵 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 (2) 邻接表

序号 vertex firstedge 0 v0 1 2 Λ 1 v1 0 3 Λ 2 v2 0 3 Λ 3 v3 1 2 4 4 v4 3 6 Λ 5 v5 3 6 Λ 6 v6 4 5 Λ

(4) 从A出发的“深度优先”遍历序列： v0,v1,v3,v4,v6,v5,v2（解答不唯一） (5) 从A出发的“广度优先”遍历序列： v0,v1,v2,v3,v4,v5,v6（解答不唯一）

2 Λ 5 Λ 3 Λ 4 Λ 5 Λ 第8章习题参考答案

一 判断题 X V X V X V V X X X V V V V X X V X V V

9 二 选择题 B C C C D C C D B B 三 简答题 14 4 1 判定树如右图

11 6 2 16 查找成功的ASL＝(1+2*2+3*4+4*8+5*3)/18 = 64/18 = 32/9 查找失败时的最多关键字比较次数是5 10 12 1 3 5 15 17 7 （查找的关键字大于18）

Jan 8 13 18 2 (1)二叉排序树

Feb Mar

查找成功

Apr June May ASL＝(1+2*2+3*3+4*3+5*2+6*1)/12 =42/12 = 7/2

Aug July Sep

Dec Oct

Nov

（2）有序的二叉排序树形成一个单链表，每个节点是前一个节点的右子树

顺序为Apr Aug Dec Feb Jan July June Mar May Nov Oct Sep

查找成功ASL＝(1+2+3+4+5+6+7+8+9+10+11+12)/12=78/12 = 13/2

6 哈希函数为关键字首字母在字母表中的序号除2，H(key)=i/2; ( H(key)=(c-‘A’+1)/2 ) 所以有H(Jan)=5 H(Feb)=3 H(Mar)=6 H(Apr)=0 H(May)=6 H(June)=5

H(July)=5 H(Aug)=0 H(sep)=9 H(Oct)=7 H(Nov)=7 H(Dec)=2

(1) 用线性探测开放地址法处理冲突

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr 1 Aug 2 Dec 1 Feb 1 Jan 1 Mar 1 May 2 June 4 July 5 Sep 2 Oct 5 Nov 6 查找成功ASL＝(1*4+2*3+4*1+5*2+6*1)/12 = 5/2 不成功ASL=(5+4+3+2+1+9+8+7+6+5+4+3+2+1+1+1+1)/17=43/17 0 （2）用链地址法处理冲突

1 ^

2 查找成功

3 ASL＝(1*7+2*4+3*1)/12 = 4/3

不成功 4 ^ ASL＝(2+0+1+1+0+3+2+2+0+1+0)/17 = 12/17 5 7.哈希表如下：

6 0 1 2 3 4 5 6 7 8 9 10 7 22 67 41 30 53 46 13 1 1 3 1 2 1 1 2 6 Apr Aug ^ Dec ^ Feb ^ Jan Mar Oct June May ^ Nov ^ July ^ 8 ^ 9 10 …

Sep ^ 查找成功ASL＝(1*4+2*2+3*1+6*1)/8 = 17/8