发布时间 : 星期三 文章《数据结构——C语言描述》习题及答案-耿国华-2更新完毕开始阅读8f9ed802393567ec102de2bd960590c69fc3d863
（5） 排序：按特定条件对所有员工的信息进行排序。
第八章答案
8．2 【解答】 5
ASLsucc=（1+2X2+3X4+4X3）/10=2.9
8.5 【解答】
ASLSUCC=(1 X4+2 X3+6)/8=2
ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/
11=40/11
8.12 【解答】
(1) ASLSUCC=(1+2 X2+3
X3+4X3+5X2+6)/12=3.5
(2) 排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep
折半查找ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/12
第九章 习 题
9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态：
（1）直接插入排序； （2）希尔排序（增量
d[1]=5）；
（3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。 9.2 一组关键字码，40，27，28，12，15，50，7，采用快
速排序或堆排序，写出每趟排序结果。
9.3 不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
n=7时在最好情况下需进行多少次比较？请说明理由。 对n=7给出一个最好情况的初始排列实例。 （保证每个基准记录都是中间记录）
9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从
中选出关键字从大到小顺序的前k(k< 9.5 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。 9.6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 [提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。 9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以 使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： 采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度O(n)； 讨论算法中记录的最大移动次数。 [提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。 9.8试以单链表为存储结构实现简单选择排序的算法 9.9假设含n个记录的序列中，其所有关键字为值介于v和w 之 间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。 9.10 已知两个有序序列(a1, a2 ,..., am)和(am+1 , am+2 ,..., an),并且 其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。