第10章索引与散列 第10章索引与散列 10-1什么是静态索引结构?什么是动态索引结构?它们各有哪些优缺点? 【解答】 静态索引结构指这种索引结构在初始创建,数据装入时就已经定型,而且在整个系统运 行期间,树的结构不发生变化,只是数据在更新。动态索引结构是指在整个系统运行期间 树的结构随数据的增删及时调整,以保持最佳的搜索效率。静态索引结构的优点是结构定型, 建立方法简单,存取方便:缺点是不利于更新,插入或删除时效率低。动态索引结构的优点 是在插入或删除时能够自动调整索引树结构,以保持最佳的搜索效率:缺点是实现算法复杂 10-2设有10000个记录对象,通过分块划分为若干子表并建立索引,那么为了提高搜索效 率,每一个子表的大小应设计为多大? 【解答】 每个子表的大小s=「n1=「10000=100个记录对象 10-3如果一个磁盘页块大小为1024(=1K)字节,存储的每个记录对象需要占用16字节, 其中关键码占4字节,其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件 中,每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用 于存放线性索引。试问 (1)若将线性索引常驻内存,文件中最多可以存放多少个记录?(每个索引项8字节,其 中关键码4字节,地址4字节) (2)如果使用二级索引,第二级索引占用1024字节(有128个索引项),这时文件中最 多可以存放多少个记录? 【解答】 (1)因为一个磁盘页块大小为1024字节,每个记录对象需要占用16字节,则每个页块 可存放1024/16=64个记录,除第一个记录存储线性索引外,每个页块可存储63个记录对 象。又因为在磁盘文件中所有记录对象按关键码有序存储,所以线性索引可以是稀疏索引 每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常驻内存,那么它最 多可存放256*(1024/8)=256*128=32768个索引项,文件中可存放32768*63 2064384个记录对象。 (2)由于第二级索引占用1024个字节,内存中还剩255K字节用于第一级索引。第 级索引有255*128=32640个索引项,作为稀疏索引,每个索引项索引一个页块,则索引文 件中可存放32640*63=2056320 10-4假设在数据库文件中的每一个记录是由占2个字节 Hello world 的整型数关键码和一个变长的数据字段组成。数据字段都 是字符串。为了存放右面的那些记录,应如何组织线性索 1038 This string is rather lon 【解答】 37 This is Shorter 将所有字符串依加入的先后次序存放于一个连续的 存储空间 store中,这个空间也叫做“堆”,它是存放所有 字符串的顺序文件。它有一个指针free,指示在堆 store中当前可存放数据的开始地址。初 始时free置为0,表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键 码,字符串在 store中的起始地址和字符串的长度: 索引表ID
第 10 章 索引与散列 1 第 10 章 索引与散列 10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？ 【解答】 静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运 行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间， 树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型， 建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点 是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。 10-2 设有 10000 个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效 率, 每一个子表的大小应设计为多大? 【解答】 每个子表的大小 s = n = 10000 = 100 个记录对象。 10-3 如果一个磁盘页块大小为 1024 (=1K) 字节，存储的每个记录对象需要占用 16 字节， 其中关键码占 4 字节，其它数据占 12 字节。所有记录均已按关键码有序地存储在磁盘文件 中，每个页块的第 1 个记录用于存放线性索引。另外在内存中开辟了 256K 字节的空间可用 于存放线性索引。试问： (1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项 8 字节，其 中关键码 4 字节，地址 4 字节) (2) 如果使用二级索引，第二级索引占用 1024 字节（有 128 个索引项），这时文件中最 多可以存放多少个记录？ 【解答】 (1) 因为一个磁盘页块大小为 1024 字节，每个记录对象需要占用 16 字节，则每个页块 可存放 1024 / 16 = 64 个记录，除第一个记录存储线性索引外，每个页块可存储 63 个记录对 象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引， 每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常驻内存，那么它最 多可存放 256 * (1024 / 8 ) = 256 * 128 = 32768 个索引项，文件中可存放 32768 * 63 = 2064384 个记录对象。 (2) 由于第二级索引占用 1024 个字节，内存中还剩 255K 字节用于第一级索引。第一 级索引有 255 * 128 = 32640 个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文 件中可存放 32640 * 63 = 2056320。 10-4 假设在数据库文件中的每一个记录是由占 2 个字节 的整型数关键码和一个变长的数据字段组成。数据字段都 是字符串。为了存放右面的那些记录，应如何组织线性索 引？ 【解答】 将所有字符串依加入的先后次序存放于一个连续的 存储空间 store 中，这个空间也叫做“堆”，它是存放所有 字符串的顺序文件。它有一个指针 free，指示在堆 store 中当前可存放数据的开始地址。初 始时 free 置为 0，表示可从文件的 0 号位置开始存放。线性索引中每个索引项给出记录关键 码，字符串在 store 中的起始地址和字符串的长度： 索引表 ID 堆 store 397 Hello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello new World!
第10章索引与散列 关键码串长度|串起始地 Hello World! XYZ This string is rather long This is Shorter a BC hello new World 397 1037 59 10-5设有一个职工文件 记录地址职工 刘激扬 10068 蔡晓莉 1200.00 10104 实验员 480.00 10140 1400.00 行政秘书 南燕 实验员 1032020 袁秋慧 0.00 其中,关键码为职工号。试根据此文件,对下列查询组织主索引和倒排索引,再写出搜 索结果关键码。(1)男性职工:(2)月工资超过800元的职工;(3)月工资超过平均工资的职 工;(4)职业为实验员和行政秘书的男性职工;(5)男性教师或者年龄超过25岁且职业为实 验员和教师的女性职工 【解答】 主索引 月工资倒排索引 职务倒排索引 10104 10140 10176 12310212 10248 780 实验员2073 175 064 200 0320[1400I Os-[政秘书 性别倒排索引 年龄倒排索引 年龄长 指针 175 女 064 034
第 10 章 索引与散列 2 关键码 串长度 串起始地址 0 Hello World! XYZ This string is rather long This 42 3 56 82 3 12 is Shorter ABC Hello new World! 397 12 0 1037 15 41 1038 26 15 2222 16 59 10-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 岁且职业为实 验员和教师的女性职工。 【解答】 主索引 月工资 倒排索引 职务 倒排索引 职工号 记录地址 月工资 长度 指针 职务 长度 指针 0 034 10032 480. 3 073 教师 6 034 1 064 10068 123 064 2 073 10104 175 081 3 081 10140 720. 3 034 092 4 092 10176 092 140 5 123 10212 209 209 6 140 10248 780. 1 140 实验员 2 073 7 175 10284 1200. 1 064 175 8 209 10320 1400. 1 081 行政秘书 1 123 性别 倒排索引 年龄 倒排索引 性别 长度 指针 年龄 长度 指针 男 5 034 24 1 209 073 26 1 073 081 27 1 140 092 28 2 092 123 175 女 4 064 29 1 034 free
第10章索引与散列 搜索结果 (1)男性职工(搜索性别倒排索引):{034,073,081,092,123} (2)月工资超过800元的职工(搜索月工资倒排索引):{064,081} 3)月工资超过平均工资的职工(搜索月工资倒排索引){月平均工资776元}: {064,081,140} (4)职业为实验员和行政秘书的男性职工(搜索职务和性别倒排索引): 073,123,175}&&{034,073,081,092,123}={073,123} (5)男性教师(搜索性别与职务倒排索引) 034,073,081,092,123}&&{034,064,081,092,140,209}={034,081,092} 年龄超过25岁且职业为实验员和教师的女性职工(搜索性别、职务和年龄倒排索引) {064,140,175,209}&&{034,064,073,081,092,140,175,209}&&{034,064,073, 081092,123,140,175}={064,140,175} 10-6倒排索引中的记录地址可以是记录的实际存放地址,也可以是记录的关键码。试比较 这两种方式的优缺点 【解答】 在倒排索引中的记录地址用记录的实际存放地址,搜索的速度快:但以后在文件中插入 或删除记录对象时需要移动文件中的记录对象,从而改变记录的实际存放地址,这将对所有 的索引产生影响:修改所有倒排索引的指针,不但工作量大而且容易引入新的错误或遗漏 使得系统不易维护 记录地址采用记录的关键码,缺点是寻找实际记录对象需要再经过主索引,降低了搜索 速度:但以后在文件中插入或删除记录对象时,如果移动文件中的记录对象,导致许多记录 对象的实际存放地址发生变化,只需改变主索引中的相应记录地址,其他倒排索引中的指针 一律不变,使得系统容易维护,且不易产生新的错误和遗漏 10-7m=2的平衡m路搜索树是AVL树,m=3的平衡m路搜索树是2-3树。它们的叶结 点必须在同一层吗?m阶B树是平衡m路搜索树,反过来,平衡m路搜索树一定是B树吗? 为什么? 【解答】 m=3的平衡m路搜索树的叶结点不一定在同一层,而m阶B树的叶结点必须在同一 层,所以m阶B树是平衡m路搜索树,反过来,平衡m路搜索树不一定是B树。 10-8下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化 45 8019 6070 【解答】 插入65后 5580
第 10 章 索引与散列 3 140 32 1 064 175 33 1 123 209 36 1 081 搜索结果： (1) 男性职工 (搜索性别倒排索引)：{034, 073, 081, 092, 123} (2) 月工资超过 800 元的职工 (搜索月工资倒排索引)：{064, 081} (3) 月工资超过平均工资的职工(搜索月工资倒排索引) {月平均工资 776 元}： {064, 081, 140} (4) 职业为实验员和行政秘书的男性职工(搜索职务和性别倒排索引)： {073, 123, 175} && {034, 073, 081, 092, 123} = {073, 123} (5) 男性教师 (搜索性别与职务倒排索引)： {034, 073, 081, 092, 123} && { 034, 064, 081, 092, 140, 209} = {034, 081, 092} 年龄超过 25 岁且职业为实验员和教师的女性职工 (搜索性别、职务和年龄倒排索引)： {064, 140, 175, 209} && {034, 064, 073, 081, 092, 140, 175, 209} && {034, 064, 073, 081,092, 123, 140, 175} = {064, 140, 175} 10-6 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较 这两种方式的优缺点。 【解答】 在倒排索引中的记录地址用记录的实际存放地址，搜索的速度快；但以后在文件中插入 或删除记录对象时需要移动文件中的记录对象，从而改变记录的实际存放地址，这将对所有 的索引产生影响：修改所有倒排索引的指针，不但工作量大而且容易引入新的错误或遗漏， 使得系统不易维护。 记录地址采用记录的关键码，缺点是寻找实际记录对象需要再经过主索引，降低了搜索 速度；但以后在文件中插入或删除记录对象时，如果移动文件中的记录对象，导致许多记录 对象的实际存放地址发生变化，只需改变主索引中的相应记录地址，其他倒排索引中的指针 一律不变，使得系统容易维护，且不易产生新的错误和遗漏。 10-7 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-8 下图是一个 3 阶 B 树。试分别画出在插入 65、15、40、30 之后 B 树的变化。 【解答】 插入 65 后： 45 80 90 25 35 50 60 70 85 95 55 55 80
第10章索引与散列 253 插入15后 插入40后 5、80 25145 651 插入30后 53 65 90 10-9下图是一个3阶B树。试分别画出在删除50、40之后B树的变化 50 70 【解答】 删除50后 80 删除
第 10 章 索引与散列 4 插入 15 后： 插入 40 后： 插入 30 后： 10-9 下图是一个 3 阶 B 树。试分别画出在删除 50、40 之后 B 树的变化。 【解答】 删除 50 后： 删除 40 后： 45 25 35 50 60 70 85 95 65 90 50 85 95 55 80 60 70 65 90 15 35 25 45 50 85 95 55 80 60 70 65 90 15 25 45 35 40 45 35 80 55 30 40 25 65 90 15 50 60 70 85 95 30 60 80 20 40 55 70 95 50 30 80 20 40 60 70 95 55
第10章索引与散列 [c0 10-10对于一棵有199999关键码的199阶B树,试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点) 【解答】 设B树的阶数m=199,则m/21=100。若不包括失败结点层,则其最大层数为 Llogrm/(N+1)2)+1=lg0010000001=4 若使得每一层关键码数达到最大,可使其层数达到最小。第0层最多有(m-1)个关键码,第 1层最多有(m-1)2个关键码,…,第h1层最多有(m-1)个关键码。层数为h的B树最多有 (m-1)+(m-1)2+…+(m-1)1=(m-1)(m-1)-1)/(m-2)个关键码。反之,若有n个关键 码,n≤(m-1)((m-1)-1)/(m-2),则h≥ log(m-)(n(m-2)/(m-1)+1),所以,有199999 个关键码的199阶B树的最小层数为 「 log (m-1)(n(m-2)(m-1)+1)1=「log198(199197/198+1)1=Iog1819898991 10-11给定一组记录,其关键码为字符。记录的插入顺序为{C,S,D,T,AMP,L,B,W,N,G, U,R,K,E,HO,LJ},给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录 【解答】 插入C,S,D插入T 插入A 插入M CDS ST A C 插入P 插入I DMS DMP ST A C I AP ST 插入B,WN,G 插入U IDMS ABCIDGIMNPI IST ABCIDGI ANPIST UW 插入R PR 插入K
第 10 章 索引与散列 5 10-10 对于一棵有 1999999 个关键码的 199 阶 B 树，试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点)。 【解答】 设 B 树的阶数 m = 199，则m/2 = 100。若不包括失败结点层，则其最大层数为 logm/2 ((N+1)/2) + 1 = log100 1000000 +1 = 4 若使得每一层关键码数达到最大，可使其层数达到最小。第 0 层最多有(m-1)个关键码，第 1 层最多有(m-1)2 个关键码，，第 h-1 层最多有(m-1)h 个关键码。层数为 h 的 B 树最多有 (m-1) + (m-1)2 + … + (m-1)h-1 = (m-1) ( (m-1)h – 1 ) / (m-2)个关键码。反之，若有 n 个关键 码，n ≤ (m-1) ( (m-1)h – 1 ) / (m-2)，则 h ≥ log (m-1) (n(m-2)/(m-1)+1)，所以，有 1999999 个关键码的 199 阶 B 树的最小层数为 log (m-1) (n*(m-2)/(m-1)+1) = log198 (1999999*197 / 198 +1) = log 198 1989899 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 插入 P 插入 I 插入 B, W, N, G 插入 U 插入 R 插入 K 55 80 20 30 60 70 95 C D S C D S T S A C D S T S A C D S D M S T A C D S D M P S T A C D M S D I M P S T A B C D M S D G I M N P S T W A B C D M S U D G I M N P S T U W A B C D M D G I M N P R S T U W S U P P
第10章索引与散列 ABC DG K MN PR ST Uw 插入E U ABCIIDEG IK MN ST U 插入H GIM PR 插入O,L ABCIDE GH MNOIPR ST 插入J ABCDE GH L MNO 10-12设有一棵B+树,其内部结点最多可存放100个子女,叶结点最多可存储15个记录 对于1,2,3,4,5层的B+树,最多能存储多少记录,最少能存储多少记录 【解答】 层B+树:根据B+树定义,一层B+树的结点只有一个,它既是根结点又是叶结点 最多可存储m1=15个记录,最少可存储「m1/21=8个记录。 二层B+树:第0层是根结点,它最多有m=100棵子树,最少有2个结点;第1层是 叶结点,它最多有m个结点,最多可存储m*m1=100*15=1500个记录,最少有2个结点, 最少可存储2*m1/21=16个记录 三层B+树:第2层是叶结点。它最多有m2个结点,最多可存储m2*m1=15000个记 录。最少有2*「m/21=100个结点,最少可存储2*「m/21*「m1/21=800个记录 四层B+树:第3层是叶结点。它最多有m3个结点,可存储m3*m1=15000000个记录 最少有2*「m/212=2*502=5000个结点,存储2*「m/212*「m121=4000个记录。 五层B+树:第4层是叶结点。它最多有m4个结点,可存储m4*m1=15000000个记
第 10 章 索引与散列 6 插入 E 插入 H 插入 O, L 插入 J 10-12 设有一棵 B+树，其内部结点最多可存放 100 个子女，叶结点最多可存储 15 个记录。 对于 1, 2, 3, 4, 5 层的 B+树，最多能存储多少记录，最少能存储多少记录。 【解答】 一层 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 个记 A B C D I M D G M N S U I K P R S T U W A B C D I M D E G M N S U P I K P R S T U W A B C D G I M D E M N S U P G H I K P R S T U W D E M N O S U P G H P R S T A B C I K L U W D G I M D E M N O S U I P G H P R S T A B C I J K L D G U W K M
第10章索引与散列 录。最少有2*「m/213=2*503=25000个结点,存储2*「m213*「m1/21=200000个记录 10-13设散列表为H13],散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关 键码序列12,23,45,57,20,03,78,31,15,36造表 (1)采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度 (2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下 个空位的公式为H=(H-1+RH(key)%13,H=H(key)。画出相应的散列表,并计算等概 率下搜索成功的平均搜索长度。 【解答】 使用散列函数H(key)= key mod13,有 H(23)=10 H(45)=6, H(20)=7, H(03)=3 H(78)=0 H(31)= H(15)=2 H(36)=10 (1)利用线性探查法造表: 1503 57452031 3612 (1)(1) (1)(1)(1)(4) (1)(2)(1) 搜索成功的平均搜索长度为 As1、(1+1+1+1+1+1+4+1+2+1)= 10 搜索不成功的平均搜索长度为 aslunsu (2+1+3+2+1+5+4+3+2+1+5+4+3)= (2)利用双散列法造 Hi=(Hi-1+ RH(key))%13, H1=H(key) 8 15035745203136231 (1) (1)(1) (1)(1)(1)(3)(5)(1) (1) 搜索成功的平均搜索长度为 ALoud=;(1+1+1+1+1+1+3+5+1+16 10-14设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所 需记录的平均比较次数不超过2次。试问散列表需要设计多大?设a是散列表的装载因子, 则有 ASL 【解答】 已知要存储的记录数为n=150,查找成功的平均查找长度为 ASLs≤2,则有 ASLs 1(1+-1)≤2,解得a≤2。又有a==150≤2,则m225 10-15若设散列表的大小为m,利用散列函数计算出的散列地址为h= hash(x) (1)试证明:如果二次探查的顺序为(h+q2),(h+(q-1)2)…,(h+1,h,(h-1)…(h-q), 其中,q=(m-l)2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2,m-4,m-6,…,5,3,l,1,3,5,…;,m-6,m-4,m-2 (2)编写一个算法,使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法,按给 7
第 10 章 索引与散列 7 录。最少有 2* m/2 3 = 2 * 503 = 250000 个结点，存储 2* m/2 3 * m1/2 = 2000000 个记录。 10-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)。画出相应的散列表, 并计算等概 率下搜索成功的平均搜索长度。 【解答】 使用散列函数 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)) % 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-14 设有 150 个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所 需记录的平均比较次数不超过 2 次。试问散列表需要设计多大？ 设是散列表的装载因子， 则有 ) 1 1 (1 2 1 ASLsucc − = + 【解答】 已知要存储的记录数为 n = 150，查找成功的平均查找长度为 ASLsucc 2，则有 ASLsucc = 1 2 1 1 1 + − 2，解得 2 3 。又有 = n m m = 150 2 3 ，则 m 225。 10-15 若设散列表的大小为 m，利用散列函数计算出的散列地址为 h = hash(x)。 (1) 试证明：如果二次探查的顺序为(h + q2 ), (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)和二次探查解决冲突的方法，按给
第10章索引与散列 定值x来搜索一个大小为m的散列表。如果x不在表中,则将它插入到表中。 【解答】 (1)将探查序列分两部分讨论: (h+q2),(h+(q-1)2),…,(h+1),h和(h-1),(h-2),…,(h-q2)。 对于前一部分,设其通项为h+(q-d),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,则可得到探查序列如下 对于后一部分,其通项为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, 2d-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=2m-4-m+2=m-2。〖证毕〗 (2)编写算法 下面是使用二次探查法处理溢出时的散列表类的声明。 template class Hash Table i /散列表类的定义 enum KindofEntry Active, Empty, Deleted 3: ∥表项分类(活动/空/删) HashTable(): Tables ize( DefaultS ize){ Allocate(; Currentsize=0;}∥构造函数 - HashTable (i delete [ht; ∥析构函数 const hashTable& operator=( const hashTable&h2);∥重载函数:表赋值 int Find( const Type &x ); ∥在散列表中搜索 int IsEmpty(return I CurrentSize ?1: 0; 3 ∥判散列表空否,空则返回1 priva struct HashEntry i 散列表的表项定义 pe Element; ∥表项的数据,即表项的关键码 KindofEntry info; 三种状态: Active, Empty, Deleted HashEntry () info(Empty) ∥表项构造函数 }; HashEntry *ht; /散列表存储数组 ∥数组长度,要求是满足4k+3的质数,k是整数 已占据散列地址数目 void AllocateHt){ht= new HashEntry[ Tablesize;}∥为散列表分配存储空间; nt FindPos( const Type &x ) /散列函数 template const Hash Table& Hash Table&ht2)i ∥重载函数:复制一个散列表h2
第 10 章 索引与散列 8 定值 x 来搜索一个大小为 m 的散列表。如果 x 不在表中，则将它插入到表中。 【解答】 (1) 将探查序列分两部分讨论： (h + q2 ), (h + (q-1)2 ), …, (h+1), h 和 (h-1), (h-2 2 ), …, (h-q 2 )。 对于前一部分，设其通项为 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) 编写算法 下面是使用二次探查法处理溢出时的散列表类的声明。 template class HashTable { //散列表类的定义 public: enum KindOfEntry { Active, Empty, Deleted }; //表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) { AllocateHt ( ); CurrentSize = 0; } //构造函数 ~HashTable ( ) { delete [ ] ht; } //析构函数 const HashTable & operator = ( const HashTable & ht2 ); //重载函数：表赋值 int Find ( const Type & x ); //在散列表中搜索 x int IsEmpty ( ) { return !CurrentSize ? 1 : 0; } //判散列表空否，空则返回 1 private: struct HashEntry { //散列表的表项定义 Type Element; //表项的数据, 即表项的关键码 KindOfEntry info; //三种状态: Active, Empty, Deleted HashEntry ( ) : info (Empty ) { } //表项构造函数 HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) { } }; enum { DefualtSize = 31; } HashEntry *ht; //散列表存储数组 int TableSize; //数组长度，要求是满足 4k+3 的质数，k 是整数 int CurrentSize; //已占据散列地址数目 void AllocateHt ( ) { ht = new HashEntry[TableSize ]; } //为散列表分配存储空间; int FindPos ( const Type & x ); //散列函数 }; template const HashTable & HashTable :: operator = ( const HashTable &ht2 ) { //重载函数：复制一个散列表 ht2
第10章索引与散列 if( this I=&ht2)t delete]ht; Tables ize=ht2. Tablesize; Allocate(;∥重新分配目标散列表存储空间 for int i=0; i int Hash Table: Find const Type&x)( ∥共有函数:找下一散列位置的函数 int i=0, q=( TableSize-1)/2, h0 ∥i为探查次数 int Current Pos=h0= HashPos(x ); ∥利用散列函数计算x的散列地址 while(ht[CurrentPos] info I= Empty & ht( CurrentPos) Element I=x)( /搜索是否要求表项 ∥求“下一个”桶 CurrentPos =h0+( q-1)*(q-1) while( Current Pos>= Tables ize) CurrentPos-= Tablesize;∥实现取模 CurrentPos=h0-(1-q)*(1-9) while( CurrentPos N的质数,设N>=5 if(N%2=0)N++; 偶数不是质数 for(: !IsPrime(N: N+=2); 寻找质数
第 10 章 索引与散列 9 if ( this != &ht2 ) { delete [ ] ht; TableSize = ht2.TableSize; AllocateHt ( ); //重新分配目标散列表存储空间 for ( int i = 0; i int HashTable :: Find ( const Type& x ) { //共有函数： 找下一散列位置的函数 int i = 0, q = ( TableSize -1 ) / 2, h0; // i 为探查次数 int CurrentPos = h0 = HashPos ( x ); //利用散列函数计算 x 的散列地址 while ( ht[CurrentPos].info != Empty && ht[CurrentPos].Element != x ) { /搜索是否要求表项 if ( i = TableSize ) CurrentPos -= TableSize; //实现取模 } else { CurrentPos = h0 - ( i -q ) * ( i - q ); while ( CurrentPos N 的质数，设 N >= 5 if ( N % 2 == 0 ) N++; //偶数不是质数 for ( ; !IsPrime (N); N += 2 ); //寻找质数
int Is Prime( intN)i 测试N是否质数 for(inti=3;i #include l while( ink=j;k>1: k--) t ht[k]. Element=ht(k-1].Element; ht[k]. info= htk-1]. info; 3 hto Element =id; htO info= Active 插入
第 10 章 索引与散列 10 return N; } int IsPrime ( int N ) { //测试 N 是否质数 for ( int i = 3; i*i #include #include class HashTable { //散列表类定义 public: enum KindOfEntry { Active, Empty, Deleted }; //表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) { ht = new HashEntry[TableSize]; } //构造函数 ~HashTable ( ) { delete [ ] ht; } //析构函数 int Find-Ins ( const char * id ); //在散列表中搜索标识符 id void HashSort ( ); private: struct HashEntry { //表项定义 Type Element; //表项的数据, 即表项的关键码 KindOfEntry info; //三种状态: Active, Empty, Deleted HashEntry ( ) : info (Empty ) { } //表项构造函数, 置空 }; HashEntry *ht; //散列表存储数组 int TableSize; //最大桶数 int FindPos ( string s) const { return atoi (*s) - 32; } //散列函数 } int HashTable :: Find-Ins ( const char * id ) { int i = FindPos ( id ), j = i; //i 是计算出来的散列地址 while ( ht[j].info != Empty && strcmp ( ht[j].Element, id ) != 0 ) { //冲突 j = ( j + 1 ) % TableSize; //当做循环表处理, 找下一个空桶 if ( j == i ) return -TableSize; //转一圈回到开始点, 表已满, 失败 } if ( ht[j].info != Active ) { //插入 if ( j > i ) { while ( int k = j; k > i; k-- ) { ht[k].Element = ht[k-1].Element; ht[k].info = ht[k-1].info; } ht[i].Element = id; ht[i].info = Active; //插入 } else { HashEntry temp;
