数据结构C语言版清华大学出版社89章课后部分答案.docx
- 文档编号:3727171
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:8
- 大小:17.09KB
数据结构C语言版清华大学出版社89章课后部分答案.docx
《数据结构C语言版清华大学出版社89章课后部分答案.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版清华大学出版社89章课后部分答案.docx(8页珍藏版)》请在冰点文库上搜索。
数据结构C语言版清华大学出版社89章课后部分答案
第八章
选择题
1.C2.A3.B4.C5.D6.B7.B8.A9.D10.D11.C12.C
填空题
1.n、n+1
2.4
3.8.25(折半查找所在块)
4.左子树、右子树
5.26
6.顺序、(n+1)/2、O(log2n)
7.m-1、[m/2]-1
8.直接定址
应用题
1.进行折半查找时,判定树是唯一的,折半查找过程是走了一条从根节点到末端节点的路径,所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时,其最大查找长度也是与二叉树的深度相关,但是含有n个节点的二叉排序树不是唯一的,当对n个元素的有序序列构造一棵二叉排序树时,得到的二叉排序树的深度也为n,在该二叉树上查找就演变成顺序查找,此时的最大查找长度为n;在随机情况下二叉排序树的平均查找长度为1+4log2n。
因此就查找效率而言,二分查找的效率优于二叉排序树查找,但是二叉排序树便于插入和删除,在该方面性能更优。
3.评价哈希函数优劣的因素有:
能否将关键字均匀的映射到哈希表中,有无好的处理冲突的方法,哈希函数的计算是否简单等。
冲突的概念:
若两个不同的关键字Ki和Kj,其对应的哈希地址Hash(Ki)=Hash(Kj),则称为地址冲突,称Ki和K,j为同义词。
(1)开放定址法
(2)重哈希法
(3)链接地址法
4.
(1)构造的二叉排序树,如图
(2)中序遍历结果如下:
101215202428303546505568
(4)平均查找长度如下:
ASLsucc=(1x1+2x2+3x3+4x3+5x3)/12=41/12
8.
哈希地址如下:
H(35)=35%11=2
H(67)=67%11=1
H(42)=42%11=9
H(21)=21%11=10
H(29)=29%11=7
H(86)=86%11=9
H(95)=95%11=7
H(47)=47%11=3
H(50)=50%11=6
H(36)=36%11=3
H(91)=91%11=3
第九章
选择题
1.D2.C3.B4.D5.C6.B7.A8.A9.D10.D
填空题
1.插入排序、交换排序、选择排序、归并排序
2.移动(或者交换)
3.归并排序、快速排序、堆排序
4.保存当前要插入的记录,可以省去在查找插入位置时的对是否出界的判断
5.O(n)、O(log2n)
6.直接插入排序或者改进了的冒泡排序、快速排序
7.Log2n、n
8.完全二叉树、n/2
9.15
10.{1238253550746390}
应用题
11.
(1)Shell排序(步长为531)每趟的排序结果
初始序列为
10087526127170374561118148832
步长为5的排序
14373261271008745611181708852
步长为3的排序结果
14273252376161458887170100118
步长为1的排序结果
14273237455261618788100118
最后结果
14273237455261618788100118170
(2)快速排序每趟的排序结果如图
初始序列
10087526127170374561118148832
第一趟排序
[32875261278837456114]100[118170]
第二趟排序
[1427]32[61528837456187]100118[170]
第三趟排序
14[27]32[455237]61[886187]100118[170]
第四趟排序
14[27]32[37]45[52]61[8761]88100118[170]
第五趟排序
14[27]32[37]45[52]61[8761]88100118[170]
最后结果
14[27]32[37]45[52]61[61]8788100118[170]
(3)二路归并排序每趟的排序结果
初始序列
[100][87][52][61][27][170][37][45][61][118][14][88][32]
第一趟归并
[87100][5261][27170][3745][61118][1488][32]
第二趟归并
[526187100][273745170][146188118][32]
第三趟归并排序
[273745526187100170][14326188118]
第四趟归并排序
[14273237455261618788100118170]
最后结果
14273237455261618788100118170
12.采用快速排序时,第一趟排序过程中的数据移动如图:
算法设计题
1.
分析:
为讨论方便,待排序记录的定义为(后面各算法都采用此定义):
#defineMAXSIZE100/*顺序表的最大长度,假定顺序表的长度为100*/
typedefintKeyType;/*假定关键字类型为整数类型*/
typedefstruct{
KeyTypekey;/*关键字项*/
OtherTypeother;/*其他项*/
}DataType;/*数据元素类型*/
typedefstruct{
DataTypeR[MAXSIZE+1];/*R[0]闲置或者充当哨站*/
intlength;/*顺序表长度*/
}sqList;/*顺序表类型*/
设n个整数存储在R[1..n]中,因为前n-2个元素有序,若采用直接插入算法,共要比较和移动n-2次,如果最后两个元素做一个批处理,那么比较次数和移动次数将大大减小。
算法如下:
(1)求出大小若R[n]>=R[n-1],则large=R[n],small=R[n-1];否则large=R[n-1],small=R[n]。
(2)寻找large的位置,从i=n–2开始循环,若large (3)插入largeR[i+2]=large (4)寻找small的位置从i开始循环,若small (5)插入smallR[i+1]=small,结束 算法描述如下: voidinsert-two(SqList*s){ intn,i; DataTypelarge,small; n=s->length; if(s->R[n].key>=s->R[n-1].key){ large=s->R[n]; small=s->R[n-1]; }else{ large=s->R[n-1]; small=s->R[n]; } i=n-2; s->R[0]=large; while(large.key s->R[i+2]=s->R[i]; i=i-1; } s->R[i+2]=large; s->R[0]=small; while(small.key s->R[i+1]=s->R[i]; i=i-1; s->R[i+1]=small; } } 算法分析: 因为对两个元素的插入是“同时”相继进行的,所以让其比较次数的最大值为n,最小值为3;平均值约为n/2;移动次数的最大值为n+2,最小值为4,平均约为n/2。 可以看出,平均比较次数和记录的平均移动次数约为直接插入排序的一半。 该算法是稳定的。 2. 分析: 设R[0]~R[n-1]中存有n个记录的待排序列,对其进行双向冒泡。 奇数趟对序列R[]从前往后扫描,比较相邻的关键字,若逆序则交换,直到把关键字最大的记录移动到序列尾部;偶数趟从后往前扫描,比较相邻的关键字,若逆序则交换,直到把关键字最小的记录移动到序列前端,反复进行上述过程,直到有序为止。 因此需设变量i,记录扫描的循环次数(奇数趟和偶数趟两趟作为一个循环),以便对待排序列的上下界进行修正。 算法描述如下: voidShuttlesort(DataTypeR[],intn){ inti=1,j,exchange=1; while(exchange==1){ exchange=0; for(j=i-1;j<=n-i-1;++j){ if(R[j].key>R[j+1].key){ R[j]<=>R[j+1];/*交换*/ exchange=1; } } for(j=n-i-1;j>=i;j--){ if(R[j-1].key>R[j].key){ R[j-1]<=>R[j];/*交换*/ exchange=1; } } ++i; } } 可以看出,循环次数最多为[n/2]+1次,最少为1次。 记录的比较次数和移动次数等同于单向扫描时的冒泡排序。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 清华大学出版社 89 课后 部分 答案