10-2设有10000个记录对象,通过分块划分为若干子表并建立索引,那么为了提高搜索效 率,每一个子表的大小应设计为多大? 【解答】每个子表的大小s=「n1=「1000=100个记录对象 0-4如果一个磁盘页块大小为1024(=1K)字节,存储的每个记录对象需要占用8字节,其 中关键码占4字节,其它数据占4字节。所有记录均已按关键码有序地存储在磁盘文件中, 每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存 放线性索引。试问 (1)若将线性索引常驻内存,文件中最多可以存放多少个记录? (2)如果使用二级索引,第二级索引占用1024字节(有128个索引项),这时文件中最 多可以存放多少个记录? 10-5假设在数据库文件中的每一个记录是由占397 Hello world! 2个字节的整型数关键码和一个变长的数据字段 组成。数据字段都是字符串。为了存放右面的那 This string is rather long 些记录,应如何组织线性索引? 1037 This is Shorter 222 Hello new World 10-7什么是倒排索引?针对10-6题给出的职工文件,试画出“性别”、“职业”的倒排索引 并说明如何利用它们解决诸如“职业为实验员和行政秘书的男性职工”等的查询,给出查询 步骤 记录地址职工号姓名性别 年龄月工资 0032034刘激扬匚男 880 实验员 教师 0176092卢声凯男教师|28 790 0212123 林德康男行政秘书33680 10248 140 熊南燕女 27 10284 实验员 0320 袁秋慧女 760 10-8倒排索引中的记录地址可以是记录的实际存放地址,也可以是记录的关键码。试比较 这两种方式的优缺点 10-9m=2的平衡m路搜索树是AL树,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树的变化
10-2 设有 10000 个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效 率, 每一个子表的大小应设计为多大? 【解答】每个子表的大小 s = n = 10000 = 100 个记录对象。 10-4 如果一个磁盘页块大小为 1024 (=1K) 字节，存储的每个记录对象需要占用 8 字节，其 中关键码占 4 字节，其它数据占 4 字节。所有记录均已按关键码有序地存储在磁盘文件中， 每个页块的第 1 个记录用于存放线性索引。另外在内存中开辟了 256K 字节的空间可用于存 放线性索引。试问： (1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？ (2) 如果使用二级索引，第二级索引占用 1024 字节（有 128 个索引项），这时文件中最 多可以存放多少个记录？ 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_树的变化。 397 Hello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello new World!
45) 8090 2535)(50(6070(85(95 55)(70(95 (b) 10-12对于一棵有199999个关键码的199阶B树,试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点) 10-13给定一组记录,其关键码为字符。记录的插入顺序为C,S,DTA,MPLB,W,N,G U,R,K,E,HO,L,丹},给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录 10-14设有一棵B+树,其内部结点最多可存放100个子女,叶结点最多可存储15个记录。 对于1,2,3,4,5层的B+树,最多能存储多少记录,最少能存储多少记录。 10-17设散列表为H∏13],散列函数为H(kgy)=key%13。用闭散列法解决冲突,对下列关 键码序列12,23,45,57,20,03,78,31,15,36造表 (1)采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度。 (2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下 个空位的公式为H1=(H1-1+RH(key)%13,H=H(key)。画出相应的散列表,并计算等概 率下搜索成功的平均搜索长度 【解答】 使用散列函数H(key)= key mod13,有 H(12)=12, H(45)=6 H(57)=5, H(20)=7, H(03)=3, H(78)=0, H(31)=5, H(36)=10 (1)利用线性探查法造表 搜索成功的平均搜索长度为 ASL=-(1+1+1+1+1+1+4+1+2+1)=14 搜索不成功的平均搜索长度为 SLm=1(+1+3+2+1+5+43+2+1+5+4+3)=36 (2)利用双散列法造表: Hi=(Hi-1+ RH (key)mod 13, H1=H(key) 15|03 574520313623 (1)(1)(1)(3)(5)(1) 搜索成功的平均搜索长度为 ASLsu= I 1+1+1+1+1+1+3+5+1+1)=16 10 10-18设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所 需记录的平均比较次数不超过2次。试问散列表需要设计多大?设a是散列表的装载因子
(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 10 (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 10 搜索不成功的平均搜索长度为 ASLunsucc = 1 13 (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 13 (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 10 (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 16 10 10-18 设有 150 个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所 需记录的平均比较次数不超过 2 次。试问散列表需要设计多大？ 设是散列表的装载因子
则有 【解答】 已知要存储的记录数为n=150,查找成功的平均查找长度为ASLa≤2,则有 ASLs ≤2,解得a≤2。又有=m=150≤2,则m222 n 10-19若设散列表的大小为m,利用散列函数计算出的散列地址为h=hash(x) (1)试证明:如果二次探查的顺序为(h+q),(h+(q-1)2)…;(h+1),h,(h-1),…(hv2), 其中,q=(m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2,m4,m6,…,5,3,1,1,3,5,…,m6,m-,m2 (2)编写一个算法,使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法,按给 定值x来搜索一个大小为m的散列表。如果ⅹ不在表中,则将它插入到表中。 10-22设有1000个值在1到10000的整数,试设计一个利用散列方法的算法,以最少的数 据比较次数和移动次数对它们进行排序 【解答】 10-23设有15000个记录需放在散列文件中,文件中每个桶内各页块采用链接方式连结,每 个页块可存放30个记录。若采用按桶散列,且要求搜索到一个已有记录的平均读盘时间不 超过1.5次,则该文件应设置多少个桶? 【解答】 已知用链地址法(开散列)解决冲突,搜索成功的平均搜索长度为1+α/2≤1.5,解出 a≤1,又a=n/m=15000/30/m=500/m≤1,m≥500。由此可知,该文件至少应设置 500个桶
则有 ASLsucc = + − 1 2 1 1 1 ( ) 【解答】 已知要存储的记录数为 n = 150，查找成功的平均查找长度为 ASLsucc 2，则有 ASLsucc = 1 2 1 1 1 + − 2，解得 2 3 。又有 = n m m = 150 2 3 ，则 m 225。 10-19 若设散列表的大小为 m，利用散列函数计算出的散列地址为 h = hash(x)： (1) 试证明：如果二次探查的顺序为(h + q 2 ), (h + (q-1)2 ), …, (h+1), h, (h-1), …, (h-q 2 )， 其中， 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 个桶