将k=[log2n]+1，n=s分别代入（a）（b）两个等式即得。
2. 选择题
（1）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
（2）对一个长度为50的有序表进行折半查找，最多比较（ ）次就能查找出结果。 A. 6 B. 7 C. 8 D. 9
（3）对有18个元素的有序表做折半查找，则查找A[3]（下标从1开始）的比较序列的下标依次为（ ）。
A. 1-2-3 B. 9-5-2-3 C. 9-5-3 D. 9-4-2-3
（4）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则做（ ）型调整以使其平衡。 A. LL B. LR C. RL D. RR （5）理论上，散列表的平均比较次数为（ ）次。
A. 1 B. 2 C. 4 D. n （6）二叉排序树中，最小值结点的（ ）。 A. 左指针一定为空 B. 右指针一定为空 C. 左、右指针均为空 D. 左、右指针均不为空
（7）散列技术中的冲突指的是（ ）。
A.两个元素具有相同的序号 B. 两个元素的键值不同，而其他属性相同 C. 数据元素过多 D. 不同键值的元素对应于相同的存储地址
（8）散列表表长m=14，散列函数H(k)=k。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。 A. 8 B. 3 C. 5 D. 9
（9）采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。 A. 一定都是同词义词 B. 一定都不是同义词 C. 不一定都是同义词 D. 都相同
（10）静态查找与动态查找的根本区别在于（ ）。 A. 它们的逻辑结构不一样 B. 施加在其上的操作不同
C. 所包含的数据元素的类型不一样 D. 存储实现不一样
3．设一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突，请按以下要求，将关键码{10，100，32，45，58，126，3，29，200，400，0}散列到表中。 （1）散列函数采用除留余数法，用%hashSize(取余运算)将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 400 key 0 3 29 200 32 45 58 100 10 126 产生冲突的关键码有：29－1次，45－1次，58－2次，126－2次，400－2次
（2）散列函数采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 key 58 10 100 3 200 32 400 0 45 126 29 产生冲突的关键码有：100－1次，200－2次，400－2次，0－7次，126－1次
4．试编写一个函数，完成拉链法解决冲突的散列表上删除一个指定结点的算法。
5．设散列表的长度为13，散列函数为H(k)=k，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探测查找解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。 答案：拉链法：
1141277936855671920841011231110 平均查找次数：成功时是21/12=1.75次，不成功时是(4+2+2+1+2+1)/13=12/13=0.92次（在这里查找比较是指元素值的比较。如果指针为空，则不进行查找比较，此时不算查找）。
线性探测法： H(key) 0 key 冲突次数 成功时的比较次数 不成功时的比较次数 1 14 0 1 2 01 1 2 3 68 0 1 4 27 3 4 5 55 2 3 6 19 0 1 7 20 0 1 8 84 2 3 9 79 8 9 10 23 0 1 11 11 0 1 12 10 2 3 0 12 11 10 9 8 7 6 5 4 3 2 1 平均查找次数：成功时是2.5次，不成功时ASL=（0+12+11+10+9+8+7+6+5+4+3+2+1）/13 = 6次。
习题8
1. 填空题
(1) 排序的主要目的是为了以后对已排序的数据元素进行（___________）。
答案：查找
(2) 对n个元素进行起泡排序，在（___________）的情况下比较的次数最少，其比较次数
为（___________）；在（___________）的情况下比较次数最多，其比较次数为（___________）。 答案：原始序列有序 n-1 原始序列逆序 n(n-1)/2
(3) 对一组元素{54,38,96,23,15,72,60,45,83}进行直接插入排序，当第7个元素60插入到有
序表时，寻找插入位置需比较（___________）次。 答案：3
(4) 对一族元素{54,38,96,23,15,72,60,45,83}进行快速排序，在递归调用中使用的栈所能达到的最大深度为（___________） 答案：4
(5) 对n个待排序元素序列进行快速排序，所需最好时间是（___________），最坏时间是
（___________）。 答案：O(nlogn) O(n)
(6) 利用简单选择排序对n个元素进行排序，最坏情况下，元素交换的次数为（___________）。 答案：n-1
(7) 如果将序列{50,16,23,68,94,70,73}建成堆，只需把16与（___________）交换。 答案：50
(8) 对于键值序列{12,13,11,18,60,15,7,18,25,100}，用筛选法建堆，必须从键值为（___________）的结点开始。 答案：60
(9) 采用改进的冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递
增，则排序过程中记录的比较次数为（___________）。若A的初始状态为递减排序，
则记录的交换次数为（___________）。 答案：n-1 n(n-1)/2
2. 单选题
(1) 从未排序序列中依此取出一个元素与已排序序列中的元素依此进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A.插入排序 B. 选择排序 C. 希尔排序 D. 二路归并排序 (2) 一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序以位于最左位置的对象为基
准而得到的第一次划分结果为（ ）。
A. {38,46,79,56,40,84} C. {40,38,46,56,79,84}
B. {38,79,56,46,40,84} C. {38,46,56,79,40,84}
2
(3) 对二叉排序树进行（ ）遍历，可以得到该二叉树所有节点构成的排序序列。 A. 前序 B. 中序 C. 后序 D. 按层序 (4) 当待排序列基本有序时，下列排序方法中（ ）最好。
A. 直接插入排序
B. 快速排序
C. 堆排序
D. 归并排序
(5) 在下列排序算法中，在待排序的数据表已经为有序时，比较操作花费时间反而最多的是（ ）。
A. 快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序
(6) 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是
（ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接插入排序 (7) 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 希尔排序 (8) 已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时
间。 A. 堆排序
B. 插入排序
C. 快速排序
D. 直接选择排序 D. 堆 D. 插入排序
(9) 下面给出的4种排序法中（ ）排序法是不稳定排序法。 A. 插入 B. 冒泡 C. 二路归并 (10) 就平均性能而言，最快的排序方法是（ ）。
A. 冒泡排序
B. 希尔排序
C. 快速排序
3. 判断以下序列是否为小（顶）根堆？若否，则以最少的移动次数将他们调整为小（顶）
根堆。（要求画出最后的堆结构和线性序列） (1) (19,78,32,66,26,58,46,95,89,31)；
(2) (113,98,69,35,68,25,43,19,31,55,16,29)。 答案：
(1) (19,26,32,66,31,58,46,95,89,78)
19263266315846958978
(2) (16,19,25,31,55,29,43,35,113,98,68,69)
1619253155294335113986869
4. 设有关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要求按照关键码值递增的次序进行排序。
(1) 若采用初时步长为4的Shell（希尔）排序法，写出一趟排序的结果；
(2) 若采用以第一个元素为分界元素（枢轴）的快速排序法，写出一趟排序的结果。 答案：
(1) (Q,A,C,S,Q,D,F,X,R,H,M,Y)
(2) (F,H,C,D,Q,A,M,Q,R,S,Y,X)
5. 试编写一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。
6. 编写算法，实现将整形数组中的元素按照奇数和偶数分开，使奇数在原数组的前面，偶
数在原数组的后面。
7. 利用快速排序算法的思想，编写算法，实现求第k个最小值的功能。
8. 试写一个非递归的快速排序算法。
9. 如果存储结构采用的是带头结点的单链表，编写排序算法使链表中的元素有序排列。