西安建筑科技大学：《数据结构基础》课程课外习题_第五部分查找与排序_索引与散列.doc_大学文库

第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章索引与散列搜索结果 (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章索引与散列录。最少有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 章索引与散列 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

西安建筑科技大学：《数据结构基础》课程课外习题_第五部分 查找与排序_索引与散列

西安建筑科技大学：《数据结构基础》课程课外习题_第五部分查找与排序_索引与散列