初级程序员软考重点6 数据结构与算法

初级程序员软考重点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个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动$$\frac{n?1}{2}$$个元素。

4. 链表

三、栈和队列

• 父结点
• 子结点
• 兄弟结点
• 叶子结点：没有子结点
• 结点的度：结点有几个子结点
• 树的度：所有结点度最大的值
• 二叉树：树的度不超过2
• 层（深度、高度）

2. 二叉树

（1）一些概念

满二叉树

每一层都不能增加结点

完全二叉树

除了最后一层，都不能增加结点。 最后一层左侧连续有，右侧连续无。

非完全二叉树

除了最后一层，都不能增加结点。但不满足最后一层左侧连续有、右侧连续无的条件 。

（2）二叉树的特性

• 每一层上最多有$2^{n?1}$个节点
• 深度为k的二叉树最多有$2_k?1$个节点
• 如果对一棵有n个结点的完全二叉树的结点按层序编号，有：

如果i=1，则结点i无父结点，二叉树的根；如果i>1，则父结点是 i/2取整。
如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i。
如果2i+1>n，则结点i无右子结点，否则，其右子结点是结点2i+1。

有向图转邻接矩阵

六、算法特性与复杂度

1. 算法的特性

• 有穷性
• 确定性

2. 算法评价指标

• 正确性
• 友好性
• 可读性
• 健壮性
• 效率

3. 时间复杂度

常见的算法时间复杂度：
$$O(1)(lo{g}_{2}n)O(n)O(nlo{g}_{2}n)O(n^2)O(n^3)O(2^n)$$

• 二分查找： $lo{g}_{2}n$
• 一次循环： O(n)
• 插入、冒泡、选择排序：$O(来源：编程圈子声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！$