开放教育数据结构历年真题 09年自考《数据结构》各章要点二[3]

09年自考《数据结构》各章要点二[3]  

　　树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致

　　树的带权路径长度是树中所有叶结点的带权路径长度之和 树的带权路径长度最小的二叉树就称为最优二叉树(即哈夫曼树)

　　在叶子的权值相同的二叉树中 完全二叉树的路径长度最短

　　哈夫曼树有n个叶结点 共有 n 个结点 没有度为 的结点 这类树又称为严格二叉树

　　变长编码技术可以使频度高的字符编码短 而频度低的字符编码长 但是变长编码可能使解码产生二义性 如 这三个码无法在解码时确定是哪一个 所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀 这种码称为前缀码(其实是非前缀码)

　　哈夫曼树的应用最广泛地是在编码技术上 它能够容易地求出给定字符集及其概率分布的最优前缀码 哈夫曼编码的构造很容易 只要画好了哈夫曼树 按分支情况在左路径上写代码 右路径上写代码 然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码

　　第七章 图

　　图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的 即任意两个结点之间之间都可能相关

　　图GraphG=(V E) V是顶点的有穷非空集合 E是顶点偶对的有穷集

　　有向图Digraph 每条边有方向

　　无向图Undigraph 每条边没有方向

　　有向完全图 具有n*(n )条边的有向图

　　无向完全图 具有n*(n )/ 条边的无向图

　　有根图 有一个顶点有路径到达其它顶点的有向图

　　简单路径 是经过顶点不同的路径

　　简单回路 是开始和终端重合的简单路径

　　网络 是带权的图