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

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

1、1第第10-12章章习题课习题课宋国杰宋国杰北京高校信息科学技术学院北京高校信息科学技术学院gjsongpku.edu 北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法第第10章章检索检索第第11章章索引索引第第12章章高级数据结构高级数据结构2第1题请设计一个字典，支持下列的操作：INSERTx：插入一个字符串xFINDx：返回一个bool值，表示字符串是否存在请设计一个这样的字典，并且介绍其优点和缺点。留意：字符串本身可能比较长；字符串的个数在105个左右。3答案考查学问点：开散列考查学

2、问点：开散列方案：考虑到字符串很多的因素，接受拉链式方案：考虑到字符串很多的因素，接受拉链式Hash表解决，用一个表解决，用一个Hash函数进行寻址；函数进行寻址；考虑到字符串很长的因素，在插入的时候用另一个考虑到字符串很长的因素，在插入的时候用另一个Hash函数来给每一个字符串一个函数来给每一个字符串一个ID，相同的字符串，相同的字符串ID确定相同，不同的字符串也有确定概率确定相同，不同的字符串也有确定概率ID相同，相同，在查找时，仅需考虑在查找时，仅需考虑ID相同的串来确定是否串相同的串来确定是否串X存在，存在，避开了大范围的查找，和大量长字符串匹配。避开了大范围的查找，和大量长字符串匹配

3、。4第2题现在有一个文本编辑器，具有如下的操作：现在有一个文本编辑器，具有如下的操作：MOVEk：将光标移动到第：将光标移动到第k个字符之前，假个字符之前，假如如k=0，那么移动到文档开头，那么移动到文档开头PRINTn：输出光标之后的：输出光标之后的n个字符个字符PREV：光标前移一位：光标前移一位NEXT：光标后移一位：光标后移一位5（1）请基于线性数据结构设计一套合理的算法，来实）请基于线性数据结构设计一套合理的算法，来实现这些操作，并且分析每个操作的性能。假定：文本现这些操作，并且分析每个操作的性能。假定：文本最大的长度为最大的长度为Lh2：15那么，为了满足红黑树性质，我们令那么，为

4、了满足红黑树性质，我们令T2的根结点为的根结点为多多(h1-h2+1)黑结点。我们可以利用红黑树的删除算黑结点。我们可以利用红黑树的删除算法中对双黑结点处理的方法同样处理法中对双黑结点处理的方法同样处理T2的根结点，的根结点，即令其从即令其从(h1-h2+1)黑结点，变为黑结点，变为(h1-h2)黑结点黑结点直直至为单黑结点，那么就变成了一棵正常的红黑树。至为单黑结点，那么就变成了一棵正常的红黑树。16双黑结点的调整双黑结点的调整假设假设X是左子结点（若是左子结点（若X为右子结点，处理方法类似，不重述）为右子结点，处理方法类似，不重述）状况状况1：双黑结点的兄弟：双黑结点的兄弟C是红色，执行旋

5、转操作（黑红）！是红色，执行旋转操作（黑红）！推出：推出：B结点也确定是黑色，结点也确定是黑色，和和也是黑色也是黑色旋转：兄弟节点为根变黑，父节点变红旋转：兄弟节点为根变黑，父节点变红X结点仍是结点仍是“双黑双黑”结点，转化为状况结点，转化为状况2,317北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法BCXXBC双黑结点状况状况2：兄弟是黑色：兄弟是黑色,且有两个黑子结点（黑且有两个黑子结点（黑黑黑）黑黑）执行换色操作，把执行换色操作，把C着红色，着红色，B着黑色着黑色假如假如B原为红色，

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

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

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

9、，调调整完成整完成保持保持树树的的稳稳定性！定性！X以祖结点为轴旋以祖结点为轴旋转父结点转父结点AXBB BA AC CC C22北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法4种形式的结构调整种形式的结构调整原原则则：保持：保持BST的中序性的中序性质质2 2466 624264 423提升操作旋转操作北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法双红调整双红调整2：红红换色红红换色

10、状况状况2：新增：新增结结点点X的叔父的叔父结结点也是点也是红红色色X父祖换色父祖换色叔父变黑叔父变黑AXBB BA AC CC24对B接着红红检查北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院北京高校信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法假如B是根节点，则只叔父节点变色，根节点不变！25第第10章章检索检索第第11章章索引索引第第12章章高级数据结构高级数据结构26供应广义表的下列操作供应广义表的下列操作make_GList(a,b,c.);将随意多个广义表连接成一个将随意多个广义表连接成一个新的广义表新的广义表head(gList

11、);取广义表头取广义表头tail(gList);取广义表尾；取广义表尾；要求设计一个算法，将广义表置逆，不能运用其他数要求设计一个算法，将广义表置逆，不能运用其他数据结构。比如，对于广义表据结构。比如，对于广义表(a,(a,b,c),(b,(d),置逆之后的结果为：置逆之后的结果为：(d),b),(c,b,a),a);27解：干脆用递归即可。解：干脆用递归即可。GListreverse(gList)Returnmake_Glist(reverse(tail(gList),reverse(head(gList)282.假定经过分词后的网页已经形成了倒排索引，运用假定经过分词后的网页已经形成了倒排

12、索引，运用trie树作为词典，叶子结点会有指向倒排表的指针，树作为词典，叶子结点会有指向倒排表的指针，倒排表是依据网页文档倒排表是依据网页文档id（连续的整数值）排好序的。（连续的整数值）排好序的。现在须要系统支持简洁的布尔查询。请写出以下算现在须要系统支持简洁的布尔查询。请写出以下算法的代码或伪代码，并分析困难度法的代码或伪代码，并分析困难度29I.Keyword1andkeyword2II.Keyword2andnotkeyword2III.假如须要支持相邻查询，例如假如须要支持相邻查询，例如keywordandkeword2neardistance，distance代表词与词代表词与词之

13、间的距离，须要怎样更改倒排索引表，支之间的距离，须要怎样更改倒排索引表，支持这一需求？持这一需求？30答案答案1、用、用trie树可以在树可以在O(length(string)的时间内找到单的时间内找到单词所对应的倒排表的位置。词所对应的倒排表的位置。依据这一点，设计如下代码。依据这一点，设计如下代码。设设A1.AN为第一个单词的文档，为第一个单词的文档，B1.BM为其次个为其次个单词的文档单词的文档313233343.AVL树和红黑树的高度树和红黑树的高度A.高度为高度为h的的AVL树上的最少结点个数是多少？最多树上的最少结点个数是多少？最多结点个数是多少？结点个数是多少？B.高度为高度为h

14、的红黑树上的最少结点个数是多少？最多的红黑树上的最少结点个数是多少？最多结点个数是多少？结点个数是多少？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树树是一种用于多是一种用于多维检维检索的索的树结树结构，它的每构，它的每一一层层都依据特定关都依

15、据特定关键码键码将将对对象空象空间间分解分解为为两个两个顶层结顶层结点按一个点按一个维维划分划分其次其次层结层结点依据另一点依据另一维进维进行划分行划分以此以此类类推在各个推在各个维维之之间间反复反复进进行划分行划分最最终终当一个当一个结结点中的点数少于点中的点数少于给给点的最大点数点的最大点数时时，划分，划分结结束束识别器(discriminator)在每一层用来进行决策的关键码称为识别器在每一层用来进行决策的关键码称为识别器对于对于k k维关键码，在第维关键码，在第i i层把识别器定义为层把识别器定义为i i mod kmod k例如，对一个三维的关键码做检索，例如，对一个三维的关键码做检

16、索，3 3个关键个关键码（码（x x，y y，z z）标号分别为）标号分别为0 0、1 1、2 2第一层是第一层是0 mod 3=00 mod 3=0，所以运用关键码，所以运用关键码x x，其次层是其次层是1 mod 3=11 mod 3=1，所以运用关键码，所以运用关键码yy结点的安排结点的安排在结点安排的时候首先比较该层的识别器在结点安排的时候首先比较该层的识别器假如关键码小于识别器的值就放到左子树中假如关键码小于识别器的值就放到左子树中否则放到右子树否则放到右子树然后在下一层运用新的识别器来推断每个结点然后在下一层运用新的识别器来推断每个结点的归属的归属识别器的值应当尽量使得被划分的结点

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

18、把空间分解为矩形树中的这些结点最终把空间分解为矩形这些矩形是结点可能落到的各子树范围这些矩形是结点可能落到的各子树范围K-D树的不足 其结构与输入数据的依次也是有关的其结构与输入数据的依次也是有关的有可能导致它每个子树的元素安排不均衡有可能导致它每个子树的元素安排不均衡BentleyBentley和和FriedmanFriedman独创了独创了adaptive k-dadaptive k-d树，树，类似于类似于BSTBST全部的数据记录都存储在叶结点全部的数据记录都存储在叶结点内部结点只是用来在各个维之间导航内部结点只是用来在各个维之间导航每一个识别器的选择不再依靠于输入的数据每一个识别器的选

19、择不再依靠于输入的数据尽量选择让左右子树的记录数目相等的值尽量选择让左右子树的记录数目相等的值 2、PR四分树四分树 PR四分树，即点四分树，即点-区域四分树（区域四分树（Point-RegionQuadtree）：每个内部结点都恰好有四个子结点每个内部结点都恰好有四个子结点每个内部结点将当前空间均等地划分为四个区域每个内部结点将当前空间均等地划分为四个区域NWNW（西北）、（西北）、NENE（东北）、（东北）、SWSW（西南）和（西南）和SESE（东南）（东南）PR四分树也是对对象空间的划分四分树也是对对象空间的划分完全四叉树完全四叉树PR四分树对空间的划分四分树对空间的划分每个内部结点将当

20、前空间均等地划分为四个区每个内部结点将当前空间均等地划分为四个区假如子区域包含的数据点数大于假如子区域包含的数据点数大于1 1，那么就把，那么就把该区域接着均等地划分为四个区域该区域接着均等地划分为四个区域依次类推，直到每个区域所包含的数据点不超依次类推，直到每个区域所包含的数据点不超过一个为止过一个为止 PR树的图示PR树的划分树的划分上图所表示的上图所表示的PRPR四分树，其对象空间为四分树，其对象空间为128128 128 128，并包含点，并包含点A A、B B、C C、D D、E E、F F和和G G 根结点的四个子结点把整个空间平分为四份大根结点的四个子结点把整个空间平分为四份大小

21、为小为6464 6464的子空间的子空间NWNW，NENE，SWSW，SE SE NWNW（包含三个数据点）和（包含三个数据点）和SE(SE(包含两个数据点包含两个数据点)须要进一步分裂须要进一步分裂 PR树的插入假如这个位置的叶结点没有包含其他的数据点假如这个位置的叶结点没有包含其他的数据点那么我们就把记录插入这里；那么我们就把记录插入这里；假如这个叶结点中已经包含假如这个叶结点中已经包含P P了了(或者一个具有或者一个具有P P的坐的坐标的记录标的记录)那么就报告记录重复；那么就报告记录重复；假如叶结点已经包含另一条记录假如叶结点已经包含另一条记录X X那么就必需接着分解这个结点，直到已存

22、在的记录那么就必需接着分解这个结点，直到已存在的记录X X和和P P分别进入不同的结点为止分别进入不同的结点为止 PR树的删除产生的合并删除结点删除结点D导致的区域合并导致的区域合并PR树的不足无法做到有效率的插入删除，很有可能出现最坏状况；无法做到有效率的插入删除，很有可能出现最坏状况；空间动态安排，但是增加空间动态安排，但是增加/削减的量并不稳定；削减的量并不稳定；处理分布比较匀整的状况时，效果并不差。处理分布比较匀整的状况时，效果并不差。53考试大纲考试大纲54关于考试时间和地点时间和地点时间：时间：2015年年1月月7日日上午上午8:30-10:30地点：一教地点：一教201考试题型考

23、试题型填空、选择、辨析与简答、数据结构或算法的填空、选择、辨析与简答、数据结构或算法的设计和分析、数学证明设计和分析、数学证明（1）数据结构）数据结构/算法设计与分析题只要写明基算法设计与分析题只要写明基本思想、无歧义即可，必要时加上足够的注释。本思想、无歧义即可，必要时加上足够的注释。（2）对于算法中干脆运用的类和函数（例如）对于算法中干脆运用的类和函数（例如栈、队列的函数），应当先写栈、队列的函数），应当先写ADT，并简洁，并简洁说明算法中用到的重要函数的功能、入口参数、说明算法中用到的重要函数的功能、入口参数、出口参数。出口参数。范围：范围：1-12章章55考场支配和留意事项考场支配和留

24、意事项请随身带好您的学生证，笔和涂改工具参与考试。请随身带好您的学生证，笔和涂改工具参与考试。考试形式为闭卷，可以运用计算器考试形式为闭卷，可以运用计算器考前考前10分钟，请大家把书包等放在教室前面的讲台和窗台上，分钟，请大家把书包等放在教室前面的讲台和窗台上，留意在试卷纸和有效答题纸上写上姓名和学号。留意在试卷纸和有效答题纸上写上姓名和学号。统一发草稿纸，不够可以随时举手要。统一发草稿纸，不够可以随时举手要。请大家留意考场纪律，不要窃窃私语，私下探讨。考试时对请大家留意考场纪律，不要窃窃私语，私下探讨。考试时对试题有疑问，可以举手，待监考老师来到旁边时，再请向监试题有疑问，可以举手，待监考老

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

26、计数据结构3.算法的渐进分析方法算法的渐进分析方法4.大大O表示法（不要求驾驭大表示法（不要求驾驭大、大、大表示法）表示法）57第第2章章 线性表线性表一一.概念概念1.线性表线性表2.单链表单链表3.双链表双链表4.循环表循环表二二.方法方法1.依次表上实现的运算依次表上实现的运算2.链表上实现的运算链表上实现的运算(指针操作的正确性指针操作的正确性)3.依次表和链表的比较依次表和链表的比较58第第3章章 栈与队列栈与队列一一.概念概念1.栈栈2.队列队列3.循环队列循环队列二二.方法方法1.栈的性质，用栈来生成序列栈的性质，用栈来生成序列2.队列的性质，用队列队列的性质，用队列生成生成序列

27、序列3.栈的依次实现栈的依次实现4.循环队列的实现循环队列的实现5.表达式求值表达式求值(中缀表达式转后缀表达式的算法、中缀表达式转后缀表达式的算法、后缀表达式求值算法后缀表达式求值算法)6.栈在递归调用及转换中的应用栈在递归调用及转换中的应用59第第4章章 字符串字符串一一.概念概念1.串串2.模式匹配模式匹配二二.方法方法1.串的基本操作串的基本操作2.串的存储及运算串的存储及运算3.串的串的KMP快速模式匹配算法，求特征向量数快速模式匹配算法，求特征向量数组（组（N数组）和利用数组）和利用N向量完成匹配的方法向量完成匹配的方法60第第5章章 二叉树二叉树一一.概念概念1.二叉树二叉树2.

28、二叉树的深度优先周游二叉树的深度优先周游3.二叉排序树二叉排序树4.堆堆5.Huffman树、树、Huffman编码编码各种结构的节点个数与高度、层次、度等关系换算各种结构的节点个数与高度、层次、度等关系换算二二.方法方法1二叉树的链式存储二叉树的链式存储（1）二叉链表）二叉链表（2）带父指针的三重链表）带父指针的三重链表612.二叉树的依次存储二叉树的依次存储完全二叉树的依次存储完全二叉树的依次存储3.二叉树的深度优先周游二叉树的深度优先周游4.BST树的插入与删除树的插入与删除5.构造构造Huffman树和树和Huffman编码编码6.堆的建立与维护过程堆的建立与维护过程62636465第

29、第6章章 树树一一.概念概念树、森林树、森林、先根、后根、层次周游先根、后根、层次周游K叉树叉树二二.方法方法1.森林与二叉树相互转换森林与二叉树相互转换2森林的链式存储森林的链式存储(1)转换为相应的二叉树，用二叉链表表示转换为相应的二叉树，用二叉链表表示(2)父指针表示法、(3)子结点表表示法(4)等价类和并查算法的应用663.森林的深度优先周游（递归），可能结合应用森林的深度优先周游（递归），可能结合应用4.森林的依次存储及其构造森林的依次存储及其构造5.二叉树和森林的层次周游二叉树和森林的层次周游(用队列用队列)，可能结合应用，可能结合应用67第第7章章 图图一一.概念概念1.图的相关

30、概念：连通性、连通重量、边与顶点关系图的相关概念：连通性、连通重量、边与顶点关系等等2.深度周游、宽度周游深度周游、宽度周游3.图的生成树、生成树林、最小生成树图的生成树、生成树林、最小生成树二二.方法及算法方法及算法1.图的存储方法图的存储方法:（1）相邻矩阵相邻矩阵（2）邻接表邻接表2.图的周游图的周游:1）深度优先深度优先（2）宽度优先宽度优先683.图的生成树与最小生成树图的生成树与最小生成树从某一点动身，按深度优先或宽度优先周游的生成树从某一点动身，按深度优先或宽度优先周游的生成树最小生成树最小生成树Prim算法算法Kruskal算法算法(避圈法避圈法)4.拓扑排序拓扑排序:给定图，

31、找出若干个或全部拓扑序列给定图，找出若干个或全部拓扑序列5.最短路径最短路径:Dijkstra算法、算法、Floyd算法算法6.Dijkstra算法、算法、Prim算法、算法、Kruskal算法都是典型算法都是典型的贪心法（退化的动态规划法）的贪心法（退化的动态规划法）69第第8章章 内排序内排序1.重点排序算法：干脆插入法、重点排序算法：干脆插入法、Shell排序、排序、快快速排序、速排序、基数排序、归并排序基数排序、归并排序2.算法分析算法分析基于比较次数和移位次数分析最好、最坏的时间、空基于比较次数和移位次数分析最好、最坏的时间、空间间干脆插入法、二分法插入排序、起泡排序、干脆选择、干脆

32、插入法、二分法插入排序、起泡排序、干脆选择、快速排序、基数排序、归并排序快速排序、基数排序、归并排序记住各种排序方法的平均时间记住各种排序方法的平均时间3.各种排序方法的局部修改和混合应用各种排序方法的局部修改和混合应用70第9章 文件管理和外排序方法及算法方法及算法1.置换选择排序置换选择排序2.多路归并多路归并(败者树，最佳归并树，多路归并的读败者树，最佳归并树，多路归并的读盘和写盘次数盘和写盘次数)71第10章 检索一一.概念概念1.平均检索长度平均检索长度2.二分法检索二分法检索3.散列表、同义词、散列表、同义词、碰撞、积累碰撞、积累二二.方法方法1.二分法检索的判定树、查找某个结点的

33、比较次数二分法检索的判定树、查找某个结点的比较次数2.散列表散列表:1)散列函数选择散列函数选择(除余法、平方取中法、除余法、平方取中法、折叠法折叠法)2)冲突处理方法冲突处理方法(分别同义词子表、线性探测、双散分别同义词子表、线性探测、双散列函数列函数)三三.散列算法（查找、插入、删除，对墓碑的处理散列算法（查找、插入、删除，对墓碑的处理72第11章 索引技术一一.概念概念1.依次文件依次文件2.散列文件散列文件3.倒排文件倒排文件4.静态索引结构静态索引结构5.动态索引结构动态索引结构(B树树)6.红黑树红黑树二二.方法（不考算法）方法（不考算法）1.B树、树、B+树的插入与删除树的插入与

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

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

36、寻树，理解平均检索长度最优的特点最佳二叉搜寻树，理解平均检索长度最优的特点5.AVL平衡二叉树的插入方法：平衡二叉树的插入方法：LL、LR、RL、RR的四种旋转调整。不考删除算法，但可考性质的四种旋转调整。不考删除算法，但可考性质6.伸展树及其简洁应用：伸展树及其简洁应用：伸展树在搜寻过程中旋转调整结构，使访问最常见的伸展树在搜寻过程中旋转调整结构，使访问最常见的结点靠近树结构的根。伸展树的旋转分为：单旋转、结点靠近树结构的根。伸展树的旋转分为：单旋转、一字形旋转和之字形旋转。留意伸展树的变种，例一字形旋转和之字形旋转。留意伸展树的变种，例如半伸展树。如半伸展树。splay树的插入、删除以及区间操作都树的插入、删除以及区间操作都要求驾驭要求驾驭7677再见再见联系信息：联系信息：电子邮件：电子邮件：gjsongpku.edu电电话：话：62754785办公地点：理科办公地点：理科2号楼号楼2307室室