第10-12章习题课分析教学内容.ppt

《第10-12章习题课分析教学内容.ppt》由会员分享，可在线阅读，更多相关《第10-12章习题课分析教学内容.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10-1210-12章章习题课分析分析第1题请设计一个字典，支持下列的操作：INSERTx：插入一个字符串xFINDx：返回一个bool 值，表示字符串是否存在请设计一个这样的字典，并且介绍其优点和缺点。注意：字符串本身可能比较长；字符串的个数在105个左右。2答案考考查知知识点：点：开散列开散列方案：考方案：考虑到字符串很多的因素，采用到字符串很多的因素，采用拉拉链式式Hash表表解决，解决，用一个用一个Hash函数函数进行行寻址址；考考虑到字符串很到字符串很长的因素，的因素，在插入的在插入的时候用另一个候用另一个Hash函数来函数来给每一个字符串一个每一个字符串一个ID，相同的字符串相

2、同的字符串ID一定相同，不同的字符串也有一定概率一定相同，不同的字符串也有一定概率ID相同，相同，在在查找找时，仅需考需考虑ID相同的串来确定是否串相同的串来确定是否串X存在，存在，避免了大范避免了大范围的的查找，和大量找，和大量长字符串匹配字符串匹配。3第2题现在有一个文本在有一个文本编辑器，具有如下的操作：器，具有如下的操作：MOVEk：将光：将光标移移动到第到第k个字符之前，如果个字符之前，如果k=0，那么移，那么移动到文档开到文档开头PRINTn：输出光出光标之后的之后的n个字符个字符PREV：光：光标前移一位前移一位NEXT：光：光标后移一位后移一位4（1）请基于基于线性数据性数据结

3、构构设计一套合理的算法，来一套合理的算法，来实现这些操作，并且分析每个操作的性能。假定：文些操作，并且分析每个操作的性能。假定：文本最大的本最大的长度度为Lh2：14那么，那么，为了了满足足红黑黑树性性质，我，我们令令T2的根的根结点点为多多(h1-h2+1)黑黑结点。我点。我们可以利用可以利用红黑黑树的的删除算除算法中法中对双黑双黑结点点处理的方法同理的方法同样处理理T2的根的根结点，点，即令其从即令其从(h1-h2+1)黑黑结点，点，变为(h1-h2)黑黑结点点直直至至为单黑黑结点，那么就点，那么就变成了一棵正常的成了一棵正常的红黑黑树。15双黑结点的调整双黑结点的调整假假设X是左子是左子

4、结点（若点（若X为右子右子结点，点，处理方法理方法类似，不重述）似，不重述）情况情况1：双黑结点的兄弟C是红色，执行旋转操作（黑红）！推出：推出：B结结点也一定是黑色，点也一定是黑色，和和也是黑色也是黑色旋旋转转：兄弟：兄弟节节点点为为根根变变黑，父黑，父节节点点变红变红X结结点仍是点仍是“双黑双黑”结结点，点，转转化化为为情况情况2,3北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法BCXXBC双黑结点16情况情况2：兄弟是黑色,且有两个黑子结点（黑黑黑）执执行行换换色操作，把色操作，把C

5、着着红红色，色，B着黑色着黑色如果如果B原原为红为红色，色，则则算法算法结结束束否否则则，对对B继续继续作作“双黑双黑”调调整（整（为为什么？什么？）BXEDCBCEDX北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法有可能继续双黑处理17双黑结点的调整双黑结点的调整情况情况3：兄弟C是黑色，且子结点有红色(黑黑红)(a)旋旋转重构：重构：侄子侄子红结点八字外撇点八字外撇将兄弟将兄弟结结点点C提上去，提上去，继继承原父承原父结结点的点的颜颜色色然后把然后把B着着为为黑色，黑色，D着着为为黑色

6、，其他黑色，其他颜颜色不色不变变即可即可BDXCDXBC单旋转调整单旋转调整北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法18(b)旋旋转重构：重构：侄子侄子红结点同点同边顺将将C结结点旋点旋转为转为D结结点的父点的父结结点，点，C继继承原子根承原子根B的的颜颜色，色，B着着为为黑色黑色BXEDCDBCXE北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法1911.6.3插入算法插入算法先

7、先调调用用BST的插入算法，将待插的插入算法，将待插记录记录定位定位新记录X着色为红色若父若父结结点是黑色，点是黑色，则则算法算法结结束束否否则则，双红调整6 6386 6384XAAX插入插入4北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法20双红调整双红调整1：红黑旋转红黑旋转情况情况1：新增结点X的叔父结点是黑色，或者NIL调调整后：祖整后：祖节节点点变为变为黑，父、叔黑，父、叔节节点点变为红变为红！每个每个结结点的点的阶阶都保持原都保持原值值，调调整完成整完成保持保持树树的的稳稳定

8、性！定性！X以祖结点为轴旋以祖结点为轴旋转父结点转父结点AXBB BA AC CC C北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法214种形式的结构调整种形式的结构调整原原则则：保持：保持BST的中序性的中序性质质2 2466 624264 4提升操作旋转操作北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法22双红调整双红调整2：红红换色红红换色情况情况2：新增结点X的叔父结点也是红色

9、X父祖换色父祖换色叔父变黑叔父变黑AXBB BA AC CC对B继续红红检查北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法如果B是根节点，则只叔父节点变色，根节点不变！2324第第10章章检索索第第11章章索引索引第第12章章高高级数据数据结构构25提供广提供广义表的下列操作表的下列操作make_GList(a,b,c.);将任意多个广将任意多个广义表表连接成一个新的广接成一个新的广义表表head(gList);取广取广义表表头tail(gList);取广取广义表尾；表尾；要求要求设计一个

10、算法，将广一个算法，将广义表置逆，不能使用其他数表置逆，不能使用其他数据据结构。比如，构。比如，对于广于广义表表(a,(a,b,c),(b,(d),置逆之置逆之后的后的结果果为：(d),b),(c,b,a),a);26解：直接用解：直接用递归即可。即可。GListreverse(gList)Returnmake_Glist(reverse(tail(gList),reverse(head(gList)272.假定假定经过分分词后的网后的网页已已经形成了倒排索引，使用形成了倒排索引，使用trie树作作为词典，叶子典，叶子结点会有指向倒排表的指点会有指向倒排表的指针，倒排表是按照网倒排表是按照网页

11、文档文档id（连续的整数的整数值）排好序的。）排好序的。现在需要系在需要系统支持支持简单的布的布尔查询。请写出以下算写出以下算法的代法的代码或或伪代代码，并分析复，并分析复杂度度28I.Keyword1andkeyword2II.Keyword2andnotkeyword2III.如果需要支持相如果需要支持相邻查询，例如，例如keywordandkeword2neardistance，distance代表代表词与与词之之间的距离，需要怎的距离，需要怎样更改倒排索引表，支更改倒排索引表，支持持这一需求？一需求？29答案答案1、用、用trie树可以在可以在O(length(string)的的时间内

12、找到内找到单词所所对应的倒排表的位置。的倒排表的位置。根据根据这一点，一点，设计如下代如下代码。设A1.AN为第一个第一个单词的文档，的文档，B1.BM为第二个第二个单词的文档的文档303132333.AVL树和和红黑黑树的高度的高度A.高度高度为h的的AVL树上的最少上的最少结点个数是多少？最多点个数是多少？最多结点个数是多少？点个数是多少？B.高度高度为h的的红黑黑树上的最少上的最少结点个数是多少？最多点个数是多少？最多结点个数是多少？点个数是多少？3435BBh=5，为奇数时，树的阶为，为奇数时，树的阶为k=inth/2k=2k=136h=6，为偶数时，树的阶为，为偶数时，树的阶为k=i

13、nth/2k=3Bk=2k=137Bh=6，为偶数时，树的阶为，为偶数时，树的阶为k=inth/2k=3k=2B384.KD树和和PR四分四分树都可以支持区域都可以支持区域查找。找。请问两者有什么两者有什么优劣劣势？391、k-d树树 k-d树是一种用于多是一种用于多维检索的索的树结构，它的每构，它的每一一层都根据特定关都根据特定关键码将将对象空象空间分解分解为两个两个顶层结点按一个点按一个维划分划分第二第二层结点按照另一点按照另一维进行划分行划分以此以此类推在各个推在各个维之之间反复反复进行划分行划分最最终当一个当一个结点中的点数少于点中的点数少于给点的最大点数点的最大点数时，划分划分结束束

14、识别器(discriminator)在每一在每一层用来用来进行决策的关行决策的关键码称称为识别器器对于于k维关关键码，在第，在第i层把把识别器定器定义为imodk例如，例如，对一个三一个三维的关的关键码做做检索，索，3个关个关键码（x，y，z）标号分号分别为0、1、2第一第一层是是0mod3=0，所以使用关，所以使用关键码x，第二第二层是是1mod3=1，所以使用关，所以使用关键码y结点的分配结点的分配在在结点分配的点分配的时候首先比候首先比较该层的的识别器器如果关如果关键码小于小于识别器的器的值就放到左子就放到左子树中中否否则放到右子放到右子树然后在下一然后在下一层使用新的使用新的识别器来判

15、断每个器来判断每个结点点的的归属属识别器的器的值应该尽量使得被划分的尽量使得被划分的结点大点大约一一半落在左子半落在左子树，另一半落在右子，另一半落在右子树K-DK-D树示例树示例K-D树的空间分解树的空间分解上上图是一个二是一个二维的的k-d树，取，取值范范围为100100之内之内k-dk-d树的每个内部的每个内部结点点把当前的空把当前的空间划分划分为两两块，交替地，交替地对两个两个维进行划分行划分根根结点把空点把空间划分成两部分划分成两部分其子其子结点点进一步把空一步把空间划分成更小的部分划分成更小的部分子子结点的划分点的划分线不会穿不会穿过根根结点的划分点的划分线 k-d树中的中的这些些

16、结点最点最终把空把空间分解分解为矩形矩形这些矩形是些矩形是结点可能落到的各子点可能落到的各子树范范围K-D树的不足 其其结构与构与输入数据的入数据的顺序也是有关的序也是有关的有可能有可能导致它每个子致它每个子树的元素分配不均衡的元素分配不均衡Bentley和和Friedman发明了明了adaptivek-d树，类似于似于BST所有的数据所有的数据记录都存都存储在叶在叶结点点内部内部结点只是用来在各个点只是用来在各个维之之间导航航每一个每一个识别器的器的选择不再依不再依赖于于输入的数据入的数据尽量选择让左右子树的记录数目相等的值 2、PR四分树四分树 PR四分四分树，即点，即点-区域四分区域四分

17、树（Point-RegionQuadtree）：每个内部每个内部结点都恰好有四个子点都恰好有四个子结点点每个内部每个内部结点将当前空点将当前空间均等地划分均等地划分为四个区域四个区域NWNW（西北）、（西北）、NENE（东北）、北）、SWSW（西南）和（西南）和SESE（东南）南）PR四分四分树也是也是对对象空象空间的划分的划分完全四叉完全四叉树PR四分树对空间的划分四分树对空间的划分每个内部每个内部结点将当前空点将当前空间均等地划分均等地划分为四个区四个区如果子区域包含的数据点数大于如果子区域包含的数据点数大于1，那么就把，那么就把该区区域域继续均等地划分均等地划分为四个区域四个区域依次依次

18、类推，直到每个区域所包含的数据点不超推，直到每个区域所包含的数据点不超过一个一个为止止PR树的图示PR树的划分树的划分上上图所表示的所表示的PR四分四分树，其，其对象空象空间为128 128，并包含点并包含点A、B、C、D、E、F和和G根根结点的四个子点的四个子结点把整个空点把整个空间平分平分为四份大四份大小小为64 64的子空的子空间NW，NE，SW，SENW（包含三个数据点）和（包含三个数据点）和SE(包含两个数据点包含两个数据点)需要需要进一步分裂一步分裂PR树的插入如果如果这个位置的叶个位置的叶结点没有包含其他的数据点点没有包含其他的数据点那么我那么我们就把就把记录插入插入这里；里；如

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

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

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

22、到旁边时，再，再请向向监考老考老师询问。监考老考老师收卷清点无收卷清点无误，并宣布，并宣布“全班同学都可以离开了全班同学都可以离开了”以后方可集体离开。注意，不要把以后方可集体离开。注意，不要把试卷卷题带出考出考场，否，否则将将计零分。零分。55第第1章章 概论概论一一.重要概念重要概念1.抽象数据抽象数据结构构2.数据数据逻辑结构构3.数据存数据存储结构构4.算法算法5.算法分析算法分析(时间代价、空代价、空间代价代价)二二.方法方法1.根据二元根据二元组画出画出图示示逻辑结构构(注意注意边的方向的方向)2.根据要求根据要求设计数据数据结构构3.算法的算法的渐进分析方法分析方法4.大大O表示

23、法表示法（不要求掌握大（不要求掌握大、大、大表示法）表示法）56第第2章章 线性表线性表一一.概念概念1.线性表性表2.单链表表3.双双链表表4.循循环表表二二.方法方法1.顺序表上序表上实现的运算的运算2.链表上表上实现的运算的运算(指指针操作的正确性操作的正确性)3.顺序表和序表和链表的比表的比较57第第3章章 栈与队列栈与队列一一.概念概念1.栈2.队列列3.循循环队列列二二.方法方法1.栈的性的性质，用，用栈来生成序列来生成序列2.队列的性列的性质，用，用队列列生成生成序列序列3.栈的的顺序序实现4.循循环队列的列的实现5.表达式求表达式求值(中中缀表达式表达式转后后缀表达式的算法、表

24、达式的算法、后后缀表达式求表达式求值算法算法)6.栈在在递归调用及用及转换中的中的应用用58第第4章章 字符串字符串一一.概念概念1.串串2.模式匹配模式匹配二二.方法方法1.串的基本操作串的基本操作2.串的存串的存储及运算及运算3.串的串的KMP快速模式匹配算法，求特征向量数快速模式匹配算法，求特征向量数组（N数数组）和利用）和利用N向量完成匹配的方法向量完成匹配的方法59第第5章章 二叉树二叉树一一.概念概念1.二叉二叉树2.二叉二叉树的深度的深度优先周游先周游3.二叉排序二叉排序树4.堆堆5.Huffman树、Huffman编码各种各种结构的构的节点个数与高度、点个数与高度、层次、度等关

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

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

27、优先先（2）宽度度优先先673.图的生成的生成树与最小生成与最小生成树从某一点出从某一点出发，按深度，按深度优先或先或宽度度优先周游的生成先周游的生成树最小生成最小生成树Prim算法算法Kruskal算法算法(避圈法避圈法)4.拓扑排序拓扑排序:给定定图，找出若干个或所有拓扑序列，找出若干个或所有拓扑序列5.最短路径最短路径:Dijkstra算法、算法、Floyd算法算法6.Dijkstra算法、算法、Prim算法、算法、Kruskal算法都是典型算法都是典型的的贪心法（退化的心法（退化的动态规划法）划法）68第第8章章 内排序内排序1.重点排序算法：直接插入法、重点排序算法：直接插入法、Sh

28、ell排序、排序、快快速排序、速排序、基数排序、基数排序、归并排序并排序2.算法分析算法分析基于比基于比较次数和移位次数分析最好、最坏的次数和移位次数分析最好、最坏的时间、空、空间直接插入法、二分法插入排序、起泡排序、直接直接插入法、二分法插入排序、起泡排序、直接选择、快、快速排序、基数排序、速排序、基数排序、归并排序并排序记住各种排序方法的平均住各种排序方法的平均时间3.各种排序方法的局部修改和混合各种排序方法的局部修改和混合应用用69第9章 文件管理和外排序方法及算法方法及算法1.置置换选择排序排序2.多路多路归并并(败者者树，最佳，最佳归并并树，多路，多路归并的并的读盘和写和写盘次数次数

29、)70第10章 检索一一.概念概念1.平均平均检索索长度度2.二分法二分法检索索3.散列表、同散列表、同义词、碰、碰撞、堆撞、堆积二二.方法方法1.二分法二分法检索的判定索的判定树、查找某个找某个结点的比点的比较次数次数2.散列表散列表:1)散列函数散列函数选择(除余法、平方取中法、折叠法除余法、平方取中法、折叠法)2)冲突处理方法(分离同义词子表、线性探测、双散列函数)三三.散列算法（散列算法（查找、插入、找、插入、删除，除，对墓碑的墓碑的处理理71第11章 索引技术一一.概念概念1.顺序文件序文件2.散列文件散列文件3.倒排文件倒排文件4.静静态索引索引结构构5.动态索引索引结构构(B树)

30、6.红黑黑树二二.方法（不考算法）方法（不考算法）1.B树、B+树的插入与的插入与删除除(注意保持性注意保持性质，特，特别是等高；是等高；以及子以及子结点和关点和关键码个数的上下限制个数的上下限制)2.B树/B+树的的读盘和写和写盘次数分析次数分析723.B树/B+树的效率分析的效率分析B树中关中关键码没有重复，父没有重复，父结点中的关点中的关键码是其子是其子结点的点的分界；分界；B+中最底中最底层是关是关键码的一个全集，往根的方向一的一个全集，往根的方向一层层复写。复写。B树插入插入与与删除除、B+树插入插入与与删除除4.红黑黑树的插入方法。的插入方法。删除算法不考，可考性除算法不考，可考性

31、质插入算法首先是采用插入算法首先是采用BST的方法把的方法把结点插入到位，然后注点插入到位，然后注意意调整。尤其是整。尤其是“红红”冲突的解决，注意有冲突的解决，注意有换色、重构色、重构73第12章 高级数据结构一一.概念概念1.多多维数数组和稀疏矩和稀疏矩阵2.广广义表表3.Trie树4.Patricia5.AVL树6.伸展伸展树二二.方法（不考具体算法，但要求掌握方法并方法（不考具体算法，但要求掌握方法并应用）用）1.特殊矩特殊矩阵和稀疏矩和稀疏矩阵的的计算。算。2.广广义表的表的结构和周游构和周游3.字符字符树：Trie树和和Patricia树744.最佳二叉搜索最佳二叉搜索树，理解平均

32、，理解平均检索索长度最度最优的特点的特点5.AVL平衡二叉平衡二叉树的插入方法：的插入方法：LL、LR、RL、RR的四种旋的四种旋转调整。不考整。不考删除算法，但可考性除算法，但可考性质6.伸展伸展树及其及其简单应用：用：伸展伸展树在搜索在搜索过程中旋程中旋转调整整结构，使构，使访问最最频繁的繁的结点点靠近靠近树结构的根。伸展构的根。伸展树的旋的旋转分分为：单旋旋转、一字形旋、一字形旋转和之字形旋和之字形旋转。注意伸展。注意伸展树的的变种，例如半伸展种，例如半伸展树。splay树的插入、的插入、删除以及区除以及区间操作都要求掌握操作都要求掌握75再见再见联系信息：系信息：电子子邮件：件：电话：62754785办公地点：理科公地点：理科2号楼号楼2307室室76此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢