1全国计算机等级考试-公共部分

《1全国计算机等级考试-公共部分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试辅导教程公共基础知识考试大纲考试方式1笔试，与程序设计语言（C、VB、VF等）笔试部分合为一张试卷。2公共基础知识占笔试试卷的30分。310道选择题、5道填空题。基本要求1掌握算法的基本概念2掌握基本数据结构及其操作3掌握基本排序和查找算法4掌握逐步求精的结构化程序设计方法5掌握软件工程的基本方法，具有初步应用相关技术进行软件开放的能力6掌握数据库的基本知识，了解关系数据库的设计考试内容——数据结构与算法1算法的基本概念：时间复杂度、空间复杂度2数据结构的基本概念：逻辑结构、存储

2、结构、图形表示线性结构与非线性结构3线性表的定义：顺序存储结构、插入与删除操作4栈和队列：顺序存储结构、基本运算5线性链表：结构、基本运算6树的基本概念：二叉树、遍历7查找技术：顺序、二分查找8排序技术：交换、选择、插入排序第一章：数据结构与算法第一节算法的基本概念1定义算法是指解题方案的准确而完整的描述。算法不等于程序,当然程序也可以作为算法的描述,但程序还需考虑很多与方法和分析无关的细节问题。2算法的基本特征（1）可行性同一个算法在不同精度的计算机上应得到相同的结果（2）确定性算法中的每一步必

3、须有明确的定义，不允许有多义性。（3）有穷性执行有限步骤后终止，应包括合理的执行时间。（4）拥有足够的情报算法的结果与输入的数据有关，不同的输入有不同的结果。当输入错误时，算法可能无法执行。当算法拥有足够多的情报时（考虑的输入可能性越多），出错的可能越小。综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止．3算法的基本要素一对数据对象的运算和操作;二算法的控制结构。（1）对数据对象的运算和操作算术、关系、逻辑运算和数据传输（赋值、输

4、入、输出）***（2）算法的控制结构控制结构一般可分为顺序、选择、循环三种基本结构。描述算法有传统流程图、N-S结构化流程图、算法描述语言等。***4算法复杂度算法复杂度主要包括时间和空间复杂度。（1）时间复杂度（次数）指算法的运算次数。（注意：不是指运算的时间）（2）空间复杂度（内存空间）执行算法需要的内存空间。包括：程序所占的空间输入的数据所占的空间运算时所需的空间算法的时间复杂度是指（）A执行算法程序所需要的时间B算法程序的长度C算法执行过程中所需要的基本运算次数D算法程序中的指令条数算法的

5、空间复杂度是指（D）A算法程序的长度B算法程序中的指令条数C算法程序所占的存储空间D算法执行过程中所需要的存储空间第2节数据结构的基本概念计算机处理数据，主要考虑两个方面：一提高数据处理的速度？二节省存储空间？数据结构主要研究三个方面的问题：（1）数据的逻辑结构：各数据元素间所固有的逻辑关系（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系（3）对各种数据结构进行的运算。1数据结构的概念数据—需要处理的数据元素的集合结构—关系，是集合中各个数据元素之间存在的关系数据结构是指反映数据元

6、素之间关系的数据元素集合的表示（1）逻辑结构反映数据元素之间逻辑关系的数据结构。例如：春、夏、秋、冬，主要指前件、后件的关系（2）存储结构(物理结构)在计算机存储空间的存放形式（数据的逻辑结构在计算机中的存放方式）春不一定存储在夏的前面数据的存储结构是指 （D）A存储在外存中的数据B数据所占的存储空间量C数据在计算机中的顺序存储方式D数据的逻辑结构在计算机中的表示2数据结构的图形表示父亲儿子女儿d1d2d3名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点春夏秋冬3线性结构和非线性结构一

7、个数据结构中一个数据元素都没有，称该数据结构为空的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分为线性结构和非线性结构线性结构必须满足以下两个条件：（1）有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。非线性结构不必须满足以上两个条件d1d2d3春夏秋冬在数据结构中，从逻辑上可以把数据结构分成（C）A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构第3节线性表和顺序存储结构1线性表的基本概念线由一组数据元素组成。是最简单、最常用的一

8、种数据结构.线性表是一种线性结构。非空线性表有如下结构特征：（1）有且只有一个根结点（2）有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。d1d2d3春夏秋冬姓名性别数学英语张三女7070李四男6590王五女68802线性表的顺序存储结构具有如下特点——逻辑相临，物理相临（1）线性表中所有元素所占的存储空间是连续的。（2）数据元素在存储空间中是按逻辑顺序依次存放的。姓名数学英语张三7070李四6590王五6880张三7070李四6590王五6