【解答】
删除50后：
55 30 80 40 60 70 95 20
删除40后：
55 80
10-10 对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。 【解答】 设B树的阶数m = 199，则?m/2? = 100。若不包括失败结点层，则其最大层数为 ?log?m/2? ((N+1)/2)? = ?log100 1000000? = 3
若使得每一层关键码数达到最大，可使其层数达到最小。第0层最多有 (m-1) 个关键码，第1层最多有m(m-1) 个关键码，第2层最多有 m2 (m-1) 个关键码，?，第h-1层最
-多有mh-1 (m-1) 个关键码。层数为h的B树最多有 (m-1) + m (m-1) + m2 (m-1) + … + mh1 (m-1) = (m-1) (mh–1) / (m-1) = mh–1个关键码。反之，若有n个关键码，n≤mh–1，则 h ≥ log m (n+1)，所以，有1999999个关键码的199阶B树的最小层数为 ?log m (n+1)? = ?log199 (1999999 +1)? = ?log 199 2000000? = 3
10-11 给定一组记录，其关键码为字符。记录的插入顺序为 { C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J }，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。 【解答】
插入C, S, D 插入T 插入A 插入M
S S D S C D S
C D S T A C D S T A C D M S T
插入P 插入I
D S D M S
A C D M P S T A C D I M P S T
插入B, W, N, G 插入U
D M S U D M S
D G I M N P S T W A B C D G I M N P S T U W A B C
20 30 60 70 95 214
插入R
P
D M S U
D G I M N P R S T U W A B C
插入K
P
D I M S U
I K A B C D G M N P R S T U W
插入E P
D I M S U
A B C D E G I K M N P R S T U W
插入H
P
D G I M S U
G H I K A B C D E M N P R S T U W
插入O, L P
D G I M S U
A B C G H I K L D E M N O P R S T U W
插入J
I P
S U D G K M
G H I J K L D E M N O P R S T U W A B C
10-12 设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1, 2, 3, 4, 5层的B+树，最多能存储多少记录，最少能存储多少记录。 【解答】
215
一层B+树：根据B+树定义，一层B+树的结点只有一个，它既是根结点又是叶结点，最多可存储m1 = 15个记录，最少可存储 ?m1/2? = 8个记录。
二层B+树：第0层是根结点，它最多有m = 100棵子树，最少有2个结点；第1层是叶结点，它最多有m个结点，最多可存储m*m1 = 100*15 = 1500个记录，最少有2个结点，最少可存储2* ?m1/2? = 16个记录。
三层B+树：第2层是叶结点。它最多有m2个结点，最多可存储m2 * m1 = 150000个记录。最少有2* ?m/2? = 100个结点，最少可存储2* ?m/2? * ?m1/2? = 800个记录。
四层B+树：第3层是叶结点。它最多有m3个结点，可存储m3 * m1 = 15000000个记录。最少有2* ?m/2? 2 = 2 * 502 = 5000个结点，存储2* ?m/2? 2 * ?m1/2? = 40000个记录。
五层B+树：第4层是叶结点。它最多有m4个结点，可存储m4 * m1 = 1500000000个记录。最少有2* ?m/2? 3 = 2 * 503 = 250000个结点，存储2* ?m/2? 3 * ?m1/2? = 2000000个记录。
10-13设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12 78
15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为
114 ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 1010搜索不成功的平均搜索长度为
361 ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =
1313(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 78
15 03 57 45 20 8 31 9 36 10 11 23 12 12 (1)
(1) (1) (1) (1) (1) (1) (3) (5) (1) 搜索成功的平均搜索长度为
116 ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 1010 216
10-14 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设?是散列表的装载因子，则有
11ASL?(1?) succ21??【解答】
已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc ? 2，则有ASLsucc 1?1?n150221???? 2，解得 ? ?。又有? = =?? ，则 m ? 225。 ?2?1??mm33
10-15 若设散列表的大小为m，利用散列函数计算出的散列地址为h = hash(x)。 (1) 试证明：如果二次探查的顺序为(h + q2), (h + (q-1)2), …, (h+1), h, (h-1), …, (h-q2)，其中， q = (m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2, m-4, m-6, …, 5, 3, 1, 1, 3, 5, …, m-6, m-4, m-2 (2) 编写一个算法，使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法，按给定值x来搜索一个大小为m的散列表。如果x不在表中，则将它插入到表中。 【解答】
(1) 将探查序列分两部分讨论：
(h + q2), (h + (q-1)2), …, (h+1), h 和 (h-1), (h-22), …, (h-q2)。
对于前一部分，设其通项为h + ( q – d )2, d = 0, 1, …, q，则相邻两个桶之间地址相减所得的差取模：
( h + (q – (d -1) )2 – ( h + (q – d )2 ) ) % m = ( (q – (d -1 ) )2 – (q – d )2 ) % m = (2*q -2*d +1) % m = ( m – 2*d ) % m. ( 代换 q = (m-1)/2 ) 代入 d = 1, 2, …, q，则可得到探查序列如下： m-2, m-4, m-6, …, 5, 3, 1。 ( m – 2*q = m – 2* (m-1)/2 = 1 ) 对于后一部分，其通项为h – ( q – d )2, d = q, q+1, …, 2q，则相邻两个桶之间地址相减所得的差取模： ( h – ( q – d )2 – ( h – ( q – (d+1) )2 ) ) % m = ( ( q – (d+1)2 – (q – d )2 ) % m
= ( 2*d – 2*q +1) % m = ( 2*d – m + 2) % m ( 代换 q = (m-1)/2 ) 代入 d = q, q+1, …, 2q-1，则可得到 2*d–m+2 = 2*q – m +2 = m – 1 – m +2 = 1, 2*d–m+2 = 2*q + 2 – m +2 = m – 1 + 2 – m +2 = 3, ……,
2*d–m+2 = 2*(2*q-1) – m +2 = 2*(m–1–1) – m + 2 = 2*m – 4 – m +2 = m – 2。〖证毕〗 (2) 编写算法
下面是使用二次探查法处理溢出时的散列表类的声明。
7
template
enum KindOfEntry { Active, Empty, Deleted }; ~HashTable ( ) { delete [ ] ht; } int Find ( const Type & x ); private:
struct HashEntry {
//散列表的表项定义
//表项分类 (活动 / 空 / 删) //析构函数 //在散列表中搜索x
//判散列表空否，空则返回1
HashTable ( ) : TableSize ( DefaultSize ) { AllocateHt ( ); CurrentSize = 0; } //构造函数 const HashTable & operator = ( const HashTable & ht2 ); //重载函数：表赋值
//散列表类的定义
int IsEmpty ( ) { return !CurrentSize ? 1 : 0; }
217
Type Element; KindOfEntry info;
//表项的数据, 即表项的关键码 //三种状态: Active, Empty, Deleted //表项构造函数
HashEntry ( ) : info (Empty ) { } };
enum { DefualtSize = 31; } HashEntry *ht; int TableSize; int CurrentSize;
HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) { }
//散列表存储数组
//数组长度，是满足4k+3的质数，k是整数 //已占据散列地址数目
//为散列表分配存储空间; //散列函数
void AllocateHt ( ) { ht = new HashEntry[TableSize ]; } int FindPos ( const Type & x ); };
template
return *this; }
template
//返回目标散列表结构指针
delete [ ] ht; TableSize = ht2.TableSize; AllocateHt ( ); //重新分配目标散列表存储空间 for ( int i = 0; i < TableSize; i++ ) ht[i] = ht2.ht[i]; CurrentSize = ht2.CurrentSize;
//从源散列表向目标散列表传送
//传送当前表项个数
//共有函数： 找下一散列位置的函数 int i = 0, q = ( TableSize -1 ) / 2, h0; int CurrentPos = h0 = HashPos ( x );
// i为探查次数
//利用散列函数计算x的散列地址 /搜索是否要求表项
}
if ( ht[CurrentPos].info == Active && ht[CurrentPos].Element == x ) return CurrentPos; else {
ht[CurrentPos].info = Active; ht[CurrentPos].Element = x; if ( ++CurrentSize < TableSize / 2 ) return CurrentPos;
//当前已有项数加1, 不超过表长的一半返回
218
//插入x
//返回桶号
if ( i <= q ) {
//求“下一个”桶
//实现取模
CurrentPos = h0 + (q - i ) * ( q - i );
while ( CurrentPos >= TableSize ) CurrentPos -= TableSize; } else {
CurrentPos = h0 - ( i -q ) * ( i - q );
while ( CurrentPos < 0 ) CurrentPos += TableSize; } i++;
//实现取模
while ( ht[CurrentPos].info != Empty && ht[CurrentPos].Element != x ) {