《第10-12章习题课分析.ppt》由会员分享，可在线阅读，更多相关《第10-12章习题课分析.ppt（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第第10-12章章习题课习题课宋国杰宋国杰北京大学信息科学技北京大学信息科学技术学院学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法第第10章章检索索第第11章章索引索引第第12章章高高级数据数据结构构2第1题请设计一个字典，支持下列的操作：INSERTx：插入一个字符串xFINDx：返回一个bool 值，表示字符串是否存在请设计一个这样的字典，并且介绍其优点和缺点。注意：字符串本身可能比较长；字符串的个数在105个左右。3答案考考查知知识点：点：开散列开散列方案：考方案：考虑到字符串
2、很多的因素，采用到字符串很多的因素，采用拉拉链式式Hash表表解决，解决，用一个用一个Hash函数函数进行行寻址址；考考虑到字符串很到字符串很长的因素，的因素，在插入的在插入的时候用另一个候用另一个Hash函数来函数来给每一个字符串一个每一个字符串一个ID，相同的字符串相同的字符串ID一定相同，不同的字符串也有一定概率一定相同，不同的字符串也有一定概率ID相同，相同，在在查找找时，仅需考需考虑ID相同的串来确定是否串相同的串来确定是否串X存在，存在，避免了大范避免了大范围的的查找，和大量找，和大量长字符串匹配字符串匹配。4第2题现在有一个文本在有一个文本编辑器，具有如下的操作：器，具有如下的操
3、作：MOVEk：将光：将光标移移动到第到第k个字符之前，如果个字符之前，如果k=0，那么移，那么移动到文档开到文档开头PRINTn：输出光出光标之后的之后的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,317北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法BCXXBC双黑结点情况情况2：兄弟是黑色,且有两个黑子结点（黑黑黑）执执行行换换色操作，把色操作，把C着着红红色，色，B着黑色着黑色如果如果B原原为红为红色，色，则则算法算法结结束束否否则则，对对B继续继续作作“双黑双黑”调调整（整（为为什么？什么？）BXEDCBCEDX18北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法有
6、可能继续双黑处理双黑结点的调整双黑结点的调整情况情况3：兄弟C是黑色，且子结点有红色(黑黑红)(a)旋旋转重构：重构：侄子侄子红结点八字外撇点八字外撇将兄弟将兄弟结结点点C提上去，提上去，继继承原父承原父结结点的点的颜颜色色然后把然后把B着着为为黑色，黑色，D着着为为黑色，其他黑色，其他颜颜色不色不变变即可即可19BDXCDXBC单旋转调整单旋转调整北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法(b)旋旋转重构：重构：侄子侄子红结点同点同边顺将将C结结点旋点旋转为转为D结结点的父点的父结结
7、点，点，C继继承原子根承原子根B的的颜颜色，色，B着着为为黑色黑色BXEDCDBCXE20北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法11.6.3插入算法插入算法先先调调用用BST的插入算法，将待插的插入算法，将待插记录记录定位定位新记录X着色为红色若父若父结结点是黑色，点是黑色，则则算法算法结结束束否否则则，双红调整6 6 6 66 6 6 6XAAX插入插入4 421北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构
8、与算法数据结构与算法数据结构与算法双红调整双红调整1：红黑旋转红黑旋转情况情况1：新增结点X的叔父结点是黑色，或者NIL调调整后：祖整后：祖节节点点变为变为黑，父、叔黑，父、叔节节点点变为红变为红！每个每个结结点的点的阶阶都保持原都保持原值值，调调整完成整完成保持保持树树的的稳稳定性！定性！以祖结点为轴旋以祖结点为轴旋转父结点转父结点B BA AC CC C22北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法4种形式的结构调整种形式的结构调整原原则则：保持：保持BST的中序性的中序性质质2
9、26 64 423提升操作旋转操作北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法双红调整双红调整2：红红换色红红换色情况情况2：新增结点X的叔父结点也是红色父祖换色父祖换色叔父变黑叔父变黑B BA AC C24对B继续红红检查北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法如果B是根节点，则只叔父节点变色，根节点不变！25第第10章章检索索第第11章章索引索引第第12章章高高级数据数据结
10、构构26提供广提供广义表的下列操作表的下列操作make_GList(a,b,c.);将任意多个广将任意多个广义表表连接成一个新的广接成一个新的广义表表head(gList);取广取广义表表头tail(gList);取广取广义表尾；表尾；要求要求设计一个算法，将广一个算法，将广义表置逆，不能使用其他数表置逆，不能使用其他数据据结构。比如，构。比如，对于广于广义表表(a,(a,b,c),(b,(d),置逆之置逆之后的后的结果果为：(d),b),(c,b,a),a);27解：直接用解：直接用递归即可。即可。GListreverse(gList)Returnmake_Glist(reverse(tai
11、l(gList),reverse(head(gList)282.假定假定经过分分词后的网后的网页已已经形成了倒排索引，使用形成了倒排索引，使用trie树作作为词典，叶子典，叶子结点会有指向倒排表的指点会有指向倒排表的指针，倒排表是按照网倒排表是按照网页文档文档id（连续的整数的整数值）排好序的。）排好序的。现在需要系在需要系统支持支持简单的布的布尔查询。请写出以下算写出以下算法的代法的代码或或伪代代码，并分析复，并分析复杂度度29I.Keyword1andkeyword2II.Keyword2andnotkeyword2III.如果需要支持相如果需要支持相邻查询，例如，例如keywordand
12、keword2neardistance，distance代表代表词与与词之之间的距离，需要怎的距离，需要怎样更改倒排索引表，支更改倒排索引表，支持持这一需求？一需求？30答案答案1、用用trie树可以在可以在O(length(string)的的时间内找到内找到单词所所对应的倒排表的位置。的倒排表的位置。根据根据这一点，一点，设计如下代如下代码。设A1.AN为第一个第一个单词的文档，的文档，B1.BM为第二个第二个单词的文档的文档313233343.AVL树和和红黑黑树的高度的高度A.高度高度为h的的AVL树上的最少上的最少结点个数是多少？最多点个数是多少？最多结点个数是多少？点个数是多少？B.
13、高度高度为h的的红黑黑树上的最少上的最少结点个数是多少？最多点个数是多少？最多结点个数是多少？点个数是多少？353637BBh=5，为奇数时，树的阶为，为奇数时，树的阶为k=inth/2k=2k=138h=6，为偶数时，树的阶为，为偶数时，树的阶为k=inth/2k=3Bk=2k=139Bh=6，为偶数时，树的阶为，为偶数时，树的阶为k=inth/2k=3k=2B4.KD树和和PR四分四分树都可以支持区域都可以支持区域查找。找。请问两者有什么两者有什么优劣劣势？401、k-d树树 k-d树是一种用于多是一种用于多维检索的索的树结构，它的每构，它的每一一层都根据特定关都根据特定关键码将将对象空象
14、空间分解分解为两个两个顶层结点按一个点按一个维划分划分第二第二层结点按照另一点按照另一维进行划分行划分以此以此类推在各个推在各个维之之间反复反复进行划分行划分最最终当一个当一个结点中的点数少于点中的点数少于给点的最大点数点的最大点数时，划分划分结束束识别器(discriminator)在每一在每一层用来用来进行决策的关行决策的关键码称称为识别器器对于于k维关关键码，在第，在第i层把把识别器定器定义为imodk例如，例如，对一个三一个三维的关的关键码做做检索，索，3个关个关键码（x，y，z）标号分号分别为0、1、2第一第一层是是0mod3=0，所以使用关，所以使用关键码x，第二第二层是是1mod
15、3=1，所以使用关，所以使用关键码y结点的分配结点的分配在在结点分配的点分配的时候首先比候首先比较该层的的识别器器如果关如果关键码小于小于识别器的器的值就放到左子就放到左子树中中否否则放到右子放到右子树然后在下一然后在下一层使用新的使用新的识别器来判断每个器来判断每个结点点的的归属属识别器的器的值应该尽量使得被划分的尽量使得被划分的结点大点大约一一半落在左子半落在左子树，另一半落在右子，另一半落在右子树K-DK-D树示例树示例K-D树的空间分解树的空间分解上上图是一个二是一个二维的的k-d树，取，取值范范围为100100之内之内k-dk-d树的每个内部的每个内部结点点把当前的空把当前的空间划分
16、划分为两两块，交替地，交替地对两个两个维进行划分行划分根根结点把空点把空间划分成两部分划分成两部分其子其子结点点进一步把空一步把空间划分成更小的部分划分成更小的部分子子结点的划分点的划分线不会穿不会穿过根根结点的划分点的划分线 k-d树中的中的这些些结点最点最终把空把空间分解分解为矩形矩形这些矩形是些矩形是结点可能落到的各子点可能落到的各子树范范围K-D树的不足 其其结构与构与输入数据的入数据的顺序也是有关的序也是有关的有可能有可能导致它每个子致它每个子树的元素分配不均衡的元素分配不均衡Bentley和和Friedman发明了明了adaptivek-d树，类似于似于BST所有的数据所有的数据记
17、录都存都存储在叶在叶结点点内部内部结点只是用来在各个点只是用来在各个维之之间导航航每一个每一个识别器的器的选择不再依不再依赖于于输入的数据入的数据尽量选择让左右子树的记录数目相等的值 2、PR四分树四分树 PR四分四分树，即点，即点-区域四分区域四分树（Point-RegionQuadtree）：每个内部每个内部结点都恰好有四个子点都恰好有四个子结点点每个内部每个内部结点将当前空点将当前空间均等地划分均等地划分为四个区域四个区域NWNW（西北）、（西北）、NENE（东北）、北）、SWSW（西南）和（西南）和SESE（东南）南）PR四分四分树也是也是对对象空象空间的划分的划分完全四叉完全四叉树P
18、R四分树对空间的划分四分树对空间的划分每个内部每个内部结点将当前空点将当前空间均等地划分均等地划分为四个区四个区如果子区域包含的数据点数大于如果子区域包含的数据点数大于1，那么就把，那么就把该区区域域继续均等地划分均等地划分为四个区域四个区域依次依次类推，直到每个区域所包含的数据点不超推，直到每个区域所包含的数据点不超过一个一个为止止PR树的图示PR树的划分树的划分上上图所表示的所表示的PR四分四分树，其，其对象空象空间为128 128，并包含点并包含点A、B、C、D、E、F和和G根根结点的四个子点的四个子结点把整个空点把整个空间平分平分为四份大四份大小小为64 64的子空的子空间NW，NE，
19、SW，SENW（包含三个数据点）和（包含三个数据点）和SE(包含两个数据点包含两个数据点)需要需要进一步分裂一步分裂PR树的插入如果如果这个位置的叶个位置的叶结点没有包含其他的数据点点没有包含其他的数据点那么我那么我们就把就把记录插入插入这里；里；如果如果这个叶个叶结点中已点中已经包含包含P了了(或者一个具有或者一个具有P的坐的坐标的的记录)那么就那么就报告告记录重复；重复；如果叶如果叶结点已点已经包含另一条包含另一条记录X那么就必那么就必须继续分解分解这个个结点，直到已存在的点，直到已存在的记录X和和P分分别进入不同的入不同的结点点为止止PR树的删除产生的合并删除结点删除结点D导致的区域合并
20、导致的区域合并PR树的不足无法做到有效率的插入无法做到有效率的插入删除，很有可能出除，很有可能出现最坏情况；最坏情况；空空间动态分配，但是增加分配，但是增加/减少的量并不减少的量并不稳定；定；处理分布比理分布比较均匀的情况均匀的情况时，效果并不差。，效果并不差。53考考试大大纲54关于考试时间和地点和地点时间：2015年年1月月7日日上午上午8:30-10:30地点：一教地点：一教201考考试题型型填空、填空、选择、辨析与、辨析与简答、数据答、数据结构或算法的构或算法的设计和分析、和分析、数学数学证明明（1）数据）数据结构构/算法算法设计与分析与分析题只要写明基本思想、无只要写明基本思想、无歧
21、歧义即可，必要即可，必要时加上足加上足够的注的注释。（2）对于算法中直接使用的于算法中直接使用的类和函数（例如和函数（例如栈、队列的列的函数），函数），应该先写先写ADT，并，并简单说明算法中用到的重要函明算法中用到的重要函数的功能、入口参数、出口参数。数的功能、入口参数、出口参数。范范围：1-12章章55考场安排和注意事项考场安排和注意事项请随身随身带好您的学生好您的学生证，笔和涂改工具参加考，笔和涂改工具参加考试。考考试形式形式为闭卷，可以使用卷，可以使用计算器算器考前考前10分分钟，请大家把大家把书包等放在教室前面的包等放在教室前面的讲台和窗台上，台和窗台上，注意在注意在试卷卷纸和有效答
22、和有效答题纸上写上姓名和学号。上写上姓名和学号。统一一发草稿草稿纸，不，不够可以随可以随时举手要。手要。请大家注意考大家注意考场纪律，不要交律，不要交头接耳，私下接耳，私下讨论。考。考试时对试题有疑有疑问，可以，可以举手，待手，待监考老考老师来到旁来到旁边时，再，再请向向监考老考老师询问。监考老考老师收卷清点无收卷清点无误，并宣布，并宣布“全班同学都可以离开了全班同学都可以离开了”以后方可集体离开。注意，不要把以后方可集体离开。注意，不要把试卷卷题带出考出考场，否，否则将将计零分。零分。56第第1章章 概论概论一一.重要概念重要概念1.抽象数据抽象数据结构构2.数据数据逻辑结构构3.数据存数据
23、存储结构构4.算法算法5.算法分析算法分析(时间代价、空代价、空间代价代价)二二.方法方法1.根据二元根据二元组画出画出图示示逻辑结构构(注意注意边的方向的方向)2.根据要求根据要求设计数据数据结构构3.算法的算法的渐进分析方法分析方法4.大大O表示法表示法（不要求掌握大（不要求掌握大、大、大表示法）表示法）57第第2章章 线性表线性表一一.概念概念1.线性表性表2.单链表表3.双双链表表4.循循环表表二二.方法方法1.顺序表上序表上实现的运算的运算2.链表上表上实现的运算的运算(指指针操作的正确性操作的正确性)3.顺序表和序表和链表的比表的比较58第第3章章 栈与队列栈与队列一一.概念概念1
24、.栈2.队列列3.循循环队列列二二.方法方法1.栈的性的性质，用，用栈来生成序列来生成序列2.队列的性列的性质，用，用队列列生成生成序列序列3.栈的的顺序序实现4.循循环队列的列的实现5.表达式求表达式求值(中中缀表达式表达式转后后缀表达式的算法、表达式的算法、后后缀表达式求表达式求值算法算法)6.栈在在递归调用及用及转换中的中的应用用59第第4章章 字符串字符串一一.概念概念1.串串2.模式匹配模式匹配二二.方法方法1.串的基本操作串的基本操作2.串的存串的存储及运算及运算3.串的串的KMP快速模式匹配算法，求特征向量数快速模式匹配算法，求特征向量数组（N数数组）和利用）和利用N向量完成匹配
25、的方法向量完成匹配的方法60第第5章章 二叉树二叉树一一.概念概念1.二叉二叉树2.二叉二叉树的深度的深度优先周游先周游3.二叉排序二叉排序树4.堆堆5.Huffman树、Huffman编码各种各种结构的构的节点个数与高度、点个数与高度、层次、度等关系次、度等关系换算算二二.方法方法1二叉二叉树的的链式存式存储（1）二叉）二叉链表表（2）带父指父指针的三重的三重链表表612.二叉二叉树的的顺序存序存储完全二叉完全二叉树的的顺序存序存储3.二叉二叉树的深度的深度优先周游先周游4.BST树的插入与的插入与删除除5.构造构造Huffman树和和Huffman编码6.堆的建立与堆的建立与维护过程程62
26、636465第第6章章 树树一一.概念概念树、森林、森林、先根、后根、先根、后根、层次周游次周游K叉叉树二二.方法方法1.森林与二叉森林与二叉树相互相互转换2森林的森林的链式存式存储(1)转换为相相应的二叉的二叉树，用二叉，用二叉链表表示表表示(2)父指针表示法、(3)子结点表表示法(4)等价类和并查算法的应用663.森林的深度森林的深度优先周游（先周游（递归），可能），可能结合合应用用4.森林的森林的顺序存序存储及其构造及其构造5.二叉二叉树和森林的和森林的层次周游次周游(用用队列列)，可能，可能结合合应用用67第第7章章 图图一一.概念概念1.图的相关概念：的相关概念：连通性、通性、连通分
27、量、通分量、边与与顶点关系等点关系等2.深度周游深度周游、宽度周游度周游3.图的生成的生成树、生成、生成树林、最小生成林、最小生成树二二.方法及算法方法及算法1.图的存的存储方法方法:（1）相相邻矩矩阵（2）邻接表接表2.图的周游的周游:1）深度深度优先先（2）宽度度优先先683.图的生成的生成树与最小生成与最小生成树从某一点出从某一点出发，按深度，按深度优先或先或宽度度优先周游的生成先周游的生成树最小生成最小生成树Prim算法算法Kruskal算法算法(避圈法避圈法)4.拓扑排序拓扑排序:给定定图，找出若干个或所有拓扑序列，找出若干个或所有拓扑序列5.最短路径最短路径:Dijkstra算法、
28、算法、Floyd算法算法6.Dijkstra算法、算法、Prim算法、算法、Kruskal算法都是典型算法都是典型的的贪心法（退化的心法（退化的动态规划法）划法）69第第8章章 内排序内排序1.重点排序算法：直接插入法、重点排序算法：直接插入法、Shell排序、排序、快快速排序、速排序、基数排序、基数排序、归并排序并排序2.算法分析算法分析基于比基于比较次数和移位次数分析最好、最坏的次数和移位次数分析最好、最坏的时间、空、空间直接插入法、二分法插入排序、起泡排序、直接直接插入法、二分法插入排序、起泡排序、直接选择、快、快速排序、基数排序、速排序、基数排序、归并排序并排序记住各种排序方法的平均住
29、各种排序方法的平均时间3.各种排序方法的局部修改和混合各种排序方法的局部修改和混合应用用70第9章 文件管理和外排序方法及算法方法及算法1.置置换选择排序排序2.多路多路归并并(败者者树，最佳，最佳归并并树，多路，多路归并的并的读盘和写和写盘次数次数)71第10章 检索一一.概念概念1.平均平均检索索长度度2.二分法二分法检索索3.散列表、同散列表、同义词、碰、碰撞、堆撞、堆积二二.方法方法1.二分法二分法检索的判定索的判定树、查找某个找某个结点的比点的比较次数次数2.散列表散列表:1)散列函数散列函数选择(除余法、平方取中法、折叠法除余法、平方取中法、折叠法)2)冲突处理方法(分离同义词子表
30、、线性探测、双散列函数)三三.散列算法（散列算法（查找、插入、找、插入、删除，除，对墓碑的墓碑的处理理72第11章 索引技术一一.概念概念1.顺序文件序文件2.散列文件散列文件3.倒排文件倒排文件4.静静态索引索引结构构5.动态索引索引结构构(B树)6.红黑黑树二二.方法（不考算法）方法（不考算法）1.B树、B+树的插入与的插入与删除除(注意保持性注意保持性质，特，特别是等高；是等高；以及子以及子结点和关点和关键码个数的上下限制个数的上下限制)2.B树/B+树的的读盘和写和写盘次数分析次数分析733.B树/B+树的效率分析的效率分析B树中关中关键码没有重复，父没有重复，父结点中的关点中的关键码
31、是其子是其子结点的点的分界；分界；B+中最底中最底层是关是关键码的一个全集，往根的方向一的一个全集，往根的方向一层层复写。复写。B树插入插入与与删除除、B+树插入插入与与删除除4.红黑黑树的插入方法。的插入方法。删除算法不考，可考性除算法不考，可考性质插入算法首先是采用插入算法首先是采用BST的方法把的方法把结点插入到位，然后注点插入到位，然后注意意调整。尤其是整。尤其是“红红”冲突的解决，注意有冲突的解决，注意有换色、重构色、重构74第12章 高级数据结构一一.概念概念1.多多维数数组和稀疏矩和稀疏矩阵2.广广义表表3.Trie树4.Patricia5.AVL树6.伸展伸展树二二.方法（不考
32、具体算法，但要求掌握方法并方法（不考具体算法，但要求掌握方法并应用）用）1.特殊矩特殊矩阵和稀疏矩和稀疏矩阵的的计算。算。2.广广义表的表的结构和周游构和周游3.字符字符树：Trie树和和Patricia树754.最佳二叉搜索最佳二叉搜索树，理解平均，理解平均检索索长度最度最优的特点的特点5.AVL平衡二叉平衡二叉树的插入方法：的插入方法：LL、LR、RL、RR的四种旋的四种旋转调整。不考整。不考删除算法，但可考性除算法，但可考性质6.伸展伸展树及其及其简单应用：用：伸展伸展树在搜索在搜索过程中旋程中旋转调整整结构，使构，使访问最最频繁的繁的结点点靠近靠近树结构的根。伸展构的根。伸展树的旋的旋转分分为：单旋旋转、一字形旋、一字形旋转和之字形旋和之字形旋转。注意伸展。注意伸展树的的变种，例如半伸展种，例如半伸展树。splay树的插入、的插入、删除以及区除以及区间操作都要求掌握操作都要求掌握7677再见再见联系信息：系信息：电子子邮件：件：电话：62754785办公地点：理科公地点：理科2号楼号楼2307室室