第10-12章习题课分析

1、1第第10-12章章习题课习题课宋国杰宋国杰北京大学信息科学技术学院北京大学信息科学技术学院第第10章章 检索检索第第11章章 索引索引第第12章章 高级数据结构高级数据结构2第1题请设计一个字典，支持下列的操作：INSERT x：插入一个字符串 xFIND x：返回一个 bool 值，表示字符串是否存在 请设计一个这样的字典，并且介绍其优点和缺点。 注意：字符串本身可能比较长；字符串的个数在105 个左右。3答案考查知识点：考查知识点：开散列开散列方案：考虑到字符串很多的因素，采用方案：考虑到字符串很多的因素，采用拉链式拉链式Hash表表解决，解决，用一个用一个Hash函数进行寻址函数进行寻

2、址；考虑到字符串很长的因素，考虑到字符串很长的因素，在插入的时候用另一个在插入的时候用另一个Hash函数来给每一个字符串一个函数来给每一个字符串一个ID，相同的字符串相同的字符串ID一定相同，不同的字符串也有一定概率一定相同，不同的字符串也有一定概率ID相同，相同，在查找时，仅需考虑在查找时，仅需考虑ID相同的串来确定是否串相同的串来确定是否串X存在存在，避免了大范围的查找，和大量长字符串匹配，避免了大范围的查找，和大量长字符串匹配。4第2题现在有一个文本编辑器，具有如下的操作：现在有一个文本编辑器，具有如下的操作：MOVE k：将光标移动到第：将光标移动到第k个字符之前，如果个字符之前，如果

3、k=0，那么移动到文档开头，那么移动到文档开头PRINT n：输出光标之后的：输出光标之后的n个字符个字符PREV：光标前移一位：光标前移一位NEXT：光标后移一位：光标后移一位5（1）请基于线性数据结构设计一套合理的算法，来实）请基于线性数据结构设计一套合理的算法，来实现这些操作，并且分析每个操作的性能。假定：文本现这些操作，并且分析每个操作的性能。假定：文本最大的长度为最大的长度为Lh2：15那么，为了满足红黑树性质，我们令那么，为了满足红黑树性质，我们令T2的根结点为的根结点为多多(h1-h2+1)黑结点。我们可以利用红黑树的删除算黑结点。我们可以利用红黑树的删除算法中对双黑结点处理的方

4、法同样处理法中对双黑结点处理的方法同样处理T2的根结点，的根结点，即令其从即令其从(h1-h2+1)黑结点，变为黑结点，变为(h1-h2)黑结点黑结点直直至为单黑结点，那么就变成了一棵正常的红黑树。至为单黑结点，那么就变成了一棵正常的红黑树。16双黑结点的调整双黑结点的调整假设假设X是左子结点（若是左子结点（若X为右子结点，处理方法类似，不重述）为右子结点，处理方法类似，不重述）情况情况1：双黑结点的兄弟C是红色，执行旋转操作（黑红）！推出：推出：B结点也一定是黑色，结点也一定是黑色， 和和也是黑色也是黑色旋转：兄弟节点为根变黑，父节点变红旋转：兄弟节点为根变黑，父节点变红X结点仍是结点仍是“

5、双黑双黑”结点，转化为情况结点，转化为情况2,317BCXXBC双黑结点情况情况2：兄弟是黑色, 且有两个黑子结点（黑黑黑）执行换色操作，把执行换色操作，把C着红色，着红色，B着黑色着黑色如果如果B原为红色，则算法结束原为红色，则算法结束否则，对否则，对B继续作继续作“双黑双黑”调整（调整（为什么？为什么？）BXEDCBCEDX18有可能继续双黑处理双黑结点的调整双黑结点的调整情况情况3：兄弟C是黑色，且子结点有红色(黑黑红)(a)旋转重构：旋转重构：侄子红结点八字外撇侄子红结点八字外撇将兄弟结点将兄弟结点C提上去，继承原父结点的颜色提上去，继承原父结点的颜色然后把然后把B着为黑色，着为黑色，

6、D着为黑色，其他颜色不变即可着为黑色，其他颜色不变即可19BDXCDXBC单旋转调整单旋转调整(b)旋转重构：旋转重构：侄子红结点同边顺侄子红结点同边顺将将C结点旋转为结点旋转为D结点的父结点，结点的父结点，C继承原子根继承原子根B的颜的颜色，色，B着为黑色着为黑色BXEDCDBCXE2011.6.3 插入算法插入算法先调用先调用BST的插入算法，将待插记录定位的插入算法，将待插记录定位新记录X着色为红色若父结点是黑色，则算法结束若父结点是黑色，则算法结束否则，否则，双红调整XAAX插入插入4 421双红调整双红调整1：红黑旋转红黑旋转情况情况1：新增结点X的叔父结点是黑色，或者NIL调整后：

7、祖节点变为黑，父、叔节点变为红！调整后：祖节点变为黑，父、叔节点变为红！每个结点的阶都保持原值，调整完成每个结点的阶都保持原值，调整完成保持树的稳定性！保持树的稳定性！以祖结点为轴旋以祖结点为轴旋转父结点转父结点224种形式的结构调整种形式的结构调整原则：保持原则：保持BST的中序性质的中序性质23提升操作旋转操作双红调整双红调整2：红红换色红红换色情况情况2：新增结点X的叔父结点也是红色父祖换色父祖换色叔父变黑叔父变黑24对B继续红红检查如果B是根节点，则只叔父节点变色，根节点不变！25第第10章章 检索检索第第11章章 索引索引第第12章章 高级数据结构高级数据结构26提供广义表的下列操作

8、提供广义表的下列操作make_GList(a,b,c.);将任意多个广义表连接成一个新的广将任意多个广义表连接成一个新的广义表义表head(gList);取广义表头取广义表头tail(gList);取广义表尾；取广义表尾；要求设计一个算法，将广义表置逆，不能使用其他要求设计一个算法，将广义表置逆，不能使用其他数据结构。比如，对于广义表数据结构。比如，对于广义表(a,(a,b,c),(b,(d),置逆置逆之后的结果为：之后的结果为：(d),b),(c,b,a),a);27解：直接用递归即可。解：直接用递归即可。GList reverse(gList) Return make_Glist(reve

9、rse(tail(gList),reverse(head(gList)282.假定经过分词后的网页已经形成了倒排索引，使用假定经过分词后的网页已经形成了倒排索引，使用trie树作为词典，叶子结点会有指向倒排表的指针，树作为词典，叶子结点会有指向倒排表的指针，倒排表是按照网页文档倒排表是按照网页文档id（连续的整数值）排好序（连续的整数值）排好序的。现在需要系统支持简单的布尔查询。请写出以的。现在需要系统支持简单的布尔查询。请写出以下算法的代码或伪代码，并分析复杂度下算法的代码或伪代码，并分析复杂度29I. Keyword1 and keyword2II. Keyword2 and not ke

10、yword2III.如果需要支持相邻查询，例如如果需要支持相邻查询，例如keyword and keword2 near distance，distance代表词与词代表词与词之间的距离，需要怎样更改倒排索引表，支之间的距离，需要怎样更改倒排索引表，支持这一需求？持这一需求？30答案答案1、用用 trie 树可以在树可以在 O(length(string)的时间内找到的时间内找到单词所对应的倒排表的位置。单词所对应的倒排表的位置。根据这一点，设计如下代码。根据这一点，设计如下代码。设设 A1.AN 为第一个单词的文档，为第一个单词的文档，B1.BM 为第二个为第二个单词的文档单词的文档3132

11、33343.AVL树和红黑树的高度树和红黑树的高度A. 高度为高度为h的的AVL树上的最少结点个数是多少？最多树上的最少结点个数是多少？最多结点个数是多少？结点个数是多少？B. 高度为高度为h的红黑树上的最少结点个数是多少？最多的红黑树上的最少结点个数是多少？最多结点个数是多少？结点个数是多少？35363721h21hBBh=5，为奇数时，树的阶为，为奇数时，树的阶为k=inth/221 12kk 21 12kk k=2k=112*21kkiinth/2 2233821h21hh=6，为偶数时，树的阶为，为偶数时，树的阶为k=inth/221 12kk k=3B112*221kikiinth/

12、23*23k=2k=13921h21hBh=6，为偶数时，树的阶为，为偶数时，树的阶为k=inth/221 12kk k=3k=2B22*23kkiinth/2 2254. KD树和树和PR四分树都可以支持区域四分树都可以支持区域查找。请问两者有什么优劣势？查找。请问两者有什么优劣势？401、k-d树树 k-d树是一种用于多维检索的树结构，它的每树是一种用于多维检索的树结构，它的每一层都根据特定关键码将对象空间分解为两一层都根据特定关键码将对象空间分解为两个个顶层结点按一个维划分顶层结点按一个维划分第二层结点按照另一维进行划分第二层结点按照另一维进行划分以此类推在各个维之间反复进行划分以此类推

13、在各个维之间反复进行划分 最终当一个结点中的点数少于给点的最大点数时，最终当一个结点中的点数少于给点的最大点数时，划分结束划分结束 识别器( discriminator ) 在每一层用来进行决策的关键码称为识别器在每一层用来进行决策的关键码称为识别器对于对于k维关键码，在第维关键码，在第i层把识别器定义为层把识别器定义为i mod k例如，对一个三维的关键码做检索，例如，对一个三维的关键码做检索，3个关键码个关键码（x，y，z）标号分别为）标号分别为0、1、2第一层是第一层是0 mod 3=0，所以使用关键码，所以使用关键码x，第二层是第二层是1 mod 3=1，所以使用关键码，所以使用关键码

14、y结点的分配结点的分配在结点分配的时候首先比较该层的识别器在结点分配的时候首先比较该层的识别器如果关键码小于识别器的值就放到左子树中如果关键码小于识别器的值就放到左子树中否则放到右子树否则放到右子树然后在下一层使用新的识别器来判断每个结然后在下一层使用新的识别器来判断每个结点的归属点的归属识别器的值应该尽量使得被划分的结点大约识别器的值应该尽量使得被划分的结点大约一半落在左子树，另一半落在右子树一半落在左子树，另一半落在右子树K-DK-D树示例树示例K-D树的空间分解树的空间分解上图是一个二维的上图是一个二维的k-d树，取值范围为树，取值范围为100100之内之内k-dk-d树的每个内部结点树

15、的每个内部结点把当前的空间划分为两块，交替地对两个维进行划分把当前的空间划分为两块，交替地对两个维进行划分根结点把空间划分成两部分根结点把空间划分成两部分其子结点进一步把空间划分成更小的部分其子结点进一步把空间划分成更小的部分子结点的划分线不会穿过根结点的划分线子结点的划分线不会穿过根结点的划分线 k-d树中的这些结点最终把空间分解为矩形树中的这些结点最终把空间分解为矩形这些矩形是结点可能落到的各子树范围这些矩形是结点可能落到的各子树范围K-D树的不足 其结构与输入数据的顺序也是有关的其结构与输入数据的顺序也是有关的有可能导致它每个子树的元素分配不均衡有可能导致它每个子树的元素分配不均衡Ben

16、tley和和Friedman发明了发明了adaptive k-d树，树，类似于类似于BST所有的数据记录都存储在叶结点所有的数据记录都存储在叶结点内部结点只是用来在各个维之间导航内部结点只是用来在各个维之间导航每一个识别器的选择不再依赖于输入的数据每一个识别器的选择不再依赖于输入的数据尽量选择让左右子树的记录数目相等的值 2、PR四分树四分树 PR四分树，即点四分树，即点-区域四分树（区域四分树（Point-Region Quadtree） ：每个内部结点都恰好有四个子结点每个内部结点都恰好有四个子结点每个内部结点将当前空间均等地划分为四个区域每个内部结点将当前空间均等地划分为四个区域NWNW

17、（西北）、（西北）、NENE（东北）、（东北）、SWSW（西南）和（西南）和SESE（东南）（东南）PR四分树也是对对象空间的划分四分树也是对对象空间的划分完全四叉树完全四叉树 PR四分树对空间的划分四分树对空间的划分每个内部结点将当前空间均等地划分为四个每个内部结点将当前空间均等地划分为四个区区如果子区域包含的数据点数大于如果子区域包含的数据点数大于1，那么就把该区，那么就把该区域继续均等地划分为四个区域域继续均等地划分为四个区域依次类推，直到每个区域所包含的数据点不超过依次类推，直到每个区域所包含的数据点不超过一个为止一个为止 PR树的图示PR树的划分树的划分上图所表示的上图所表示的PR四

18、分树，其对象空间为四分树，其对象空间为128 128 ，并包含点并包含点A、B、C、D、E、F和和G 根结点的四个子结点把整个空间平分为四份根结点的四个子结点把整个空间平分为四份大小为大小为64 64的子空间的子空间NW，NE，SW，SE NW（包含三个数据点）和（包含三个数据点）和SE(包含两个数据点包含两个数据点) 需要进一步分裂需要进一步分裂 PR树的插入如果这个位置的叶结点没有包含其他的数据点如果这个位置的叶结点没有包含其他的数据点那么我们就把记录插入这里；那么我们就把记录插入这里；如果这个叶结点中已经包含如果这个叶结点中已经包含P了了(或者一个具有或者一个具有P的坐的坐标的记录标的记

19、录)那么就报告记录重复；那么就报告记录重复；如果叶结点已经包含另一条记录如果叶结点已经包含另一条记录X那么就必须继续分解这个结点，直到已存在的记录那么就必须继续分解这个结点，直到已存在的记录X和和P分分别进入不同的结点为止别进入不同的结点为止 PR树的删除产生的合并删除结点删除结点D导致的区域合并导致的区域合并PR树的不足无法做到有效率的插入删除，很有可能出现最坏情无法做到有效率的插入删除，很有可能出现最坏情况；况；空间动态分配，但是增加空间动态分配，但是增加/减少的量并不稳定；减少的量并不稳定；处理分布比较均匀的情况时，效果并不差。处理分布比较均匀的情况时，效果并不差。53考试大纲考试大纲5

20、4关于考试时间和地点时间和地点时间：时间：2015年年1月月7日日 上午上午8:30-10:30地点：一教地点：一教 201考试题型考试题型填空、选择、辨析与简答、数据结构或算法的设计和分析填空、选择、辨析与简答、数据结构或算法的设计和分析、数学证明、数学证明（1）数据结构）数据结构/算法设计与分析题只要写明基本思想、无算法设计与分析题只要写明基本思想、无歧义即可，必要时加上足够的注释。歧义即可，必要时加上足够的注释。（2）对于算法中直接使用的类和函数（例如栈、队列的）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写函数），应该先写ADT，并简单说明算法中用到的重要函，并简单说明算

21、法中用到的重要函数的功能、入口参数、出口参数。数的功能、入口参数、出口参数。范围：范围：1-12章章55考场安排和注意事项考场安排和注意事项 请随身带好您的学生证，笔和涂改工具参加考试。请随身带好您的学生证，笔和涂改工具参加考试。 考试形式为闭卷，可以使用计算器考试形式为闭卷，可以使用计算器 考前考前10分钟，请大家把书包等放在教室前面的讲台和窗台上分钟，请大家把书包等放在教室前面的讲台和窗台上，注意在试卷纸和有效答题纸上写上姓名和学号。，注意在试卷纸和有效答题纸上写上姓名和学号。 统一发草稿纸，不够可以随时举手要。统一发草稿纸，不够可以随时举手要。 请大家注意考场纪律，不要交头接耳，私下讨论

22、。考试时对请大家注意考场纪律，不要交头接耳，私下讨论。考试时对试题有疑问，可以举手，待监考老师来到旁边时，再请向监试题有疑问，可以举手，待监考老师来到旁边时，再请向监考老师询问。考老师询问。 监考老师收卷清点无误，并宣布监考老师收卷清点无误，并宣布“全班同学都可以离开了全班同学都可以离开了”以后方可集体离开。注意，不要把试卷题带出考场，否则将以后方可集体离开。注意，不要把试卷题带出考场，否则将计零分。计零分。56第第1章章 概论概论一一. 重要概念重要概念1. 抽象数据结构抽象数据结构 2. 数据逻辑结构数据逻辑结构 3.数据存储结构数据存储结构 4. 算法算法 5. 算法分析算法分析(时间代

23、价、空间代价时间代价、空间代价) 二二. 方法方法1. 根据二元组画出图示逻辑结构根据二元组画出图示逻辑结构(注意边的方向注意边的方向) 2. 根据要求设计数据结根据要求设计数据结构构 3. 算法的渐进分析方法算法的渐进分析方法 4. 大大O表示法表示法（不要求掌握大（不要求掌握大、大、大表示法）表示法）57第第2章章 线性表线性表一一. 概念概念1. 线性表线性表 2. 单链表单链表 3. 双链表双链表 4. 循环表循环表二二. 方法方法1. 顺序表上实现的运算顺序表上实现的运算 2.链表上实现的运算链表上实现的运算(指针操作的正确性指针操作的正确性) 3. 顺序表和链表的比较顺序表和链表的

24、比较58第第3章章 栈与队列栈与队列一一. 概念概念1. 栈栈 2. 队列队列 3. 循环队列循环队列二二. 方法方法 1. 栈的性质，用栈来生成序列栈的性质，用栈来生成序列 2. 队列的性质，用队列队列的性质，用队列 生成生成 序列序列 3. 栈的顺序实现栈的顺序实现 4. 循环队列的实现循环队列的实现5. 表达式求值表达式求值 (中缀表达式转后缀表达式的算法、中缀表达式转后缀表达式的算法、后缀表达式求值算法后缀表达式求值算法)6. 栈在递归调用及转换中的应用栈在递归调用及转换中的应用59第第4章章 字符串字符串一一. 概念概念1. 串串 2. 模式匹配模式匹配二二. 方法方法1. 串的基本

25、操作串的基本操作2. 串的存储及运算串的存储及运算 3. 串的串的KMP快速模式匹配算法，求特征向量数快速模式匹配算法，求特征向量数组（组（N数组）和利用数组）和利用N向量完成匹配的方法向量完成匹配的方法60第第5章章 二叉树二叉树一一. 概念概念1. 二叉树二叉树 2.二叉树的深度优先周游二叉树的深度优先周游 3. 二叉排序树二叉排序树 4. 堆堆 5. Huffman树、树、Huffman编码编码各种结构的节点个数与高度、层次、度等关系换算各种结构的节点个数与高度、层次、度等关系换算 二二. 方法方法1二叉树的链式存储二叉树的链式存储（1）二叉链表）二叉链表（2）带父指针的三重链表）带父指

26、针的三重链表612. 二叉树的顺序存储二叉树的顺序存储完全二叉树的顺序存储完全二叉树的顺序存储 3. 二叉树的深度优先周游二叉树的深度优先周游 4. BST树的插入与删除树的插入与删除 5. 构造构造Huffman树树和和Huffman编码编码 6. 堆的建立与维护过程堆的建立与维护过程62636465第第6章章 树树一一. 概念概念树、森林树、森林 、先根、后根、层次周游先根、后根、层次周游 K叉树叉树 二二. 方法方法 1. 森林与二叉树相互转换森林与二叉树相互转换2森林的链式存储森林的链式存储 (1) 转换为相应的二叉树，用二叉链表表示转换为相应的二叉树，用二叉链表表示(2) 父指针表示

27、法、(3) 子结点表表示法(4)等价类和并查算法的应用66 3. 森林的深度优先周游（递归），可能结合应用森林的深度优先周游（递归），可能结合应用 4. 森林的顺序存储森林的顺序存储及其构造及其构造5. 二叉树和森林的层次周游二叉树和森林的层次周游(用队列用队列)，可能结合应用，可能结合应用67第第7章章 图图一一. 概念概念1. 图的相关概念：图的相关概念：连通性、连通分量、边与顶点关系等连通性、连通分量、边与顶点关系等2. 深度周游深度周游、宽度周游宽度周游 3. 图的生成树、生成树林、最小生成树图的生成树、生成树林、最小生成树二二. 方法及算法方法及算法1. 图的存储方法图的存储方法:（

28、1） 相邻矩阵相邻矩阵 （2） 邻接表邻接表2. 图的周游图的周游: 1） 深度优先深度优先 （2） 宽度优先宽度优先683. 图的生成树与最小生成树图的生成树与最小生成树从某一点出发，按深度优先或宽度优先周游的生成树从某一点出发，按深度优先或宽度优先周游的生成树最小生成树最小生成树 Prim算法算法 Kruskal算法算法(避圈法避圈法)4. 拓扑排序拓扑排序 : 给定图，找出若干个或所有拓扑序列给定图，找出若干个或所有拓扑序列5. 最短路径最短路径: Dijkstra算法、算法、Floyd算法算法6. Dijkstra算法、算法、Prim算法、算法、Kruskal算法都是典型算法都是典型的

29、贪心法（退化的动态规划法）的贪心法（退化的动态规划法）69第第8章章 内排序内排序 1. 重点排序算法：直接插入法、重点排序算法：直接插入法、Shell排序、快排序、快速排序、基数排序、归并排序速排序、基数排序、归并排序 2. 算法分析算法分析基于比较次数和移位次数分析最好、最坏的时间、空间基于比较次数和移位次数分析最好、最坏的时间、空间直接插入法、二分法插入排序、起泡排序、直接选择、快直接插入法、二分法插入排序、起泡排序、直接选择、快速排序、基数排序、归并排序速排序、基数排序、归并排序记住各种排序方法的平均时间记住各种排序方法的平均时间 3. 各种排序方法的局部修改和混合应用各种排序方法的局

30、部修改和混合应用70第9章 文件管理和外排序方法及算法方法及算法 1. 置换选择排序置换选择排序 2. 多路归并多路归并 (败者树，最佳归并树，多路归并的读败者树，最佳归并树，多路归并的读盘和写盘次数盘和写盘次数)71第10章 检索一一. 概念概念1. 平均检索长度平均检索长度 2. 二分法检索二分法检索 3. 散列表、同义词、碰散列表、同义词、碰撞、堆积撞、堆积二二. 方法方法1. 二分法检索的判定树、查找某个结点的比较次数二分法检索的判定树、查找某个结点的比较次数2. 散列表散列表: 1) 散列函数选择散列函数选择(除余法、平方取中法、折叠法除余法、平方取中法、折叠法)2) 冲突处理方法(分离同义词子表、线性探测、双散列函数) 三三. 散列算法（查找、插入、删除，对墓碑的处理散列算法（查找、插入、删除，对墓碑的处理72第11章 索引技术一一. 概念概念 1. 顺序文件顺序文件 2. 散列文件散列文件 3. 倒排文件倒排文件 4. 静态索引结构静态索引结构 5.动动态索引结构态索引结构(B树树) 6. 红黑树红黑树二二. 方法（不考算法）方法（不考算法）1. B树、树、B+树的插入与删除树的