计算机二级公共基础知识（一）——数据结构与算法
文章目录
数据结构与算法
【1】算法的概念
- 算法：指一组有穷的指令集，是解题方案的准确而完整的描述
- 算法的特征：
- 确定性：每一个步骤都有明确的意义
- 有穷性：算法必须能在有限的时间内做完
- 可行性：精确性
- 拥有足够的情报
- 算法的组成要素：算法 = 数据对象运算和操作 + 控制结构
- 算法的基本运算和操作：算术运算、逻辑运算、关系运算、数据传输
- 算法的基本控制结构：顺序、选择、循环
- 算法的基本设计方法：引举法、归纳、递推、递归、减半递推技术
【2】算法的复杂度
- 算法效率的质量——算法的复杂度：时间复杂度和空间复杂度
- 时间复杂度：执行算法所需的计算工作量（通常一个算法所用的时间包括编译时间和运行时间）
- 空间复杂度：执行算法所需要内存空间
时间复杂度和空间复杂度并不相关
【3】数据结构
- 数据：客观事物的符号表示
- 数据元素：数据元素是数据的基本单位
- 数据对象：性质相同的数据元素的集合
- 数据结构：某一数据对象中，所有数据或成员之间的关系组合的集合
【4】逻辑结构和存储结构
- 数据的逻辑结构：数据元素之间的关系描述。与数据的存储无关、面向问题、独立于计算机
- 数据的存储结构：也叫物理结构，计算机中的存储方式，面向计算机
- 逻辑结构可对应多个存储结构
- 常见的存储结构：顺序、链接、索引（不同的存储结构，处理的效率不同）
【5】线性结构和非线性结构
- 线性结构：有且只有一个根节点；每一个节点最多一个前件和一个后件
- 非线性结构
- 线性结构：栈、队列、双向链表
- 非线性结构：树、二叉树
【6】线性表及其顺序存储结构
- 线性表是由一组数据元素构成、数据元素只取决于自己序号
- 复杂线性表：
- 记录：若干数据元素组成的数据元素
- 文件：若干记录构成的线性表
- 非线性表的结构特征：
- 有且只有一个根节点
- 有且只有一个终节点
- 其他节点，只有一个前件和一个后件
- 线性表的顺序存储结构特特点：
- 所有元素占用空间连续
- 各元素的存储空间中是按逻辑顺序依次存放
- 顺序表的运算：查找、删除、插入
【7】线性链表
- 链表是线性表的链式存储结构
- 每一个节点：
- 数据域：存储数据元素
- 指针域：存放指针
- 链式存储结构的存储空间可以不连续
- 链式存储结构可以用于线性结构也可以用于非线性结构
【8】栈
- 栈：一种特殊的线性表，只允许在表的一端插入和删除元素（栈顶）
- 栈是一种后进先出线性表
- 栈具有记忆功能
- 栈的基础运算：
（1）入栈：栈顶插入元素
（2）退栈：栈顶删除元素
（3）读栈顶元素：将栈顶元素赋给一个指定的变量，此时指针无变化
【9】队列
- 队列：特殊的线性表
（1）队尾rear：插入元素
（2）队头front：删除元素（front指向队头元素的前一个位置）
（3）先进先出
- 队列的存储结构：
顺序存储：一维数组
链式存储：线性链表
- 队列的顺序存储结构：一般采用循环队列
s=0：空队列
s=1且front=rear：队满
- 循环队列的元素个数：rear - front（若为负，则加上容量）
【10】树
- 树：非线性结构，n个节点的集合
- 叶子节点：度为0，最后一层
- 根节点在第一层
【11】二叉树的性质
- 二叉树的第K层上：==2^(k-1)==个节点
- 深度为m的二叉树最多有2^m - 1个节点
- 叶子节点数 = 度为2的节点数 + 1
- n个节点的二叉树：深度 >=[logn] + 1（[logn]代表整数部分）
【12】满二叉树和完全二叉树
- 满二叉树：满的
- 完全二叉树：只有最后一层上缺少右边的节点
- 满二叉树是完全二叉树，完全二叉树不是满二叉树
【13】完全二叉树的性质
- n个节点的完全二叉树的深度为：等于[logn] + 1
- 完全二叉树中度为1的节点数目：0或1
【14】二叉树的遍历
【15】顺序查找
以下的两种情况只能采用顺序查找
（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找
（2）链式存储结构，只能用顺序查找
【16】二分查找
- 二分查找的条件：顺序存储结构+有序表
- 长度为n有序线性表：最坏情况下二分查找需要logn次（最高效）
【17】排序
- 交换排序
| 冒泡排序 | 最坏情况：n(n-1)/2 |
| 快速排序 | 最坏情况：==n(n-1)/2= |
- 插入排序
| 简单插入排序 | 最坏情况：n(n-1)/2 |
| 希尔排序 | 最坏情况：O(n^1.5) |
- 选择排序
| 简单选择排序 | 最坏情况：n(n-1)/2 |
| 堆排序 | 最坏情况：O(nlogn) |
除了希尔排序外，堆排序时间复杂度最小