二级基础知识 第一章 数据结构与算法 全国计算机等级考试
1.1 算法 一、算法的概念 解决问题准确而完整的描述。 特征：可行性、确定性、有穷性、拥有足够的 情报。 要素：对数据运算操作（算术、逻辑）通过指 令序列程序来实现、算法的控制结构（执行顺 序）。 算法设计方法： 列举法：列举所有可能 归纳法：从特殊到一般
递推：从条件到结论 递归：函数的自调用 减半递推：中间分冶 回溯 : 反证 二、算法复杂度 1 、时间复杂度（工作量） 平均性态（平均值）；最坏情况（最大值） 2 、空间复杂度（资源） 内存资源
1.2 数据结构的基本概念 研究数据结构 —— 逻辑结构、物理结构、运算 的实现 1 、数据结构 数据逻辑结构：数据元素及元素间的关系， B=(D,R) 存储结构：内存中的存放形式 线性与非线性结构：有且仅有一个根结点；一个 前件，一个后件 只有一个根结点不是线性结构
1.3 线性表及其顺序存储结构 线性表：连续顺序存储，逻辑结构与存储结 构一致。 插入运算：插入点起所有元素后移 删除运算：删除点后所有元素前移
1.4 栈和队列 1 、栈 只有一个出入口仅有一个元素宽度的巷道， 先进后出 入栈、退栈、读栈顶元素 2 、队列 一个出口一个入口仅有一个元素宽度的巷道， 先进先出 队列移动，循环标志 s 0 空 入队；上溢、退队；下溢
1.5 线性链表 线性表的缺点：插入删除上的复杂性、空间 的连续性（预留、不够） 结点：元素 + 指针 Head---a1 *a2---a2 *a3…an null 双链表 栈与队列的链表实现 链表的插入删除 改变前后元素的指针指向，可以不改变位置 循环链表：增加一个表头结点数据不定, 最后 一指针指向表头
1.6 树与二叉树 1 、树 层次结构 根结点、叶子结点、子结点、深度（层数）、 节点的度（分叉数） 了解表达式的树表示 2 、二叉树 分叉数少于等于 2 （左右子树）, 一个根节点是 二叉树 性质 A 、 k 层节点少于 2^(k-1) B 、 m 深度的树节点总数为 2^m-1
C 、度为 2 的比度为 0 节点多一个 d 、节点为 n ，则深度为 int(log 2 N)+1 3 、满二叉树与完全二叉树 满二叉树 不缺枝 完全二叉树：仅缺右子树 注意完全二叉树节点编号间关系 4 、二叉树的存储 采用双链表
5 、二叉树的遍历 遍历：不重复访问所有结点 前序：根、左、右 中序：左、根、右 后序：左、右、根 注意从上到下均按上述顺序 例 1.33b 左 前： abdhiejkcflg ；中 :hdibjekalfcg 后 :hidjkeblfgca
1.7 查找技术 1 、顺序查找 无序表、链表 2 、二分法查找 有序表，最多 log2N 次
1.8 排序技术 1 、交换类排序 A 、昌泡法排序 前后顺序交换改变逆序 n(n-1)/2 B 、快速排序法 取一个中点两边与中点比较交换 2 、插入类排序 A 、简单插入排序 从第一个开始小的插在前 n(n-1)/2 B 、希尔排序法 分成若于子序列排序后减少子序列个数。
3 、选择类排序法 A 、简单选择排序法 找出最小元素排在队列前 n(n-1)/2 B 、堆排序法 建二叉树、调整二叉树位置达到排序效果。