数据结构习题解析第10章

第10章 索引与散列

一、复习要点

索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。

1、基本知识点

要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括B树的搜索、插入、删除，通过关键码个数估算B树的高度的方法；B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。

二、难点与重点

1、线性索引

? 密集索引、稀疏索引、索引表计算

? 基于属性查找建立倒排索引、单元式倒排表 2、动态搜索树

? 平衡的m路搜索树的定义、搜索算法

? B树的定义、B树与平衡的m路搜索树的关系

? B树的插入(包括结点分裂)、删除(包括结点调整与合并)方法 ? B树中结点个数与高度的关系

? B+树的定义、搜索、插入与删除的方法 3、散列表

? 散列函数的比较

? 装载因子 ? 与平均搜索长度的关系，平均搜索长度的关系 ? 表长m、表中已有数据对象个数n和装载因子的关系

? 解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算

? 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 ? 线性探查法中的堆积聚集问题

? 解决冲突的(闭散列)双散列法的运用，平均探查次数计算

? 双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜 ? 解决冲突的(闭散列)二次散列法的运用，平均探查次数计算 ? 注意：二次散列法中装载因子?与表长m的设置

? 解决冲突的(开散列)开散列法的运用，平均探查次数计算 ? 由平均探查次数计算装载因子?，再计算表大小的方法

三、教材中习题的解析

10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？ 【解答】

209

静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。

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个字节 397 Hello World! 的整型数关键码和一个变长的数据字段组成。数据字段

82 XYZ 都是字符串。为了存放右面的那些记录，应如何组织线

1038 This string is rather long 性索引？

1037 This is Shorter 【解答】

42 ABC 将所有字符串依加入的先后次序存放于一个连续的

2222 Hello new World! 存储空间store中，这个空间也叫做“堆”，它是存放所有

字符串的顺序文件。它有一个指针free，指示在堆store中当前可存放数据的开始地址。初始时free置为0，表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键码，字符串在store中的起始地址和字符串的长度：

210

索引表ID 堆store 关键码 串长度 42 82 397 1037 1038 2222 3 3 12 15 26 16 串起始地址 56 12 0 41 15 59

0 Hello World! XYZ This string is rather long This is Shorter ABC Hello new World! free

10-5 设有一个职工文件：

记录地址 职工号 姓 名 10032 034 10068 064 10104 073 10140 081 10176 092 10212 123 10248 140 10284 175 10320 209 蔡晓莉 朱 力 洪 伟 卢声凯 林德康 熊南燕 吕 颖 袁秋慧 性别 女 男 男 男 男 女 女 女 职 业 教 师 教 师 实验员 教 师 教 师 教 师 实验员 教 师 年龄 29 32 26 36 28 27 28 24 籍贯 山东 辽宁 广东 北京 湖北 江西 上海 江苏 广东 月工资(元) 720.00 1200.00 480.00 1400.00 720.00 480.00 780.00 480.00 720.00 刘激扬 男 行政秘书 33

其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜索结果关键码。(1) 男性职工；(2) 月工资超过800元的职工；(3) 月工资超过平均工资的职工；(4) 职业为实验员和行政秘书的男性职工；(5) 男性教师或者年龄超过25岁且职业为实验员和教师的女性职工。 【解答】

主索引 月工资 倒排索引 职务 倒排索引 职工号 记录地址 0 034 10032 1 064 10068 2 073 10104 3 081 10140 4 092 10176 5 123 10212 6 140 10248 7 175 10284 8 209 10320

月工资 480. 720. 780. 1200. 1400. 长度 3 3 1 1 1 指针 073 123 175 034 092 209 140 064 081

职务 教师 实验员 行政秘书 长度 6 2 1 指针 034 064 081 092 140 209 073 175 123

211

性别 倒排索引 年龄 倒排索引 性别 男 女 长度 5 4 指针 034 073 081 092 123 064 140 175 209

年龄 24 26 27 28 29 32 33 36 长度 1 1 1 2 1 1 1 1 指针 209 073 140 092 175 034 064 123 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树的变化。

212

45 55 80 90 50 60 70 85 95

25 35

【解答】 插入65后：

25 35 45 55 80 65 90 70 85 95 50 60

插入15后：

25 45 15 35 50 60 55 80 65 90 70 85 95

插入40后：

55 80

65 25 45 90

35 40 15 50 60 70 85 95

插入30后： 55 35 80 65 25 45 90

30 15 40 50 60 70 85 95

10-9 下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。

20 40 55 70 95 30 50 60 80

213

【解答】

删除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 class HashTable { public:

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 const HashTable & HashTable :: operator = ( const HashTable &ht2 ) { //重载函数：复制一个散列表ht2 if ( this != &ht2 ) { }

return *this; }

template int HashTable :: Find ( const Type& x ) {

//返回目标散列表结构指针

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 ) {

本文来源：https://www.bwwdw.com/article/xir5.html