计算机二级基础知识风飞雪未扬
数据结构与算法
◆算法的基本概念1算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。2具有5个特性：（1）有穷性（在有穷步后完成）算法程序的运行时间是有限的（2）确定性（每一步都有确定的含义）（3）可行性（4）输入（一个算法有零个或多个输入）（5）输出（一个算法有一个或多个输出）3算法的复杂度包括：时间复杂度和空间复杂度。二者没有必然的联系。时间复杂度：执行算法所需要的计算工作量或基本运算次数。空间复杂度：算法所需要的空间的度量。◆数据结构的定义1数据结构包括数据的逻辑结构、数据的存储结构、数据的操作数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。包括：线性结构（线性表、栈、队列）和非线性结构（树和图）数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。一个逻辑结构可以有多种存储结构。◆线性表：线性表中元素的个数
（
0）定义为线性表的长度。顺序存储是线性表的一种最常用的存储方式。线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。1栈：是限定在表尾进行插入和删除操作的线性表。具有记忆功能只能顺序存储（错）允许插入和删除的一端叫栈顶。另一端叫栈底。后进先出的线性表2队列：是限定在一端插入而在另一端删除，插入端叫队尾，删除端叫对头。先进先出的线性表
1
f计算机二级基础知识风飞雪未扬
3栈和队列的顺序存储结构循环队列属于线性表存储结构中顺序存储结构和链式存储结构的前者。◆树1定义树的结点、度（结点的度）、叶子（终端结点）、数的度、深度、有序树和无序数2二叉树：结点至多有两棵子树，并且二叉树的子树有之分，次序不能颠倒。性质：★在二叉树的第i层上至多有2i1个结点★深度为k的二叉树至多有2k1个结点。★对任一个二叉树T，如果其叶子（终端结点数）为
，度为二的结点数为m则
m1★具有
个结点的完全二叉树的深度为k1，其中k是2
的整数部分。2二叉树的遍历先序遍历（根左右）中序遍历（左根右）后序遍历（左右根）◆查找算法（1）顺序查找顺序查找的平均查找长度为（
1）／2，最坏的情况下比较的次数为
2二分查找最坏情况下次数为log2
限定于顺序存储的有序线性表◆排序算法（1）插入类排序▲直接插入排序▲折半插r