计算机二级C语言学习总结1

计算机二级C语言知识归纳1

（本知识归纳建立在有C语言基础之上，系个人学习归纳，）

1.数据结构与算法

1. 算法是一组有穷的指令集，是解决方案的准确而完整的描述。确定性，有穷性， 可行性是算法的基本特征
2. 算法的复杂度包括时间复杂度和空间复杂度，前者指执行算法所需要的计算工作量，后者之执行算法所需要的内存空间。
3. 数据结构分为逻辑结构（数据元素之间的逻辑关系包括数据对象和数据对象之间的关系）存储结构（也称数据的物理结构，包含数据元素的存储方式和关系存储方式）注意：数据的逻辑结构与数据的存储结构无关。常见存储结构有
   ，顺序，链接，索引
4. 线性结构：有且仅有一个根结点每个结点最多一个前件也最多一个后件。（包括：栈，队列，双向链表…）
   非线性结构:不满足线性结构的数据结构（包括：树二叉树…）

性表所有元素存储位置是连续的在存储空间中按逻辑顺序依次存放。

线性链表：（每个存储节点包含数据域与指针域）

1. 栈： 只允许在一端进行插入与删除的线性表
   注意栈包含正栈与倒栈
2. 队列：只允许一端插入另一端删除，允许插入端为队尾（rear）允许删除端为队头（front）。 、、、 队列的顺序存储结构一般采用循环队列的形式

其中队空与队满时都会有front=rear

7. 二叉树：二叉树为非线性结构，是一种特殊的树型结构，每个结点最多两棵子树

$$1.二叉树的k层上最多e^{2k?1}(K>1)$$
$$1.深度为m的二叉树最多有2^m?1个结点$$
$$3.在任意二叉树中度为0的节点总比度为二的结点多一个$$

二叉树包括满二叉树和全二叉树
二叉树的遍历有三种形式：前序遍历（根左右）；中序遍历（左根右）；后序遍历（左右根）此处为必考点建议刷题掌握

8. 顺序查找（从表一端开始依次扫描各元素）线性无序表与链式存储结构只能用顺序查找 、、、、
9. 对于长度为n的有序线性表最坏情况下二分查找需log2n次而顺序查找需n次。（1.用顺序存储结构2.线性表是有序表）

10.排序法： 希尔排序（最坏情况）$$O(n^{1.5})$$堆排序最坏情况$$O(nlog2n)$$冒泡、快速、插入、简单排序均为$$n(n?1)/2$$

依然建议计算机二级多刷题，有些选择题刷多了也就没有一点问题了。后面的编程题其实并不难，加油，计算机二级必过