初级程序员软考重点6：数据结构与算法
- 一、数据结构和算法
-
- 1. 逻辑结构
-
- （1）线性结构
- （2）非线性结构
- 2. 存储结构
- 3. 顺序表
- 4. 链表
- 二、数组和字符串
- 三、矩阵
-
- 1. 特殊矩阵
- 2. 非特殊矩阵
- 3. 矩阵乘法
- 三、栈和队列
-
- 1. 队列（先进先出，FIFO——first in first out)
- 2. 栈（先进后出，FILO——first in last out）
- 四、树
-
- 1. 树的基本概念
- 2. 二叉树
-
- （1）一些概念
-
- 满二叉树
- 完全二叉树
- 非完全二叉树
- （2）二叉树的特性
- 3. 树的遍历
- 4. 特殊二叉树
-
- （1） 二叉排序树
- （2） 哈夫曼树
- 五、图
-
- 1. 图的分类
-
- （1）有向图
- （2）无向图
- （3）连通图
- （4）完全图
- 2. 图的转换：无向图转邻接矩阵
-
- 无向图转换的邻接矩阵为对称矩阵。
- 有向图转邻接矩阵
- 3. 度
-
- （1）入度
- （2）出度
- 4. 有向图转邻接链表
- 六、算法特性与复杂度
-
- 1. 算法的特性
- 2. 算法评价指标
- 3. 时间复杂度
- 4. 空间复杂度
- 七、查找
-
- 1. 顺序查找
- 2. 二分查找（折半查找）
-
- （1）二分法查找循环算法
- （2）二分法排序递归算法
- 3. 散列表查找：
-
- （1）线性探查法
- （2）拉链法
- 八、排序
-
- 1. 基本概念
- 2. 插入类排序
-
- （1） 直接插入排序
- （2）希尔排序
- 3. 交换类排序
-
- （1）冒泡排序
- （2）快速排序
- 4. 选择类排序
-
- （1）直接选择排序
- （2） 堆排序
- 5. 归并排序
- 6. 基数排序
- 7. 总结
一、数据结构和算法
数据结构：元素之间的关系，分为逻辑结构和存储结构。
1. 逻辑结构
（1）线性结构
每个元素前、后最多都只能有一个节点，如：线性表、栈、队列、数组、串
（2）非线性结构
如：二维数组、多维数组、树、图等
2. 存储结构
- 顺序存储
- 链接存储
3. 顺序表
含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动 n ? 1 2frac{n-1}{2} 2n?1?个元素。
4. 链表
三、栈和队列
- 父结点
- 子结点
- 兄弟结点
- 叶子结点：没有子结点
- 结点的度：结点有几个子结点
- 树的度：所有结点度最大的值
- 二叉树：树的度不超过2
- 层（深度、高度）
2. 二叉树
（1）一些概念
满二叉树
每一层都不能增加结点
完全二叉树
除了最后一层，都不能增加结点。 最后一层左侧连续有，右侧连续无。
非完全二叉树
除了最后一层，都不能增加结点。但不满足最后一层左侧连续有、右侧连续无的条件 。
（2）二叉树的特性
- 每一层上最多有 2 n ? 1 2^{n-1} 2n?1个节点
- 深度为k的二叉树最多有 2 k ? 1 2_k-1 2k??1个节点
- 如果对一棵有n个结点的完全二叉树的结点按层序编 ，有：
如果i=1，则结点i无父结点，二叉树的根；如果i>1，则父结点是 i/2取整。
如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i。
如果2i+1>n，则结点i无右子结点，否则，其右子结点是结点2i+1。
有向图转邻接矩阵
六、算法特性与复杂度
1. 算法的特性
- 有穷性
- 确定性
2. 算法评价指标
- 正确性
- 友好性
- 可读性
- 健壮性
- 效率
3. 时间复杂度
常见的算法时间复杂度：
O ( 1 ) O(1)(log2?n)O(n)O(nlog2?n)O(n2)O(n3)O(2n)
- 二分查找： l o g 2 n log_2n log2?n
- 一次循环： O(n)
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！