若对大小均为 n 的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概时的平均查找长度是否相同? 查找不成功，即表中没有关键字等于给定值 K 的记录； 查找成功，且表中只有一个关键字等于给定值 K 的记录；
查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。
试分别画出在线性表(a,b,c,d,e,e,f)中进行折半查找，以查关键字等于 e、f 和 g 的过程。
画出对长度为 10 的有序表进行折半查找的判定树，并求其等概时查找成功的平均查找长度。
假设按下述方法进行顺序表的查找：若表长<=10，则进行顺序查找，否则进行折半查找。试画出对表长 n=50 的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。 已知含12个关键字的有序表及其相应权值为： 关键字 A B C D E F G H I J K L 权值 8 2 3 4 9 3 2 6 7 1 1 4
画出对以上有序表进行折半查找的判定树，并计算它的 PH 值。 已知如下所示长度为12的表
(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
可以生成下方二叉排序树的关键字初始排列有几种？请写出其中的任意三个。
选取哈希函数 H(k)=(3k) MOD 11。用开放定址法处理冲突，di = i((7k) MOD 10+1) (i=1,2,3,…)。试在 0～10 的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概情况下查找成功时的平均查找长度。
试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的平均查找长度。
（ZHAO, QIAN, SUN, LI, ZHOU, WU, CHEN, WANG, CHANG, CHAO, YANG, JIN） 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 bool BiSortTree( BiTree t )
// 以二叉链表作二叉查找树的存储结构,若以 t 为根 // 指针的二叉树是二叉查找树，则返回 true, 否则返回 false
第十章
基数排序的时间复杂度为O (d×n)，因此特别适合于待排记录数 n 值很大，而关键字“位数 d ”较小的情况。并且还可以调整“基数”（如将基数定为100或1000等）以减少基数排序的趟数d的值。
一般情况下，对单关键字进行排序时，所用的排序方法是否稳定无关紧要。但当按\最次位优先\进行多关键字排序时(除第一趟外)必须选用稳定的排序方法。
以关键字序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： (1) 直接插入排序； (2) 希尔排序(增量 d[1]=5 )； (3) 快速排序； (4) 堆排序； (5) 归并排序； (6) 基数排序。
若对下列关键字序列进行快速排序或归并排序,分别写出三次调用过程 Partition 和过程 Merge 后的结果。
( Tim, Kay, Eva, Roy, Dot, Jon, Kim, Ann, Tom, Jim, Guy, Amy)
试问在1题所列各种排序方法中，哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一个不稳定的实例。
不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这 n 个元素的初始排列。
n=7 时在最好情况下需进行多少次比较? 请说明理由。 对 n=7 给出一个最好情况的初始排列实例。
判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。
(100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (12, 70, 33, 65, 24, 56, 48, 92, 86, 33); (103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20); (05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100)。