全国计算机考试二级公共基础知识

全国计算机等级考试二级公共基础知识

全国计算机等级考试二级公共基础知识考纲

考试内容

一、 基本数据结构与算法

1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、 程序设计基础 1. 程序设计方法与风格。 2. 结构化程序设计。

3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、 软件工程基础

1. 软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。

2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。

第1页

全国计算机等级考试二级公共基础知识

3. 结构化设计方法，总体设计与详细设计。

4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计

全国计算机等级考试二级公共基础知识

目录

二级公共基础知识考纲 ????????????????????????1 第一章 数据结构与算法??????????????????????2 第二章 程序设计基础???????????????????????19 第三章 软件工程基础???????????????????????23 第四章 数据库设计基础??????????????????????32

全国计算机等级考试二级公共基础知识考纲

考试内容

一、 基本数据结构与算法

1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与

非线性结构的概念。

3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。

6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排

序）。 二、 程序设计基础

1. 程序设计方法与风格。 2. 结构化程序

全国计算机等级考试二级公共基础知识复习题

一、选择题（在下列各题的A）、 B）、 C）、D）四个选项中，只有一个选项是正确的，请将正确选项

填涂在答题卡相应位置上。）

1.1 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及

A）数据的存储结构

B）计算方法 C）数据映象 D）逻辑存储 正确答案: A

1.2 数据处理的最小单位是

A）数据 B）数据元素 C）数据项 D）数据结构 正确答案: C

1.3 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成

A）动态结构和静态结构 B）紧凑结构和非紧凑结构 C）线性结构和非线性结构 D）内部结构和外部结构

正确答案: C

1.4 数据结构中，与所使用的计算机无关的是数据的

A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构

正确答案: C

1.5 在计算机中，算法是指

A）加工方法

B）解题方案的准确而完整的描述

C）排序方法 D）查询方法 正确答案: B 1.6 算法分析的目的是 A）找出数据结构的合理性 B）找出算法中输入和输出之间的

全国计算机等级考试辅导讲义

二级公共基础知识 第一章 数据结构与算法

1.1 算法

1、算法是指解题方案的准确而完整的描述。

*：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。 2、算法的基本特征

（1）可行性：针对实际问题而设计的算法，执行后能够得到满意的结果。

（2）确定性：每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。

（3）有穷性：算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。

（4）拥有足够的情报：算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。

1

一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。

*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

3、算法的基本要素：一是对数据对象的运算

二级公共基础知识

1、 2、 3、

算法是指解决方案的准确而完整的描述

算法的四个基本特性： 可行性 确定性 有穷性 拥有足够的情报

算法有两个基本的要素组成： 一、数据对象的运算和操作 二、算法的控制

结构 4、 5、

计算机中的基本操作 算术运算 逻辑运算 关系运算 数据运算

算法的控制结构给出了算法的基本框架，不仅决定了算法中各操作的执行顺序，

而且也直接反应了算法的设计是否符合结构化的原则。一个算法都可以用顺序、选择、循环3钟基本控制结构组成 6、 7、

算法的复杂度主要包括时间复杂度和空间复杂度

算法的时间复杂度是执行算法所需要的计算工作量。 他不仅应该与使用的计算

机、程序设计语言及程序编制者无关，而且应该与算法实现过程中的许多细节无关。 8、 9、

算法的空间复杂度是指执行这个算法所需要的内存空间。

如果一个数据结构中没有一个数据元素，则称该数据结构为空的数据结构。

10、 根据数据结构中个数据元素之间前后件关系的复杂程度，一般将数据结构分为 线性结构 和 非线性结构

11、 如果一个非空的数据结构满足 1、有且只有一个根结点； 2、 每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性结构又称线

全国计算机等级考试二级公共基础知识复习资料

www.ncre.me （共80个）

1）、算法的有穷性是指

（A）算法程序所处理的数据量是有限的 （B）算法只能被有限的用户使用 （C）算法程序的长度是有限的 （D）算法程序的运行时间是有限的 2）、在数据库设计中，将E-R图转换成关系数据模型的过程属于 （A）逻辑设计阶段 （B）物理设计阶段 （C）概念设计阶段 （D）需求分析阶段 3）、在软件开发中，需求分析阶段产生的主要文档是 （A）集成测试计划 （B）概要设计说明书

（C）软件需求规格说明书 （D）可行性分析报告 4）、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n－1)/2的排序方法是 （A）冒泡排序 （B）直接插入排序 （C）堆排序 （D）快速排序 5）、软件设计中模块划分应遵循的准则是 （A）高内聚高耦合 （B）低内聚低耦合 （C）低内聚高耦合 （D）高内聚低耦合 6）、下列关于栈的叙述正确的是 （A）不能删除数据

（B）栈按\先进先出\组织数据 （C）栈按\先进后出\组织数据 （D）只能在栈底插入数据

7）、结构化程序设计的基本原则不包括 （A）逐步求精 （B）多态性 （C）自顶向下 （D）模块化 8

公共基础知识

二级公共基础知识总结(30分：10选择+5填空)

复习及应试建议：

1．考生的复习必须遵守：“80/20的原则”

二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算法及数据结构、程序设计基础、软件工程基础和数据库。事实上，这些课程本身的涉及面就很广，难度系数较大。因此，这些课程甚至也是计算机专业学生最头疼的课程，对大多数考生来说其难度之大不言而喻。

所以，考生应把80%的时间用在20%的重点知识点上，争取用20%的重点知识点来答对80%的考题，这是考生复习二级考试的公共知识部分的总体思路。

2．复习的关键是考生必须准确判断和掌握常见考点

考生必须能够准确判断和掌握常见考点，例如：算法部分主要考查算法的概念及算法的复杂度；数据结构部分主要考查最基本的概念、最典型的数据结构和最常见的操作；程序设计部分主要考查程序设计风格的基本要求、结构化程序设计的最基本知识和面向对象程序设计的最常见概念；软件工程基础部分主要考查软件工程的基本概念及软件生命周期的各个阶段的基础知识；数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、数据库设计方法和步骤。对常见考点的准确把握会使考生避免盲目学习，从而能够轻松面对考试。

二级考

全国计算机等级考试二级公共基础知识课后习题及答案1 第一章 数据结构与算法 一.选择题

1.算法的时间复杂度是指( ) A. 执行算法程序所需要的时间 B. 算法程序的长度

C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 2.算法的空间复杂度是指( ) A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间 3.下列叙述中正确的是( )

A. 线性表是线性结构 B. 栈与队列是非线性结构 C. 线性链表是非线性结构 D. 二叉树是线性结构 4.数据的存储结构是指( ) A. 数据所占的存储空间量

B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据

5.下列关于队列的叙述中正确的是( )

A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D

本文由hbxshero贡献

ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。

计算机等级考试 公共基础知识 数计学院 卫春芳

计算机二级考试公共基础知识大纲 数据结构与算法

程序设计基础 软件工程基础 数据库设计基础

这四个方面在试卷中出现的情况是：选择题10个 （20分），填空题5个（10分），总分值占到了试 卷卷面分的30％，是一个不小的比例。 第2页

计算机二级考试公共基础知识试卷分析 章节 考试时间

数据结构 程序设 软件工 数据库设 计基础 程基础 计基础 与算法

2007年4月 2007年9月 2008年4月 2008年9月 2009年3月 2009年9月 2010年3月

10分 12分 10分 10分 10分 10分 10分 2分 4分 2分 2分 2分 2分 0分 10分 8分 8分 8分 8分 8分 10分 8分 6分 10分 10分 10分 10分 10分 第3页

一、基本数据结构与算法 算法

⒈ 算法的基 本概念

看看

全国计算机等级考试公共基础知识总结

第一章数据结构与算法

1.1 算法

算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：

（1）可行性；

（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；

（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；

（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念

数据结构研究的三个方面：

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑