第一章
计算机考试公共基础知识重点笔记完整版
第一章数据结构与算法
1.1算法的复杂性
1 .算法的基本概念
用计算机算法解决计算机问题的过程实际上正在实施某种算法。
(1)算法基本特征
算法一般具有可行性、确定性、穷举性和充分信息四个基本特征。
)2)算法的基本运算和操作
算法的基本运算和操作包括算术运算、逻辑运算、关系运算和数据传输。
)3)算法的三个基本控制结构
算法的三个基本控制结构是顺序结构、选择结构和循环结构。
)4)算法的基本设计方法
算法的基本设计方法：枚举法、归纳法、递归、递归、减半递归技术、回溯法。
)5)指令系统
命令系统是指一个计算机系统可以执行的所有命令的集合。
2 .算法的复杂性
算法的复杂性包括时间的复杂性和空间的复杂性。 注意两者的不同，不要混淆。 请参照表1-1。
表1-1算法的复杂性
名称说明
运行时间复杂度算法所需的计算工作量
空间复杂度执行该算法所需的内存空间
1.2数据结构
1.2.1逻辑结构和存储结构
1 .数据结构的基本概念
(1)数据结构
指相互关联的数据元素的集合。
)2)数据结构研究的三个方面
数据集合中各数据要素间固有的逻辑关系，即数据的逻辑结构
处理数据时，各数据要素在计算机中的存储关系，即数据的存储结构
对各种数据结构的运算。
2 .逻辑结构
的逻辑结构描述了数据元素之间的逻辑关系，可以用数据元素集合和为该集合定义的一些关系来表示。 的逻辑结构有两个要素。 一个是数据元素的集合，通常表示为d。 第二种关系是d上的关系，反映数据元素之间的前后关系，通常表示为r。 一个数据结构可以表示为B=(D，r )
在此，b表示数据结构。 为了反映d中各数据要素之间的前后关系，一般用二元组表示。 例如，如果将四季考虑为一个数据结构，则可以表示为B=(D，r )
D={春、夏、秋、冬}
R={ (春、夏)、(夏、秋)、(秋、冬) }
3 .存储结构
将数据的逻辑结构在计算机存储空间中的存储形式称为数据的存储结构(也称为数据的物理结构)。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，为了表示已经存储
页脚内容15