10-2 设有10000个记录对象,通过分块划分为若干子表并建立索引,那么为了提高搜索效率,每一个子表的大小应设计为多大?
【解答】每个子表的大小 s = (n( = (10000( = 100 个记录对象。
10-4 如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用8字节，其中关键码占4字节，其它数据占4字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：
(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？
(2) 如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？
397
Hello World!
82
XYZ
1038
This string is rather long
1037
This is Shorter
42
ABC
2222
Hello new World!
10-5 假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？
10-7 什么是倒排索引？针对10-6题给出的职工文件，试画出“性别”、“职业”的倒排索引，并说明如何利用它们解决诸如“职业为实验员和行政秘书的男性职工”等的查询，给出查询步骤。
记录地址
职工号
姓 名
性别
职 业
年龄
月工资
10032
034
刘激扬
男
教 师
29
820
10068
064
蔡晓莉
女
教 师
32
880
10104
073
朱 力
男
实验员
26
640
10140
081
洪 伟
男
教 师
36
945
10176
092
卢声凯
男
教 师
28
790
10212
123
林德康
男
行政秘书
33
680
10248
140
熊南燕
女
教 师
27
720
10284
175
吕 颖
女
实验员
28
620
10320
209
袁秋慧
女
教 师
24
760
10-8 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。
10-9 m = 2的平衡m路搜索树是AVL树，m = 3的平衡m路搜索树是2-3树。它们的叶结点必须在同一层吗？m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树一定是B_树吗？为什么？
【解答】m = 3的平衡m路搜索树的叶结点不一定在同一层，而m阶B_树的叶结点必须在同一层，所以m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树不一定是B_树。
10-10 下图(a)是一个3阶B_树。试分别画出在插入65、15、40、30之后B_树的变化。
10-11 下图(b)是一个3阶B_树。试分别画出在删除50、40之后B_树的变化。
(a) (b)
10-12 对于一棵有1999999个关键码的199阶B_树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。
10-13 给定一组记录，其关键码为字符。记录的插入顺序为{C,S,D,T,A,M,P,I,B,W,N,G,U,R,K,E,H,O,L,J}，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。
10-14 设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1,2,3,4,5层的B+树，最多能存储多少记录，最少能存储多少记录。
10-17设散列表为HT[13],散列函数为 H (key) = key %13。用闭散列法解决冲突,对下列关键码序列 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)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =
搜索不成功的平均搜索长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =
(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) mod 13,H1 = H (key)
0
1
2
3
4
5
6
7
8
9
10
11
12
78
15
03
57
45
20
31
36
23
12
(1)
(1)
(1)
(1)
(1)
(1)
(3)
(5)
(1)
(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =
10-18 设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设(是散列表的装载因子，则有
【解答】
已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc ( 2，则有ASLsucc =( 2，解得 ( (。又有( = ( ，则 m ( 225。
10-19 若设散列表的大小为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不在表中，则将它插入到表中。
10-22 设有1000个值在1到10000的整数，试设计一个利用散列方法的算法，以最少的数据比较次数和移动次数对它们进行排序。
【解答】
10-23 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？
【解答】
已知用链地址法（开散列）解决冲突，搜索成功的平均搜索长度为1+α/2≤1.5，解出α≤1，又α= n / m = 15000 / 30 / m = 500 / m ≤1，m≥500。由此可知，该文件至少应设置500个桶。
【解答】每个子表的大小 s = (n( = (10000( = 100 个记录对象。
10-4 如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用8字节，其中关键码占4字节，其它数据占4字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：
(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？
(2) 如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？
397
Hello World!
82
XYZ
1038
This string is rather long
1037
This is Shorter
42
ABC
2222
Hello new World!
10-5 假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？
10-7 什么是倒排索引？针对10-6题给出的职工文件，试画出“性别”、“职业”的倒排索引，并说明如何利用它们解决诸如“职业为实验员和行政秘书的男性职工”等的查询，给出查询步骤。
记录地址
职工号
姓 名
性别
职 业
年龄
月工资
10032
034
刘激扬
男
教 师
29
820
10068
064
蔡晓莉
女
教 师
32
880
10104
073
朱 力
男
实验员
26
640
10140
081
洪 伟
男
教 师
36
945
10176
092
卢声凯
男
教 师
28
790
10212
123
林德康
男
行政秘书
33
680
10248
140
熊南燕
女
教 师
27
720
10284
175
吕 颖
女
实验员
28
620
10320
209
袁秋慧
女
教 师
24
760
10-8 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。
10-9 m = 2的平衡m路搜索树是AVL树，m = 3的平衡m路搜索树是2-3树。它们的叶结点必须在同一层吗？m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树一定是B_树吗？为什么？
【解答】m = 3的平衡m路搜索树的叶结点不一定在同一层，而m阶B_树的叶结点必须在同一层，所以m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树不一定是B_树。
10-10 下图(a)是一个3阶B_树。试分别画出在插入65、15、40、30之后B_树的变化。
10-11 下图(b)是一个3阶B_树。试分别画出在删除50、40之后B_树的变化。
(a) (b)
10-12 对于一棵有1999999个关键码的199阶B_树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。
10-13 给定一组记录，其关键码为字符。记录的插入顺序为{C,S,D,T,A,M,P,I,B,W,N,G,U,R,K,E,H,O,L,J}，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。
10-14 设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1,2,3,4,5层的B+树，最多能存储多少记录，最少能存储多少记录。
10-17设散列表为HT[13],散列函数为 H (key) = key %13。用闭散列法解决冲突,对下列关键码序列 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)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =
搜索不成功的平均搜索长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =
(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) mod 13,H1 = H (key)
0
1
2
3
4
5
6
7
8
9
10
11
12
78
15
03
57
45
20
31
36
23
12
(1)
(1)
(1)
(1)
(1)
(1)
(3)
(5)
(1)
(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =
10-18 设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设(是散列表的装载因子，则有
【解答】
已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc ( 2，则有ASLsucc =( 2，解得 ( (。又有( = ( ，则 m ( 225。
10-19 若设散列表的大小为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不在表中，则将它插入到表中。
10-22 设有1000个值在1到10000的整数，试设计一个利用散列方法的算法，以最少的数据比较次数和移动次数对它们进行排序。
【解答】
10-23 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？
【解答】
已知用链地址法（开散列）解决冲突，搜索成功的平均搜索长度为1+α/2≤1.5，解出α≤1，又α= n / m = 15000 / 30 / m = 500 / m ≤1，m≥500。由此可知，该文件至少应设置500个桶。
