一、单项选择题
3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( B )。
A. 3 B. 4 C. 5 D. 6
4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( C )。
A. 2 B. 3 C. 4 D. 5
5. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( D )。
2
A. O(n) B. O(n) C. O(1) D. O(log2n)
8. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( C )。
2
A. O(n) B. O(1) C. O(log2n) D. O(n)
9. 从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( A )。
2
A. O(n) B. O(1) C. O(log2n) D. O(n)
11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K计算哈希地址，则元素64的哈希地址为( C )。
A. 4 B. 8 C. 12 D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数( B )。
A. 1 B. 2 C. 3 D. 4
13. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( D )。
A. d B. d+1 C. (d+1)/m D. (d+1)%m 二、填空题
1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为___(n+1)/2_____，时间复杂度为__O(n)______。
6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为____1____和____3____。
7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为___5_____，最后一层的结点数为___19_____。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定__小于等于____该结点的值，右子树上所有结点的值一定____大于____该结点的值。
11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个___递增序列_____。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明______查找成功_，若元素的值小于根结点的值，则继续向____左子树____查找，若元素的值大于根结点的值，则继续向___右子树_____查找。
13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的___左子树_____插入，若元素的值大于根结点的值，则接着向根结点的__右子树______插入。
16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到___5_____次存储冲突。 17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，
采用线性探测法处理冲突，则平均查找长度为___9/4_____。
19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有___3_____个，哈希地址为5的元素有___2_____个。 三、应用题
1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。
2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址
0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表
4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。 1.
45 26 63 15 34 56 74 39 58 76 ASL=(1+2*2+3*4+4*3)/10=2.9
38 25 52 16 3474 68 90 2.54 72 ASL=(1+2*2+3*3+4*2+5*2)/10=3.2 3.
元素 初始哈希地址 最终哈希地址 32 75 29 63 48 94 25 46 18 70 6 10 3 11 9 3 12 7 5 5 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 25 ASL=1/2(1+13/3)=8/3 4.
0 1 2 3 4 5 6 7 8 9 10 11 48 36 ∧ 25 49 ∧ 75 63 ∧ 29 ∧ 18 ∧ 32 80 ∧ 94 70 ∧
ASL=1/12(1*7+2*5)=17/12