type
status
date
slug
summary
tags
category
icon
password
知识点 | 分数 | 细分内容 |
概论 | 6 | 算法概念：2，数据结构概念：2，时间复杂度：2 |
线性表 | 20 | 线性表概念：2，顺序表概念：2，操作算法：6，链表概念：2，链表插入删除（填空）：2，操作算法：6 |
栈和队列 | 16 | 算法设计（栈或队列）：6，队列概念：6，栈概念：4 |
数组与广义表 | 4 | 数组：2，广义表：2 |
树 | 20 | 递归编程：6，遍历（已知两种求第三种）：填空：4，哈夫曼树（求哈夫曼编码）：6，森林概念：2,
基本概念：2 |
图 | 14 | 最小生成树（两种算法）：6，遍历（DFS，BFS）：4，存储（邻接表，邻接矩阵）：2，基本概念：2 |
查找 | 12 | 基本概念：6，编程题：6 |
排序 | 10 | 排序算法（理解并掌握）：直接插入、折半插入、希尔排序、冒泡、快速排序、选择排序、堆排序、归并排序，排序结果分析：6，排序概念与特点：4 |
题型 | 分数 | 题目内容 |
程序填空题 | - | 顺序表：1道，链表：1道，查找：1道，树：1道 |
应用题 | - | 二叉树构造，哈夫曼树，图的遍历，哈希，最小生成树 |
选择题 | 约30分 | ㅤ |
其他题型 | - | 填空题（少量） |
树
树的遍历
‣
‣
哈夫曼树
Note:
哈夫曼树求编码过程 → 
- 求出每个字母出现次数
- 每次合并两个最小次数的两个节点并合成一个新节点参与后续合成，最终生成一颗哈夫曼树,树中到每个字母节点路径即为该哈夫曼编码
⚠️注意:不同的编码方式导致哈夫曼编码不唯一,如B/D更换放置顺序→ 则B为011,D为010 但是最终的总长度一定相同
哈夫曼编码是一种压缩算法 → 所以其得到的编码是最短的,原理是贪心 , 对于等长编码来说,导致长度更长的因素是出现次数最多的字母,哈夫曼编码可以使得出现次数最多的编码长度更短,并且不会出现重复前缀→顶点到树上每个结点的路线是唯一的且每次只有两个选择(0/1).
带权路径长度（Weighted Path Length，WPL）
→ 哈夫曼编码长度(压缩后文件总大小
哈希表
平均查找长度
例题
最小生成树
- Author:Hedgeho9
- URL:https://Hedgeho9.cn/article/157fa7e3-8bb8-80ae-b544-db4834a72031
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
