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

2014数据结构习题集答案(4)

来源:网络收集 时间:2020-04-17 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

错误!未找到引用源。画表如下:

0 1 2 3 4 5 6 7 8 9 111111110 1 2 3 4 5 6 7 3164 241 33442 7 3 9 4 0 0 0 1 6 7 错误!未找到引用源。查找63,首先要与H(63)=63=15号单元内容比较,即63 vs 31 ,no;

然后顺移,与46,47,32,17,63相比,一共比较了6次! 错误!未找到引用源。查找60,首先要与H(60)=60=12号单元内容比较,但因为12号单元为空(应当有空标记),所以应当只比较这一次即可。

错误!未找到引用源。对于黑色数据元素,各比较1次;共6次;

对红色元素则各不相同,要统计移位的位数。“63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次,

所以ASL=1/11(6+2+3×3+6)=23/11 6.

022167241330455364678139101

H(22)=(3*22) % 11=0 H(41)=(3*41) % 11=2 H(53)=(3*53) % 11=5 H(46)=(3*46) % 11=6 H(30)=(3*30) % 11=2 冲突 H1=(2+(1×((7*30) % 10+1)))% 11=3

H(13)=(3*13) % 11=6 冲突 H1=(6+(1×((7*13)% 10+1)))% 11=8

H(1)=(3*1) % 11=3 冲突 H1=(3+(1×((7*1)% 10+1)))% 11=0 冲突

H2=(3+(2×((7*1) % 10+1)))% 11=8冲突H3=(3+(3×((7*1)% 10+1)))% 11=5冲突H4=(3+(4×((7*1) %

10+1)))% 11=2冲突H5=(3+(5×((7*1)% 10+1)))% 11=10

H(67)=(3*67) % 11=3 冲突 H1=(3+(1×((7*67)% 10+1)))% 11=2 冲突 H2=(3+(2×((7*67)% 10+1)))% 11=1

平均查找长度ASL=(1×4+2×2+3×1+6)/8=17/8

7. 建立2-3树后的状态 删除43后的2-3树状态: 删除 24后的2-3树状态: 34 62 34 34 62 18 13 18 51 75 18 51 75 13 51 24 62 75 43 13 24

三、算法题答案 typedef int KeyType; typedef struct{ KeyType key; char name[20]; }SElemType; typedef struct{

SElemType elem[MAXSIZE]; int length; }SSTable; (1)

int Search_Seq(SSTable ST, KeyType key) { ST.elem[0].key = key;

for ( int i = ST.length; (ST.elem[i].key != key); --i); return i;

}//Search_Seq (2)

int Search_Bin(SSTable ST, KeyType key) { int high,low,mid;

low = 1;high = ST.length; while(low <= high){ mid = (low + high)/2;

if (key == ST.elem[mid].key) return mid;

else if (key <= ST.elem[mid].key) high = mid - 1; else low = mid +1; }

return 0; }//Search_Bin

第十章 参考答案:

一.单选与填空

2

1.C 2. A 3.D 4.C 5. C 6.B 7.O(n) 8. 直接插入排序

二.解答题1. (1)希尔排序

初始3658 73 8324序列 7 5 6 6 9 4 1 6 63438527d=5 3 8 5 4 6 7 9 6 1 6 42537638d=3 3 8 6 1 6 4 6 5 7 9 23345678d=1 3 8 1 4 7 6 6 5 6 9

37,65(2)快速排序 ,56,8,76,3,89,34,21,46 i j j 21,65,56,8,76,3,89,34, □,46

i i j 21,□,56,8,76,3,89,34,65,46

i j j 21,34,56,8,76,3,89,□,65,46 过程

i i j 21,34,□,8,76,3,89,56,65,46

i j j 21,34, 3,8,76,□,89,56,65,46

i i j 21,34, 3,8,□,76,89,56,65,46

i j j (21,34, 3,8) 37 (76,89,56,65,46)

第一趟排序结果:

(3)堆排序

初始关键字的完全二叉树形式: 初始建堆的结果:

56,,658,76,38,89,34,21,46,56,,76,3,89,34,21,46 37,65,3737+6583437+568937+56893487637+566565+3*5637876+376+*389*3421462146

8462134214676+3*

89

第一次交换之后的结果: 第一次交换之后重建堆的结果:

4637+763482189+653*5637834218965+463*7637+5637

2.(1)直接插入排序

初始关键字:( 503 ) 087 512 061 908 170 897 275 653 426

i=2:( 087 503 ) 512 061 908 170 897

275 653 426

i=3:( 087 503 512 ) 061 908 170 897

275 653 426

i=4:( 061 087 503 512 ) 908 170 897

275 653 426

i=5:( 061 087 503 512 908 ) 170 897

275 653 426

i=6:( 061 087 170 503 512 908 ) 897

275 653 426

i=7:( 061 087 170 503 512 897 908 )

275 653 426

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库2014数据结构习题集答案(4)在线全文阅读。

2014数据结构习题集答案(4).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/988127.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: