上午综合部分有内容考，下午也有，而且是最难的题

目录

标色为重点

1. 数组与矩阵
2. 线性表
3. 广义表
4. 树和二叉树
5. 图
6. 排序和查找
7. 算法基础和常见算法

数组与矩阵

数组

例题

链表的基本操作

队列与栈

• 层次遍历
  12345678
• 前序：根左右
  12457836
• 中序：左根右
  42785136
• 后序：左右根
  48752631

反向构造二叉树

树转换成二叉树

最优二叉树（哈夫曼树）

• 路径乘以权值，只要求叶子，就是带权路径长度
  比如左一的就是：22+43+83+11=41

平衡二叉树

邻接表

图的最小生成树

1.普利姆算法

算法基础

算法特性

• 有穷性：执行有穷步之后结束
• 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清，都有确定的唯一的结果
• 输入（〉=0）
• 输出（〉=1）
• 有效性：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0，b/a就无效

算法的复杂度

• 时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T（n）。由于许多情况下要精确计算T（n）是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：
  如果存在两个常数c和m，对于所有的n，当n≥m时有f（n）≤cg（n），则有f（n）=O（g（n））。也就是说，随着n的增大，f（n）渐进地不大于g（n）。例如，一个程序的实际执行时间为T（n）=3n³+2n²+n，则T（n）=O（n³）。

常见的对算法执行所需时间的度量：

O（1）<O（log₂n）<O（n）<O（nlog₂n）<O（n²）<O（n³）<O（2ⁿ）

• 空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小.

查找

1.顺序查找

2.希尔排序（shell）

4.堆排序

5.冒泡排序

7.归并排序

排序的时间空间复杂度

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33828 人正在系统学习中