《(2012-9)等级考试公共基础考点(修订整理稿)》由会员分享，可在线阅读，更多相关《(2012-9)等级考试公共基础考点(修订整理稿)（55页珍藏版）》请在金锄头文库上搜索。
1、全国计算机等级考试二级公共基础知识指导 考试内容 一、基本数据结构与算法1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度） 。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序） 。 二、程序设计基础1.
2、 程序设计方法与风格。2. 结构化程序设计。3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工 程基础1. 软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。3. 结构化设计方法，总体设计与详细设计。4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5. 程序的调试，静态调试与动态调试。 四、数据库设计基础1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。2. 数据模型，实体联系模型及 E-R图，从 E-R图导出关系数据模型。3. 关系代
3、数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式1 、公共基础的考试方式为笔试，与 C语言（VisualBASIC、VisualFoxPro、Java、Access、VisualC+）的笔试部分合为一张试卷。公共基础部分占全卷的 30分。2 、公共基础知识有 10道选择题和 5道填空题。等级考试公共基础考点分析之数据结构与算法1.1算法考点 1算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都
4、是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。1 算法的基本特征(1)可行性(effectiveness) ：针对实际问题而设计的算法，执行后能够得到满意的结果。(2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。(3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。(4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可
5、能无效。2 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作包括：算术运算：主要包括加、减、乘、除等运算；逻辑运算：主要包括“与”、 “或” 、 “非”等运算；关系运算：主要包括“大于”、 “小于” 、 “等于”、 “不等于” 等运算；数据传输：主要包括赋值、输入、输出等操作。算法的控制结构：不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环 3 种基本控制结构组合而成。3 算法设计的基本方法：列举法、归纳法、递推、递归、减半递推
6、技术、回溯法。4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求考点 2算法的复杂度1算法的时间复杂度算法的时间复杂度，是指执行算法所需要的计算工作量。一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数 n表示)，它是问题的规模函数。即算法的工作量=f(n) 例如，在 NN矩阵相乘的算法中，整个算法的执行时间与该基本操作(乘法)重复执行的次数 n3成正比，也就是时间复杂度为 n3，即 f(n)=O(n3)(1)平均性态(AverageBehavior)所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。(2)最坏情况复杂性(Worst-case
7、Complexity)所谓最坏情况分析，是指在规模为 n时，算法所执行的基本运算的最大次数。2算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。1.2数据结构的基本概念考点 3数据结构的定义数据结构(datastructure) 是指反映数据元素之间的关系的数据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。一个数据结构应包含以下两方面信息：(1)表示数据元素的信息；(2)表示各数据元素之间的前后件关系。是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构研究的三个方面：（1）数据集合中和
8、数元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。1 数据的逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合 D 和定义在此集合中的若干关系 R 来表示。B=(D,R)一年四季的数据结构: D=春,夏,秋,冬, R=(春,夏),(夏,秋 ),(秋,冬)数据的逻辑结构包括集合、线性结构、树型结构和图形结构四种。2 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构(也称数据的物理结构)。由于数据元素在计算机存储空间中的位置关系可能与逻
9、辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系) ，在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。考点 4数据结构的图形表示数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合 D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据
10、元素之间的前后件关系，对于关系 R中的每一个二元组，用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点(也称为叶子结点)。一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据父亲儿子 女儿春 夏 秋 冬( a ) 一年四季数据结构 ( b ) 家庭关系数据结构结构中增加一个新结点(称为插入运算)，也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。考点 5线性结构与非线性结构如果在一个数据结构中一个数据元素都没有，
11、则称该数据结构为空的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。非空数据结构满足：(l)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称为线性表。一个线性表是 n个数据元素的有限序列。如果一个数据结构不是线性结构，称之为非线性结构。常见的线性结构有：线性表、栈与队列、线性链表常见的非线性结构有：树、二叉树、图1.3线性表及顺序存储结构考点 6线性表的定义线性表是 n(n0)个元素构成的有限序列(a1，a2，an)。在复杂的线性表中，由若干数据项组成的数据元素称为记录(r
12、ecord)，而由多个记录构成的线性表又称为文件(file)。在非空表中的每个数据元素都有一个确定的位置，如 a1是第一个元素，an 是最后一个数据元素，ai 是第 i个数据元素，称 i为数据元素 ai在线性表中的位序。非空线性表有如下一些结构特征：(1)有且只有一个根结点 a1，它无前件；(2)有且只有一个终端结点 an，它无后件；(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数 n称为线性表的长度。当 n=0时称为空表。考点 7线性表的顺序存储结构线性表的顺序储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线
13、性表中各数元素在存储空间中是按逻辑顺序依次存放的。ai 的存储地址为：ADR（ai）=ADR(a1)+（i-1）k，ADR（a1）为第一个元素的地址，k 代表每个元素占的字节数。顺序表的运算：插入、删除。考点 8顺序表的插入运算线性表的插入运算是指在表的第 i(1in+l)个位置上，插入一个新结点 x，使长度为 n的线性表(a1，ai-1，ai，an)变成长度为 n+1的线性表(a1，ai-1，x，ai，an)现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为 n。该算法的时间主要花费在循环结点后移语句上，该语句的执行次数(即移动结点的次数)是 n-i+1。由此可看出，所需移动结点的次
14、数不仅依赖于表的长度，而且还与插入位置有关。当 i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度 O(1)；当 i=1时，结点后移语句，将循环执行 n次，需移动表中所有结点，这是最坏情况，其时间复杂度为 O(n)。不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=pn+1=1/(n+1)因此，在等概率插入的情况下，也就是说，在顺序表上做插入运算，平均要移动表上一半的结点。当表长 n较大时，算法的效率相当低。虽然 Eis(n)中 n的的系数较小，但就数量级而言，它仍然是线性级的。因此算法的平均时间复杂度为 O(n
15、)。考点 9顺序表的删除运算线性表的删除运算是指将表的第 i(1in)个结点删除，使长度为 n的线性表：(a1，ai-1，ai，ai+1，an)变成长度为 n-l的线性表(a1，ai-1，ai+1，an)该算法的时间分析与插入算法相似，结点的移动次数也是由表长 n和位置 i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若 i=1，则前移语句将循环执行 n一 1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为 O(1)和 O(n)。删除算法的平均性能分析与插入算法相似。在长度为 n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均
16、次数，删除表中第 i个结点的移动次数为 n-i，故 pi表示删除表中第 i个结点的概率。在等概率的假设下，p1=p2=p3=pn=1/n由此可得： 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是 O(n)。1.4栈和队列考点 10栈及其基本运算12)(iisipEnidl ipE121)(1什么是栈栈实际也是线性表，只不过是一种特殊的线性表。栈(Stack)是只能在表的一端进行插入和删除运算配线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈(栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。假设栈 S=(al，a2，a3，an)，则 a1，称为栈底元素，an 为栈顶元素。栈中元素按a1
