0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6 ASLsucc = (1×4 + 2×3 + 6) / 8 = 2
ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11
8.6 试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的 平均查找长度。
（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG， JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。
8.7 试编写利用折半查找确定记录所在块的分块查找算法。
8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结 构，且树中结点的关键字均不同。
[提示]：检验中序遍历序列是否递增有序？
[方法 1]：用非递归中序遍历算法，设双指针pre, p 一旦 pre->data > p->data 则返回假
[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦 pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法
（1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根
8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。
8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结 点A、B 中，A 是 B 的祖先，则认为A 是A、B 的最近公共祖先）。 [提示]：
（1） 假设A<=B，
（2） 从根开始，左走或右走，直到A 在左（或根），B 在右（或根）。
8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素 x，并保持表的有序 性。 [提示]：（1）表中已经有x，（2）表中没有x 参 P. 231
8.12 已知长度为12 的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。 （1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。
[提示]：画出判定树或排序树，根据P.191ASL 定义计算平均查找长度。
8.13 含有 9 个叶子结点的 3 阶 B-树中至少有多少个非叶子结点？含有 10 个叶子结点的 3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。
8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]：
（1） p=root
（2） 如果p->key 大于、等于x，则删除p->rchild 和 p， （3） 左走一步，转（2）
（4） 如果p->key 小于x，则反复右走， （5） 转（2）
（6） 直到p==NULL
8.15 在平衡二叉排序树的每个结点中增加一个lsize 域，其值为它的左子树中的结点数加1。编写一时间复杂度为 O(log n)的算法，确定树中第k 个结点的位置。 [提示]：先画图手工求。 （1）sum=0,
（2）从当前根开始沿左链找sum + lsize<=k 的最大结点a，
（3）沿a 的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k
第九章
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 已知两个有序序列(a , a ,..., a )和(a , a ,..., a ),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。 9.11 偶交换排序如下所述：第一趟对所有奇数 i,将 a[i]和 a[i+1]进行比较；第二趟对所有偶数 i,将 a[i]和 a[i+1]进行比较，若 a[i]>a[i+1],则将两者交换；第一趟对所有奇数 i, 第二趟对所有偶数 i，?,依次类推直至整个序列有序为止。 （1） 这种排序方法的结束条件是什么？ （2） 分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。 （3） 写出奇偶交换排序的算法。 9.12 设计一个用链表表示的直接选择排序算法。（与9.8 重） 9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。（与9.5 重复） 9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（与9.7 类似） 9.15 为什么通常使用一维数组作为堆的存放形式？ 9.16 已知（k ,k ,?，k ）是堆，写一个算法将（k ,k ,?，k ，k）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。 9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基 数排序的时空性能、稳定性和适用情况。 9.18 在供选择的答案中填入正确答案： 1 ）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_ 。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为 C 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 3）、下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误： （ ）在一个大堆中，最小元素不一定在最后。 （ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o （nlog2n）。 （ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。 第 1 章 绪论 1．4 试编写算法，求一元多项式P (x)=a +a x+a x +a x +?a x 的值P (x )，并确定算法中 的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a (i=0,1,?,n),x和n，输出为P (x )。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2 ）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 void polyvalue() { int n,p,i,x,xp,sum; float a[]; float *p=a; printf(\ scanf(\ printf(\ for(i=0;i<=n;i++) scanf(\ printf(\ scanf(\ p=a;xp=1;sum=0; //xp 用于存放x 的i 次方 for(i=0;i<=n;i++) { sum+=xp*(*p++); xp*=x; } printf(\ }//polyvalue 第二章 线性表 2．4 设线性表存于 a(1:arrsize)的前elenum 个分量中且递增有序。试写一算法，将 X 插入 到线性表的适当位置上，以保持线性表的有序性。 Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中 { if(va.length+1>va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2．6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink 且小于maxk 的所有元素 { p=L;