数据结构习题解析第10章.doc

《数据结构习题解析第10章.doc》由会员分享，可在线阅读，更多相关《数据结构习题解析第10章.doc（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构习题解析第10章.精品文档.第10章 索引与散列一、复习要点索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。1、基本知识点要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括B树的搜索、插入、删除，通过关键码个数估算B树的高度的方法；B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。二、难点与重点 1、线性索引密集索引、稀

2、疏索引、索引表计算基于属性查找建立倒排索引、单元式倒排表2、动态搜索树平衡的m路搜索树的定义、搜索算法B树的定义、B树与平衡的m路搜索树的关系 B树的插入(包括结点分裂)、删除(包括结点调整与合并)方法B树中结点个数与高度的关系B+树的定义、搜索、插入与删除的方法3、散列表 散列函数的比较 装载因子 a 与平均搜索长度的关系，平均搜索长度的关系 表长m、表中已有数据对象个数n和装载因子的关系 解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 线性探查法中的堆积聚集问题 解决冲突的(闭散列)双散列法的运用，平均探查次数计算

3、双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜 解决冲突的(闭散列)二次散列法的运用，平均探查次数计算 注意：二次散列法中装载因子a与表长m的设置 解决冲突的(开散列)开散列法的运用，平均探查次数计算 由平均探查次数计算装载因子a，再计算表大小的方法三、教材中习题的解析10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定

4、型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。10-2 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效率, 每一个子表的大小应设计为多大? 【解答】每个子表的大小 s = n = 10000 = 100 个记录对象。10-3如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用16字节，其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中

5、开辟了256K字节的空间可用于存放线性索引。试问：(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)(2) 如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？【解答】(1) 因为一个磁盘页块大小为1024字节，每个记录对象需要占用16字节，则每个页块可存放1024 / 16 = 64个记录，除第一个记录存储线性索引外，每个页块可存储63个记录对象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引，每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常

6、驻内存，那么它最多可存放256 * (1024 / 8 ) = 256 * 128 = 32768个索引项，文件中可存放 32768 * 63 = 2064384个记录对象。(2) 由于第二级索引占用1024个字节，内存中还剩255K 字节用于第一级索引。第一级索引有255 * 128 = 32640个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文件中可存放32640 * 63 = 2056320。 397 Hello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello

7、 new World! 10-4 假设在数据库文件中的每一个记录是由占2个字节的整型数关键码和一个变长的数据字段组成。数据字段都是字符串。为了存放右面的那些记录，应如何组织线性索引？【解答】将所有字符串依加入的先后次序存放于一个连续的存储空间store中，这个空间也叫做“堆”，它是存放所有字符串的顺序文件。它有一个指针free，指示在堆store中当前可存放数据的开始地址。初始时free置为0，表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键码，字符串在store中的起始地址和字符串的长度：索引表ID 堆store 关键码串长度串起始地址 0Hello World! XYZ T

8、his string is rather long This 4235682312is Shorter ABC Hello new World!free39712010371541103826152222165910-5 设有一个职工文件： 记录地址 职工号 姓 名 性别 职 业 年龄 籍贯 月工资(元) 10032 034 刘激扬 男 教 师 29 山东720.00 10068 064 蔡晓莉 女 教 师 32 辽宁1200.00 10104 073 朱 力 男 实验员 26 广东480.00 10140 081 洪 伟 男 教 师 36 北京1400.00 10176 092 卢声凯 男

9、教 师 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岁且职业为实验员和教师的女性职工。【解答】 主索引 月工资

10、倒排索引 职务 倒排索引 职工号记录地址月工资长度指针职务长度指针003410032480.3073教师6034106410068123064207310104175081308110140720.3034092409210176092140512310212209209614010248780.1140实验员20737175102841200.10641758209103201400.1081行政秘书1123 性别 倒排索引 年龄 倒排索引性别长度指针年龄长度指针男5034241209073261073081271140092282092123175女40642910341403210641

11、75331123209361081搜索结果： (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

12、, 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, 17510-6 倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较这两种方式的优缺点。 【解答】在倒排索引中的记录地址用记录的实际存放地址，搜索的速度快；但以后在文件中插入或删除记录对象时需要移动文件中的记录对

13、象，从而改变记录的实际存放地址，这将对所有的索引产生影响：修改所有倒排索引的指针，不但工作量大而且容易引入新的错误或遗漏，使得系统不易维护。记录地址采用记录的关键码，缺点是寻找实际记录对象需要再经过主索引，降低了搜索速度；但以后在文件中插入或删除记录对象时，如果移动文件中的记录对象，导致许多记录对象的实际存放地址发生变化，只需改变主索引中的相应记录地址，其他倒排索引中的指针一律不变，使得系统容易维护，且不易产生新的错误和遗漏。10-7 m = 2的平衡m路搜索树是AVL树，m = 3的平衡m路搜索树是2-3树。它们的叶结点必须在同一层吗？m阶B树是平衡m路搜索树，反过来，平衡m路搜索树一定是B

14、树吗？为什么？【解答】m = 3的平衡m路搜索树的叶结点不一定在同一层，而m阶B_树的叶结点必须在同一层，所以m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树不一定是B_树。10-8 下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化。5580 904560 7025 35508595【解答】插入65后：55 80 45659025 35508595607055 80 插入15后：659025 4550859560701535插入40后：55 80 659025 4550859560701535 40插入30后：55 35804530659025405085956070

15、1510-9 下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。5060 80305520407095【解答】删除50后： 558030204060 7095删除40后：55 8020 3060 709510-10 对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。【解答】设B树的阶数m = 199，则m/2 = 100。若不包括失败结点层，则其最大层数为logm/2 (N+1)/2) = log100 1000000 = 3若使得每一层关键码数达到最大，可使其层数达到最小。第0层最多有 (m-1) 个关键码，第1层最多

16、有m(m-1) 个关键码，第2层最多有 m2 (m-1) 个关键码，第h-1层最多有mh-1 (m-1) 个关键码。层数为h的B树最多有 (m-1) + m (m-1) + m2 (m-1) + + mh-1 (m-1) = (m-1) (mh1) / (m-1) = mh1个关键码。反之，若有n个关键码，nmh1，则 h log m (n+1)，所以，有1999999个关键码的199阶B树的最小层数为log m (n+1) = log199 (1999999 +1) = log 199 2000000 = 310-11 给定一组记录，其关键码为字符。记录的插入顺序为 C, S, D, T,

17、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 C D S S S D S C D S T A C D S T A CS T D M 插入P 插入ID S D M S A CS T D M PA CD IS T M PD M S U 插入B, W, N, G 插入U D M S U W M N PS T D G IA B CM N PS T W D G IA B C 插入RP D M S U A B CD G IP R M N S

18、T U W 插入KP D I M S U A B CD G M N U W P R S T I K P 插入ED I M S U A B CD E G M N U W P R S T I K 插入HP D G I M S U A B CD E M N G H P R S T I K U W 插入O, LP S U D G I M D E M N O G H P R S T I K L U W A B C 插入JI P S U D G K M U W A B CK L I J S T P R G H M N O D E 10-12 设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存

19、储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 = 10

20、0个结点，最少可存储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设散列表为HT13, 散列函数为 H (key) = key %13。用

21、闭散列法解决冲突, 对下列关键码序列 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) =

22、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 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 搜索不成功的平均搜索长度为ASLunsucc = (2

23、 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = (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 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10-14 设有150个记录要存储到散列表中, 要求利用线性探查

24、法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设a是散列表的装载因子，则有【解答】已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc 2，则有ASLsucc = 2，解得 a 。又有a = ，则 m 225。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-

25、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 )

26、 ) % 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

27、= ( 2*d 2*q +1) % m = ( 2*d m + 2) % m ( 代换 q = (m-1)/2 )代入 d = q, q+1, , 2q-1，则可得到2*dm+2 = 2*q m +2 = m 1 m +2 = 1,2*dm+2 = 2*q + 2 m +2 = m 1 + 2 m +2 = 3, , 2*dm+2 = 2*(2*q-1) m +2 = 2*(m11) m + 2 = 2*m 4 m +2 = m 2。证毕(2) 编写算法下面是使用二次探查法处理溢出时的散列表类的声明。template class HashTable /散列表类的定义public: enum K

28、indOfEntry Active, Empty, Deleted ;/表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) AllocateHt ( ); CurrentSize = 0; /构造函数 HashTable ( ) delete ht; /析构函数 const HashTable & operator = ( const HashTable & ht2 );/重载函数：表赋值7 int Find ( const Type & x );/在散列表中搜索x int IsEmpty ( ) return !Curren

29、tSize ? 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; /散列表存储数组

30、 int TableSize;/数组长度，是满足4k+3的质数，k是整数 int CurrentSize;/已占据散列地址数目 void AllocateHt ( ) ht = new HashEntryTableSize ; /为散列表分配存储空间; int FindPos ( const Type & x );/散列函数template const HashTable & HashTable : operator = ( const HashTable &ht2 ) /重载函数：复制一个散列表ht2 if ( this != &ht2 ) delete ht; TableSize = ht

31、2.TableSize; AllocateHt ( ); /重新分配目标散列表存储空间 for ( int i = 0; i TableSize; i+ ) hti = ht2.hti;/从源散列表向目标散列表传送 CurrentSize = ht2.CurrentSize;/传送当前表项个数 return *this;/返回目标散列表结构指针template int HashTable : Find ( const Type& x ) /共有函数： 找下一散列位置的函数 int i = 0, q = ( TableSize -1 ) / 2, h0;/ i为探查次数 int CurrentP

32、os = h0 = HashPos ( x );/利用散列函数计算x的散列地址 while ( htCurrentPos.info != Empty & htCurrentPos.Element != x ) /搜索是否要求表项 if ( i = TableSize ) CurrentPos -= TableSize;/实现取模 else CurrentPos = h0 - ( i -q ) * ( i - q ); while ( CurrentPos 0 ) CurrentPos += TableSize; /实现取模 i+; if ( htCurrentPos.info = Active

33、 & htCurrentPos.Element = x ) return CurrentPos;/返回桶号 else htCurrentPos.info = Active; htCurrentPos.Element = x; /插入x if ( +CurrentSize TableSize / 2 ) return CurrentPos;/当前已有项数加1, 不超过表长的一半返回HashEntry *Oldht = ht;/分裂空间处理: 保存原来的散列表int OldTableSize = TableSize;CurrentSize = 0;TableSize = NextPrime ( 2

34、 * OldTableSize );/原表大小的2倍，取质数Allocateht ( );/建立新的二倍大小的空表for ( i = 0; i N的质数，设N = 5 if ( N % 2 = 0 ) N+;/偶数不是质数 for ( ; !IsPrime (N); N += 2 );/寻找质数 return N;int IsPrime ( int N ) /测试N是否质数 for ( int i = 3; i*i = N; i += 2 )/若N能分解为两个整数的乘积, 其中一个一定 if ( N % i = 0 ) return 0;/N能整除i, N不是质数 return 1;/N是质数

35、10-16 编写一个算法，以字典顺序输出散列表中的所有标识符。设散列函数为hash(x) = x中的第一个字符，采用线性探查法来解决冲突。试估计该算法所需的时间。 【解答】用线性探查法处理溢出时散列表的类的声明。#define DefaultSize 1000#include #include #include class HashTable /散列表类定义public: enum KindOfEntry Active, Empty, Deleted ;/表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) ht = new H

36、ashEntryTableSize; /构造函数 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 Ta

37、bleSize;/最大桶数 int FindPos ( string s ) const return atoi (*s) - 32; /散列函数int HashTable : Find-Ins ( const char * id ) int i = FindPos ( id ), j = i; /i是计算出来的散列地址 while ( htj.info != Empty & strcmp ( htj.Element, id ) != 0 ) /冲突 j = ( j + 1 ) % TableSize;/当做循环表处理, 找下一个空桶 if ( j = i ) return -TableSize;/转一圈回到开始点, 表已满, 失败 if ( htj.info != Active ) /插入if ( j i ) while ( int k = j; k i; k- ) htk.Element = htk-1.Element; htk.info = htk-1.info; hti.Element = id; ht