一、选择题

1．设有1000个元素，用二分法查找时，最小比较次数为（ B ）
A、0 B、1
C、10 D、500

2．二分查找要求结点（ A ）。
A、有序、顺序存储 B、有序、链接存储
C、无序、顺序存储 D、无序、链接存储

3.已知8个元素（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( B )。【解：画出二叉排序树】
A、 4 B、 5 C、 6 D、7

4.比较次数与排序的初始状态无关的排序方法是( B )。
A．直接插入排序 B．直接选择排序 C．快速排序 D．冒泡排序

5.在内部排序中，排序时不稳定的是( C )
A. 插入排序 B. 冒泡排序 C. 交换排序 D. 归并排序

二、应用题

1、按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树（二叉查找树、二叉搜索树）中, 使之仍是一棵二叉排序树。
(1)画出插入完成之后的二叉排序树；

(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?（比较次数）
10 12 20 15 19
(3)对该树进行中序遍历，试写出中序遍历序列。
5 6 8 9 10 12 15 19 20 25

2.设一组初始记录关键字为(25，18，14，30，45，8)，则以记录关键字25为枢轴的一趟快速排序结果的过程。
8 18 14 25 45 30

3．采用直接选择排序算法对线性表(25，18，14，30，45，8)进行排序，写出每趟排序的过程，并用[　]将有序区括起来。
i=1: [ 8 ] 18 14 30 45 25
i=2 [ 8 14 ] 18 30 45 25
i=3 [ 8 14 18 ] 30 45 25
i=4 [ 8 14 18 25 ] 45 30
i=5 [ 8 14 18 25 30 ] 45

3．采用直接插入排序算法对线性表(25，18，14，30，45，8)进行排序，写出每趟排序的过程，并用[　]将有序区括起来。
i=1 [ 18 25 ] 14 30 45 8
i=2 [ 14 18 25 ] 30 45 8
i=3 [ 14 18 25 30 ] 45 8
i=4 [ 14 18 25 30 45 ] 8
i=5 [ 8 14 18 25 30 45 ]

4.设散列表的地址范围为0～17，散列函数为：H（K）＝K MOD 13，K为关键字。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），完成以下问题：

（1）试画出构造的散列表；

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
	40			17	31	32	30	46	47	10	24	63	49

（2）说明查找关键字49时需要依次与哪些关键字进行比较；
10 24 63 49

（3）计算等概率情况下查找成功时的平均查找长度。（即所有元素查找成功时比较次数之和/元素个数）
ASL=(1+1+1+1+1+4+2+2+1+2+4)/11=1.82