北邮算法与数据结构习题参考答案

. . . .

w = NextAdj ( v, w ); }

visited[v] = FALSE; }

二十二、求最小代价生成树： 1、 0 2 3 ∞ ∞ ∞ ∞ ∞ 2 b 2 2 e 2 g 2 0 ∞ 2 ∞ ∞ ∞ ∞

1 d 3 ∞ 0 1 ∞ ∞ ∞ ∞ a 1 1 c f h ∞ 2 1 0 2 4 ∞ ∞ ∞ ∞ ∞ 2 0 1 2 ∞ ∞ ∞ ∞ 4 1 0 2 1 ∞ ∞ ∞ ∞ 2 2 0 3 ∞ ∞ ∞ ∞ ∞ 1 3 0 2、 2 2 3 3 ∧ 1 a 2 b 2 2 e 2 g 1 1 2 4 2 ∧ a d 2 b 1 1 1 3 4 1 ∧ c f h 3 c 4 d 2 2 3 1 5 2 6 4 ∧ 5 e 4 2 6 1 7 2 ∧ 6 f 4 4 5 1 7 2 8 1 ∧ 7 g 5 2 6 2 8 3 ∧ 8 h 6 1 7 3 ∧

二十三、求关键路经和最短路经：

1、 a b c d e f g h i

ve: 0 2 3 6 11 10 13 14 17

vl: 0 4 3 6 11 10 13 15

. . . . .

. . . .

17

关键路经为：a c d f e g i

2、a→b c d e f g h i

2(ab) 3(ac) ∞ ∞ ∞ ∞ ∞ ∞

3(ac) 4(abd) ∞ ∞ ∞ ∞ ∞

4(abd) ∞ ∞ ∞ ∞ ∞ 7(abde) 8(abdf) ∞ ∞ ∞ 8(abdf) 9(abdeg) ∞ 9(abdeg) 9(abdfh) 9(abdfh)13(abdegi)

11(abdfhi)

二十四、边界标识法： 1、

802 213 462 559 0 56 0 117 0 53 0 167

0 0 0 0 av 2、

802 213 462 0 56 0 17 0 264

0 0 0 av

二十五、按访问频度查找：

list Search ( list H, keytype K )

. . . . .

∞

∞ . . . .

{

p = H; q = NULL;

while ( p->next && ! q )

{

if (p->next->key == K) {

q = p->next; q->freq++;

while ((H!=p) && (H->next->freq>=q->freq)) H->next;

if (H!=p) {

p->next = q->next; q->next = H->next; H->next = q; } }

p = p->next;

}

return q; }

二十六、判断是否二叉排序树：

int BST ( bitptr t, bitptr &p ) {

if ( ！ t ) return 1; L = BST ( t->lc , p ); D = 1;

if ( p && p->data > t->data) else D = 0; p = t;

R = BST ( t->rc , p );

. . . . .

H = . . . .

return L && D && R; }

int BinarySortTree ( bitptr t ) {

p=NULL;

return BST ( t , p ); }

二十七、建立 2-3 树：

20 20 30 30

20 50

插入20 插入30 插入50

30 30 52 30 52 20 20 50 52 20 60 60 68 50 50

插入52 插入60 插入68 52 52 68 52 20 30 30 68 70 20 32 60 70 60 50 60 70 20

插入70 删除50 删除68

二十八、散列表：

（1）：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

. . . . .

. . . .

Apr Aug Dec Feb Jan Mar May Jun Jul Sep Oct Nov

1+2+1+1+1+1+2+4+5+2+5+6 31 ASL成功 = —————————————— = —— 12 12

5+4+3+2+1+9+8+7+6+5+4+3+2+1 30 ASL不成功 = ———————————————— = —— 14 7

（2）：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ Apr Dec Feb Jan Mar Oct Sep Aug Jun May Nov Jul

1+2+1+1+1+2+3+1+2+1+2+1 9 ASL成功 = —————————————— = —— 12 6

3+1+2+2+1+4+3+3+1+2+1+1+1+1 13 ASL不成功 = ———————————————— = —— 14 7

ASL不成功 = 12/14 （与空指针比较次数不算）？

二十九、证明快速排序退化时的时间复杂度：

当待排序列有序时，有 T ( n ) = T ( n – 1 ) + n – 1 = T ( n – 2 ) + 2 * n – 3 = T ( n – 3 ) + 3 * n – 6 …

= T ( n – i ) + i * n – i * ( i

. . . . .