第10-12章习题课分析.ppt

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

2、ID，相同的字符串ID一定相同，不同的字符串也有一定概率ID相同，在查找时，仅需考虑ID相同的串来确定是否串X存在，避免了大范围的查找，和大量长字符串匹配。,4,第2题,现在有一个文本编辑器，具有如下的操作： MOVE k：将光标移动到第k个字符之前，如果k=0，那么移动到文档开头 PRINT n：输出光标之后的n个字符 PREV：光标前移一位 NEXT：光标后移一位,5,（1）请基于线性数据结构设计一套合理的算法，来实现这些操作，并且分析每个操作的性能。假定：文本最大的长度为L106 （2）添加2个操作： INSERT n, s：在当前光标之后插入长度为n的字符串s DELETE n：删除光

3、标之后的n个字符 此时数据结构应当作出什么样的改变来适应这一变化？,6,答案,（1）使用分块链表实现。因为这里只有一个Radnom Access的操作，其它的操作都是有相对起始位置的；但是又不能使得MOVE操作成为瓶颈，我们考虑对文本进行分块。按照一般的原则，应当进行sqrt(L)大小的分块 （2）可让分块链表获得自适应的功能。当相邻两个块元素个数和小于设定阈值时，将相邻表合并；如果一个块的大小大于某个阈值时，将其分割。,7,第10章 检索 第11章 索引 第12章 高级数据结构,8,第1题,持久动态集合是这样的集合，每当集合被更新（插入元素或删除元素）时，仍然需要维护该集合的一个较旧的版本。

4、 下图就展示了一个二叉查找树的持久动态集合，对于每个版本，都会有一个对应的根结点，所有根结点处在一个可维护的链表中，可以通过该链表访问所有的根结点，进而访问所有的版本。该二叉树结点没有父结点域。,9,10,1、对一个持久二叉查找树，插入或删除一个关键字 z 的，需要改变哪些结点？ 答案 不需要改变任何结点，只需要复制从根结点开始到插入/删除结点路径上的所有结点。,11,写出向持久二叉查找树中插入一个结点的过程，如果持久二叉查找树的高度为 h ，则实现上述过程的时间和空间复杂性如何？ 答案 与BST插入类似,12,13,第2题,现有红黑树T1、T2和关键码z，T1中的关键码都比z小，T2中的关键

5、码都比z大。试将T1、T2和z合并成一棵新的红黑树T3。树中的关键码不重复。 N是操作结点总数的上限，请分析你的算法的时间代价，如果高于O(logN)，请调整你的算法。 在不给定关键码z的情况下，实现两棵红黑树的合并操作,14,答案,首先生成如下形式的红黑树，这里不妨设T1的阶为h1，T2的阶为h2，且h1h2：,15,那么，为了满足红黑树性质，我们令T2的根结点为多(h1-h2+1)黑结点。我们可以利用红黑树的删除算法中对双黑结点处理的方法同样处理T2的根结点，即令其从(h1-h2+1)黑结点，变为(h1-h2)黑结点直至为单黑结点，那么就变成了一棵正常的红黑树。,16,双黑结点的调整,假设

6、X是左子结点（若X为右子结点，处理方法类似，不重述） 情况1：双黑结点的兄弟C是红色，执行旋转操作（黑红）！ 推出：B结点也一定是黑色， 和也是黑色 旋转：兄弟节点为根变黑，父节点变红 X结点仍是“双黑”结点，转化为情况2,3,17,北京大学信息科学技术学院,数据结构与算法,B,C,X,双黑结点,情况2：兄弟是黑色, 且有两个黑子结点（黑黑黑） 执行换色操作，把C着红色，B着黑色 如果B原为红色，则算法结束 否则，对B继续作“双黑”调整（为什么？）,18,北京大学信息科学技术学院,数据结构与算法,有可能继续双黑处理,双黑结点的调整,情况3：兄弟C是黑色，且子结点有红色(黑黑红) (a)旋转重构

7、：侄子红结点八字外撇 将兄弟结点C提上去，继承原父结点的颜色 然后把B着为黑色，D着为黑色，其他颜色不变即可,19,B,D,X,C,北京大学信息科学技术学院,数据结构与算法,(b)旋转重构：侄子红结点同边顺 将C结点旋转为D结点的父结点，C继承原子根B的颜色，B着为黑色,B,X,E,D,C,20,北京大学信息科学技术学院,数据结构与算法,11.6.3 插入算法,先调用BST的插入算法，将待插记录定位 新记录X着色为红色 若父结点是黑色，则算法结束 否则，双红调整,6,3,8,6,3,8,4,X,A,A,X,插入4,21,北京大学信息科学技术学院,数据结构与算法,双红调整1：红黑旋转,情况1：新

8、增结点X的叔父结点是黑色，或者NIL 调整后：祖节点变为黑，父、叔节点变为红！ 每个结点的阶都保持原值，调整完成 保持树的稳定性！,22,北京大学信息科学技术学院,数据结构与算法,4种形式的结构调整,原则：保持BST的中序性质,2,4,6,2,6,4,23,北京大学信息科学技术学院,数据结构与算法,双红调整2：红红换色,情况2：新增结点X的叔父结点也是红色,24,对B继续红红检查,北京大学信息科学技术学院,数据结构与算法,如果B是根节点，则只叔父节点变色，根节点不变！,25,第10章 检索 第11章 索引 第12章 高级数据结构,26,提供广义表的下列操作 make_GList(a,b,c.)

9、;将任意多个广义表连接成一个新的广义表 head(gList);取广义表头 tail(gList);取广义表尾； 要求设计一个算法，将广义表置逆，不能使用其他数据结构。比如，对于广义表(a,(a,b,c),(b,(d),置逆之后的结果为：(d),b),(c,b,a),a);,27,解：直接用递归即可。 GList reverse(gList) Return make_Glist (reverse(tail(gList),reverse(head(gList) ,28,2.假定经过分词后的网页已经形成了倒排索引，使用trie树作为词典，叶子结点会有指向倒排表的指针，倒排表是按照网页文档id（连续

10、的整数值）排好序的。现在需要系统支持简单的布尔查询。请写出以下算法的代码或伪代码，并分析复杂度,29,Keyword1 and keyword2 Keyword2 and not keyword2 如果需要支持相邻查询，例如keyword and keword2 near distance，distance代表词与词之间的距离，需要怎样更改倒排索引表，支持这一需求？,30,答案,1、用 trie 树可以在 O(length(string)的时间内找到单词所对应的倒排表的位置。 根据这一点，设计如下代码。 设 A1.AN 为第一个单词的文档，B1.BM 为第二个单词的文档,31,32,33,34

11、,3.AVL树和红黑树的高度 高度为h的AVL树上的最少结点个数是多少？最多结点个数是多少？ 高度为h的红黑树上的最少结点个数是多少？最多结点个数是多少？,35,36,37,B,B,h=5，为奇数时，树的阶为k=inth/2,k=2,k=1,38,h=6，为偶数时，树的阶为k=inth/2,k=3,B,k=2,k=1,39,B,h=6，为偶数时，树的阶为k=inth/2,k=3,k=2,B,4. KD树和PR四分树都可以支持区域查找。请问两者有什么优劣势？,40,1、k-d树,k-d树是一种用于多维检索的树结构，它的每一层都根据特定关键码将对象空间分解为两个 顶层结点按一个维划分 第二层结点按

12、照另一维进行划分 以此类推在各个维之间反复进行划分 最终当一个结点中的点数少于给点的最大点数时，划分结束,识别器( discriminator ),在每一层用来进行决策的关键码称为识别器 对于k维关键码，在第i层把识别器定义为i mod k 例如，对一个三维的关键码做检索，3个关键码（x，y，z）标号分别为0、1、2 第一层是0 mod 3=0，所以使用关键码x， 第二层是1 mod 3=1，所以使用关键码y,结点的分配,在结点分配的时候首先比较该层的识别器 如果关键码小于识别器的值就放到左子树中 否则放到右子树 然后在下一层使用新的识别器来判断每个结点的归属 识别器的值应该尽量使得被划分的结

13、点大约一半落在左子树，另一半落在右子树,K-D树示例,K-D树的空间分解,上图是一个二维的k-d树，取值范围为100100之内 k-d树的每个内部结点 把当前的空间划分为两块，交替地对两个维进行划分 根结点把空间划分成两部分 其子结点进一步把空间划分成更小的部分 子结点的划分线不会穿过根结点的划分线 k-d树中的这些结点最终把空间分解为矩形 这些矩形是结点可能落到的各子树范围,K-D树的不足,其结构与输入数据的顺序也是有关的 有可能导致它每个子树的元素分配不均衡 Bentley和Friedman发明了adaptive k-d树， 类似于BST 所有的数据记录都存储在叶结点 内部结点只是用来在各

14、个维之间导航 每一个识别器的选择不再依赖于输入的数据 尽量选择让左右子树的记录数目相等的值,2、PR四分树,PR四分树，即点-区域四分树（Point-Region Quadtree） ： 每个内部结点都恰好有四个子结点 每个内部结点将当前空间均等地划分为四个区域 NW（西北）、NE（东北）、SW（西南）和SE（东南） PR四分树也是对对象空间的划分 完全四叉树,PR四分树对空间的划分,每个内部结点将当前空间均等地划分为四个区 如果子区域包含的数据点数大于1，那么就把该区域继续均等地划分为四个区域 依次类推，直到每个区域所包含的数据点不超过一个为止,PR树的图示,PR树的划分,上图所表示的PR四

15、分树，其对象空间为128128 ，并包含点A、B、C、D、E、F和G 根结点的四个子结点把整个空间平分为四份大小为6464的子空间 NW，NE，SW，SE NW（包含三个数据点）和SE(包含两个数据点) 需要进一步分裂,PR树的插入,如果这个位置的叶结点没有包含其他的数据点 那么我们就把记录插入这里； 如果这个叶结点中已经包含P了(或者一个具有P的坐标的记录) 那么就报告记录重复； 如果叶结点已经包含另一条记录X 那么就必须继续分解这个结点，直到已存在的记录X和P分别进入不同的结点为止,PR树的删除产生的合并,删除结点D导致的区域合并,PR树的不足,无法做到有效率的插入删除，很有可能出现最坏情

16、况； 空间动态分配，但是增加/减少的量并不稳定； 处理分布比较均匀的情况时，效果并不差。,53,考试大纲,54,关于考试,时间和地点 时间：2015年1月7日 上午8:30-10:30 地点：一教 201 考试题型 填空、选择、辨析与简答、数据结构或算法的设计和分析、数学证明 （1）数据结构/算法设计与分析题只要写明基本思想、无歧义即可，必要时加上足够的注释。 （2）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并简单说明算法中用到的重要函数的功能、入口参数、出口参数。 范围：1-12章,55,考场安排和注意事项,请随身带好您的学生证，笔和涂改工具参加考试。 考试形式为闭

17、卷，可以使用计算器 考前10分钟，请大家把书包等放在教室前面的讲台和窗台上，注意在试卷纸和有效答题纸上写上姓名和学号。 统一发草稿纸，不够可以随时举手要。 请大家注意考场纪律，不要交头接耳，私下讨论。考试时对试题有疑问，可以举手，待监考老师来到旁边时，再请向监考老师询问。 监考老师收卷清点无误，并宣布“全班同学都可以离开了”以后方可集体离开。注意，不要把试卷题带出考场，否则将计零分。,56,第1章 概论,一. 重要概念 1. 抽象数据结构 2. 数据逻辑结构 3.数据存储结构 4. 算法 5. 算法分析(时间代价、空间代价) 二. 方法 1. 根据二元组画出图示逻辑结构(注意边的方向) 2.

18、根据要求设计数据结构 3. 算法的渐进分析方法 4. 大O表示法（不要求掌握大、大表示法）,57,第2章 线性表,一. 概念 1. 线性表 2. 单链表 3. 双链表 4. 循环表 二. 方法 1. 顺序表上实现的运算 2.链表上实现的运算(指针操作的正确性) 3. 顺序表和链表的比较,58,第3章 栈与队列,一. 概念 1. 栈 2. 队列 3. 循环队列 二. 方法 1. 栈的性质，用栈来生成序列 2. 队列的性质，用队列 生成 序列 3. 栈的顺序实现 4. 循环队列的实现 5. 表达式求值 (中缀表达式转后缀表达式的算法、后缀表达式求值算法) 6. 栈在递归调用及转换中的应用,59,第

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

20、fman编码 6. 堆的建立与维护过程,62,63,64,65,第6章 树,一. 概念 树、森林 、先根、后根、层次周游 K叉树 二. 方法 1. 森林与二叉树相互转换 2森林的链式存储 (1) 转换为相应的二叉树，用二叉链表表示 (2) 父指针表示法、(3) 子结点表表示法 (4)等价类和并查算法的应用,66, 3. 森林的深度优先周游（递归），可能结合应用 4. 森林的顺序存储及其构造 5. 二叉树和森林的层次周游(用队列)，可能结合应用,67,第7章 图,一. 概念 1. 图的相关概念：连通性、连通分量、边与顶点关系等 2. 深度周游、宽度周游 3. 图的生成树、生成树林、最小生成树 二

21、. 方法及算法 1. 图的存储方法:（1） 相邻矩阵 （2） 邻接表 2. 图的周游: 1） 深度优先 （2） 宽度优先,68,3. 图的生成树与最小生成树 从某一点出发，按深度优先或宽度优先周游的生成树 最小生成树 Prim算法 Kruskal算法(避圈法) 4. 拓扑排序 : 给定图，找出若干个或所有拓扑序列 5. 最短路径: Dijkstra算法、Floyd算法 6. Dijkstra算法、Prim算法、Kruskal算法都是典型的贪心法（退化的动态规划法）,69,第8章 内排序,1. 重点排序算法：直接插入法、Shell排序、快速排序、基数排序、归并排序 2. 算法分析 基于比较次数和

22、移位次数分析最好、最坏的时间、空间 直接插入法、二分法插入排序、起泡排序、直接选择、快速排序、基数排序、归并排序 记住各种排序方法的平均时间 3. 各种排序方法的局部修改和混合应用,70,第9章 文件管理和外排序,方法及算法 1. 置换选择排序 2. 多路归并 (败者树，最佳归并树，多路归并的读盘和写盘次数),71,第10章 检索,一. 概念 1. 平均检索长度 2. 二分法检索 3. 散列表、同义词、碰撞、堆积 二. 方法 1. 二分法检索的判定树、查找某个结点的比较次数 2. 散列表: 1) 散列函数选择(除余法、平方取中法、折叠法) 2) 冲突处理方法(分离同义词子表、线性探测、双散列函数) 三. 散列算