二级基础知识 第一章 数据结构与算法 全国计算机等级考试. 1.1 算法  一、算法的概念 解决问题准确而完整的描述。  特征：可行性、确定性、有穷性、拥有足够的 情报。  要素：对数据运算操作（算术、逻辑）通过指 令序列程序来实现、算法的控制结构（执行顺 序）。  算法设计方法： 列举法：列举所有可能.

Presentation on theme: "二级基础知识 第一章 数据结构与算法 全国计算机等级考试. 1.1 算法  一、算法的概念 解决问题准确而完整的描述。  特征：可行性、确定性、有穷性、拥有足够的 情报。  要素：对数据运算操作（算术、逻辑）通过指 令序列程序来实现、算法的控制结构（执行顺 序）。  算法设计方法： 列举法：列举所有可能."— Presentation transcript:

1 二级基础知识 第一章 数据结构与算法 全国计算机等级考试

2 1.1 算法  一、算法的概念 解决问题准确而完整的描述。  特征：可行性、确定性、有穷性、拥有足够的 情报。  要素：对数据运算操作（算术、逻辑）通过指 令序列程序来实现、算法的控制结构（执行顺 序）。  算法设计方法： 列举法：列举所有可能 归纳法：从特殊到一般

3 递推：从条件到结论 递归：函数的自调用 减半递推：中间分冶 回溯 : 反证  二、算法复杂度 1 、时间复杂度（工作量） 平均性态（平均值）；最坏情况（最大值） 2 、空间复杂度（资源） 内存资源

4 1.2 数据结构的基本概念  研究数据结构 —— 逻辑结构、物理结构、运算 的实现  1 、数据结构 数据逻辑结构：数据元素及元素间的关系， B=(D,R) 存储结构：内存中的存放形式 线性与非线性结构：有且仅有一个根结点；一个 前件，一个后件 只有一个根结点不是线性结构

5 1.3 线性表及其顺序存储结构  线性表：连续顺序存储，逻辑结构与存储结 构一致。  插入运算：插入点起所有元素后移  删除运算：删除点后所有元素前移

6 1.4 栈和队列  1 、栈 只有一个出入口仅有一个元素宽度的巷道， 先进后出 入栈、退栈、读栈顶元素  2 、队列 一个出口一个入口仅有一个元素宽度的巷道， 先进先出 队列移动，循环标志 s 0 空 入队；上溢、退队；下溢

7 1.5 线性链表  线性表的缺点：插入删除上的复杂性、空间 的连续性（预留、不够） 结点：元素 + 指针 Head---a1 *a2---a2 *a3…an null  双链表  栈与队列的链表实现  链表的插入删除 改变前后元素的指针指向，可以不改变位置  循环链表：增加一个表头结点数据不定, 最后 一指针指向表头

8 1.6 树与二叉树  1 、树 层次结构 根结点、叶子结点、子结点、深度（层数）、 节点的度（分叉数） 了解表达式的树表示  2 、二叉树 分叉数少于等于 2 （左右子树）, 一个根节点是 二叉树  性质 A 、 k 层节点少于 2^(k-1) B 、 m 深度的树节点总数为 2^m-1

9 C 、度为 2 的比度为 0 节点多一个 d 、节点为 n ，则深度为 int(log 2 N)+1  3 、满二叉树与完全二叉树 满二叉树 不缺枝 完全二叉树：仅缺右子树 注意完全二叉树节点编号间关系  4 、二叉树的存储 采用双链表

10  5 、二叉树的遍历 遍历：不重复访问所有结点 前序：根、左、右 中序：左、根、右 后序：左、右、根  注意从上到下均按上述顺序  例 1.33b 左 前： abdhiejkcflg ；中 :hdibjekalfcg 后 :hidjkeblfgca

11 1.7 查找技术  1 、顺序查找 无序表、链表  2 、二分法查找 有序表，最多 log2N 次

12 1.8 排序技术 1 、交换类排序  A 、昌泡法排序 前后顺序交换改变逆序 n(n-1)/2  B 、快速排序法 取一个中点两边与中点比较交换 2 、插入类排序  A 、简单插入排序 从第一个开始小的插在前 n(n-1)/2  B 、希尔排序法 分成若于子序列排序后减少子序列个数。

13 3 、选择类排序法  A 、简单选择排序法 找出最小元素排在队列前 n(n-1)/2  B 、堆排序法 建二叉树、调整二叉树位置达到排序效果。