文档介绍：计算机等级考试 公共基础知识
2012版（HNU）
第*页
计算机二级考试公共基础知识大纲
数据结构与算法
程序设计基础
软件工程基础
数据库设计基础
这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（ D)算法在执行过程中所需要的基本运算次数
(5) 算法的空间复杂度是指 (09年9月)
A）算法在执行过程中所需要的计算机存储空间
B）算法所处理的数据量
C）算法程序中的语句或指令条数
D）算法在执行过程中所需要的临时工作单元数
(6) 下列叙述中正确的是 (06年9月)
A）一个算法的空间复杂度大，则其时间复杂度也必定大
B）一个算法的空间复杂度大，则其时间复杂度必定小
C）一个算法的时间复杂度大，则其空间复杂度必定小
D）上述三种说法都不对
(D)
计算工作量
(A)
(D)
第*页
计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。
二、数据结构
程序=算法+数据结构
数据结构是指相互有关联的数据元素的集合。
一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。
一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。
第*页
二. 数据结构
数据结构是指相互有关联的数据元素的集合。
数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
第*页
1. 逻辑结构
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
数据的逻辑结构包含：
（1）表示数据元素的信息；
（2）表示各数据元素之间的前后件关系。
例：
1. 一年四季的数据结构
B=(D,R)
D={春，夏，秋，冬}
R={(春，夏) ,(夏，秋),(秋，冬)}
2. 家庭成员的数据结构
B=(D,R)
D={父亲，儿子，女儿}
R={(父亲，儿子) ,(父亲，女儿)}
春
夏
秋
冬
数据结构的图形表示
父亲
儿子
女儿
第*页
常见的逻辑结构有：
线性结构、树形结构和图形结构。
线性结构
树形结构
图形结构
① 线性结构
结构中的每个元素之间存在一个对一个的关系；
② 树形结构
结构中的每个元素之间存在一个对多个的关系；
③ 图形结构或网状结构
结构中的每个元素之间存在多个对多个的关系。
其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。
第*页
2. 存储结构（物理结构）
计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
如：一年四季
家庭成员 计算机存储空间怎样存放？
存储结构指数据结构在计算机存储空间中的具体实现。
常见的存储结构有：
顺序存储结构
链式存储结构
索引存储结构
只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。
一种数据结构可以根据需要表示成一种或多种存储结构。
第*页
3. 数据的运算
检索
插入
删除
更新
排序
通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。
在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表
数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：
数据的逻辑结构
数据的存储结构
数据的运算
第*页
常见的数据结构