2020新疆事业单：计算机之数据结构与算法（9）

　　5、B+树

　　(图e)

　　B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：

　　(1)有n棵子树的节点含有n个关键字;

　　(2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;

　　(3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;

　　(4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

　　6、字典树(trie树)

　　(图f)

　　字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：

　　(1)根节点为空;

　　(2)除根节点外，每个节点包含一个字符;

　　(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

　　(4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。

　　7、后缀树

　　后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。

　　8、广义后缀树

　　广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。

　　6.图 (Graph)

　　图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

　　1.图的存储结构

　　——推荐阅读——

招考公告——2022新疆事业单位报考公告

　　试题资料——2022新疆事业单位相关考题

　　考试技巧——事业单位备考技巧

　　职位查询——新疆事业单位职位库

　　笔试课程——事业单位好课程 备战事考有方法

　以上为本文的全部内容，由新疆公务员考试网提供，希望对考生有所帮助！更多新疆公务员招考信息，请加新疆公务员考试交流群，及关注新疆公务员考试招考资讯/新疆人事考试网。