第九章习题.doc

习题
一、单项选择题
1. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(　　)。
A. n B. n+1 C. (n-1)/2 D. (n+1)/2
2. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(　　)。
A. 3 B. 4 C. 5 D. 6
3. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为(　　)。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
4. 从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为(　　)。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
5. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是(　　)。
A. -1~1 B. -2~2 C. 1~2 D. 0~1
6. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为(　　)。
A. 4 B. 8 C. 12 D. 13
7. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数(　　)。
A. 1 B. 2 C. 3 D. 4
8. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为(　　)。
A. d B. d+1 C. (d+1)/m D. (d+1)%m
二、填空题
1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时间复杂度为________。
2. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。
3. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。
4. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。
5. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。
6. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。
7. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
8. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。
9. 一棵5阶B-树中，除根结点外，每个结点的子树树目最少为________，最多为________。
10. 高度为k的m阶B-树至少有________个结点。
三、应用题
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.试将折半查找的算法改写成递归算法。
2.设计算法判定给定二叉树是否为二叉排序树。

习题参考答案
一、单项选择题
1. D 2. B 3. C 4. A 5. A 6. C 7. B 8. D
二、填空题
1. (n+1)/2, O(n) 2. 20.5, 41
3. 1，3 4. (n/s+s)/2+1
5. 小于，大于 6. 有序序列
7. 1 8. 2
9.3，5 10.
三、应用题
1. 折半查找判定树如图所示，平均查找长度等于1*1+2*2+4*3+3*4=29/10。图中的结点与有序表中元素的对应关系如下表所示。

10
9
4
5
6
7
8
1
2
3

1
2
3
4
5
6
7
8
9
10
15
26
34
39
45
56
58
63
74
76

38
52
25
16
74
30
68
90
54
72
2. 二叉排序树如图所示，平均查找长度等于1*1+2*2+3*3+2*4+2*5=32/10。

3. H(K)=K % 13平均查找长度为14/10，其余解答如下。

元素 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

4. H(K)=K % 11，哈希表如图所示，平均查找长度17/12。

0

∧

四、算法设计题
1. int bisearch (sqlist L, int low, int high , elemtype x ) {
if (low>high) reeturn( 0 );
else { mid=(low+high)/2;
if (L.data[mid]= =x) return (mid);
else if (L.data[mid]>x) bisearch(L,low,mid-1,x);
else bisearch(L,mid+1,high,x);
}
}//bisearch
2. 分析：对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。算法一：
int bsbtr(BiTree T ) {//predt记录当前结点的前驱结点值，初值为-∞
if (!T) return (1);
else { b1=bsbtr(TàLchild);
if (!b1| |(predt>=Tàdata)) return (0);
predt=Tàdata;
b2=bsbtr(Tàrchild);
return (b2);
}
}//bsbtr
算法二：（用中序递归遍历树算法，“访问T”为将T进队列，遍历树后，对队列从1到n检查是否升序）