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

{

w = FirstAdj ( v ); while ( w ) {

if ( ! visited[w] ) SearchPath(w, vt, k, m+1); w = NextAdj ( v, w ); } }

visited[v] = FALSE; }

二十一、求所有简单回路：

void SearchCycle ( int v, int m ) { // 存储结构可选用邻接矩阵 visited[v] = TRUE; P[m] = v;

w = FirstAdj ( v ); while ( w ) {

if ( ! visited[w] ) SearchCycle(w, m+1); else {

for ( j = 1 ; P[j]==w ; j++);

for ( i =j ; i <= m ; i++ ) cout << P[i]; cout << w << endl; }

w = NextAdj ( v, w ); }

visited[v] = FALSE; }

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

9

2 b c 2 2

e 1 a 1 d 2 1

g h f ∞ ∞ ∞ ∞ ∞ 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

2 2 3 1 5 2 6 4 ∧ 4 d 4 2 6 1 7 2 ∧ 5 e

4 4 5 1 7 2 8 1 ∧ 6 f

5 2 6 2 8 3 ∧ 7 g 6 1 7 3 ∧ 8 h

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

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 av

0 10 0 0 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)) if (H!=p) {

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

p = p->next; }

return q; }

11

H = H->next; 二十六、判断是否二叉排序树：

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 );

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 50 52 20 60 20 50 60 68 50

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

12