第一范文网 - 专业文章范例文档资料分享平台

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

来源:用户分享 时间:2025/7/9 19:07:33 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

. . . .

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

. . . . .

搜索更多关于: 北邮算法与数据结构习题参考答案 的文档
北邮算法与数据结构习题参考答案.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c1kk3a9s6so6m3qp9xkwe9ersa9ps1u00xcx_3.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top