数据结构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.keyR[i].key）{
s->R[i+2]=s->R[i];
i=i-1;
}
s->R[i+2]=large;
s->R[0]=small;
while（small.keyR[i].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次。
记录的比较次数和移动次数等同于单向扫描时的冒泡排序。
升级会员 