11-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？
11-2 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效率, 每一个子表的大小应设计为多大?
11-3如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用16字节，其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：
(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)
(2) 如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？
|
397 |
Hello World! |
|
82 |
XYZ |
|
1038 |
This string is rather long |
|
1037 |
This is Shorter |
|
42 |
ABC |
|
2222 |
Hello new World! |
11-4 假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？
11-5 设有一个职工文件：
|
记录地址 |
职工号 |
姓 名 |
性别 |
职 业 |
年龄 |
籍贯 |
月工资(元) |
|
10032 |
034 |
刘激扬 |
男 |
教 师 |
29 |
山东 |
720.00 |
|
10068 |
064 |
蔡晓莉 |
女 |
教 师 |
32 |
辽宁 |
1200.00 |
|
10104 |
073 |
朱 力 |
男 |
实验员 |
26 |
广东 |
480.00 |
|
10140 |
081 |
洪 伟 |
男 |
教 师 |
36 |
北京 |
1400.00 |
|
10176 |
092 |
卢声凯 |
男 |
教 师 |
28 |
湖北 |
720.00 |
|
10212 |
123 |
林德康 |
男 |
行政秘书 |
33 |
江西 |
480.00 |
|
10248 |
140 |
熊南燕 |
女 |
教 师 |
27 |
上海 |
780.00 |
|
10284 |
175 |
吕 颖 |
女 |
实验员 |
28 |
江苏 |
480.00 |
|
10320 |
209 |
袁秋慧 |
女 |
教 师 |
24 |
广东 |
720.00 |
其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜索结果关键码。(1) 男性职工；(2) 月工资超过800元的职工；(3) 月工资超过平均工资的职工；(4) 职业为实验员和行政秘书的男性职工；(5) 男性教师或者年龄超过25岁且职业为实验员和教师的女性职工。
11-6 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。
11
11-8 下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化。
11-9 下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。
11-10 对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。
11-11 给定一组记录，其关键码为字符。记录的插入顺序为 { C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J }，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。
11-12 设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1, 2, 3, 4, 5层的B+树，最多能存储多少记录，最少能存储多少记录。
11-13设散列表为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)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
11-14 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设a是散列表的装载因子，则有
11-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不在表中，则将它插入到表中。
11-16 编写一个算法，以字典顺序输出散列表中的所有标识符。设散列函数为hash(x) = x中的第一个字符，采用线性探查法来解决冲突。试估计该算法所需的时间。
11-17 设有1000个值在1到10000的整数，试设计一个利用散列方法的算法，以最少的数据比较次数和移动次数对它们进行排序。
11-18 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？
11-19 用可扩充散列法组织文件时，若目录深度为d，指向某个页块的指针有n个，则该页块的局部深度有多大？
11-20 设一组对象的关键码为 { 69, 115, 110, 255, 185, 143, 208, 96, 63, 175, 160, 99, 171, 137, 149, 229, 167, 121, 204, 52, 127, 57, 1040 }。要求用散列函数将这些对象的关键码转换成二进制地址，存入用可扩充散列法组织的文件里。定义散列函数为hash(key) = key % 64, 二进制地址取6位。设每个页块可容纳4个对象。要求按10 .4节介绍的方法设置目录表的初始状态，使目录表的深度为3。然后按题中所给的顺序，将各个对象插入的可扩充散列文件中。试画出每次页块分裂或目录扩充时的状态和文件的最后状态。