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

本文格式为Word版，下载可任意编辑全国计算机等级考试二级公共基础知识教程 全国计算机等级考试二级公共根基学识 全国计算机等级考试二级公共根基学识考纲 考试内容 一、 根本数据布局与算法 1. 算法的根本概念；算法繁杂度的概念和意义（时间繁杂度与空间繁杂度） 2. 数据布局的定义；数据的规律布局与存储布局；数据布局的图形表示；线性布局与非线性布局的概念 3. 线性表的定义；线性表的依次存储布局及其插入与删除运算 4. 栈和队列的定义；栈和队列的依次存储布局及其根本运算 5. 线性单链表、双向链表与循环链表的布局及其根本运算 6. 树的根本概念；二叉树的定义及其存储布局；二叉树的前序、中序和后序遍历 7. 依次查找与二分法查找算法；根本排序算法（交换类排序，选择类排序，插入类排序） 二、 程序设计根基 1. 程序设计方法与风格 2. 布局化程序设计 3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性 三、 软件工程根基 1. 软件工程根本概念，软件生命周戎概念，软件工具与软件开发环境 2. 布局化分析方法，数据流图，数据字典，软件需求规格说明书。

第1页 全国计算机等级考试二级公共根基学识 3. 布局化设计方法，总体设计与细致设计 4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试 5. 程序的调试，静态调试与动态调试 四、 数据库设计根基 1. 数据库的根本概念：数据库，数据库管理系统，数据库系统 2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型 3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库模范化理论 4. 数据库设计方法和步骤：需求分析、概念设计、规律设计和物理设计的相关策略 考试方式 公共根基的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试片面合为一张试卷公共根基片面占全卷的30分公共根基学识有10道选择题和5道填空题 第2页 全国计算机等级考试二级公共根基学识 第一章 数据布局与算法 一、内容要点 （一）算法 1．算法的根本概念 算法是指解题方案的切实而完整的描述。

即是一组严谨地定义运算依次的规矩，并且每一个规矩都是有效的，且是明确的，没有二义性，同时该规矩将在有限次运算后可终止 1）算法的根本特征 （1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差 如：计算机的数值有效位是有限的，当大数和小数举行运算时，往往会由于有效位数的影响而使小数损失，因此，在算法设计时，理应考虑到这一点 （2）确定性 算法的设计务必是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性 例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一 第3页 全国计算机等级考试二级公共根基学识 ?x?y?12个方程?来求解，要求x和y的值，公式是正确的，但如 ?x?y?4何让计算能够举行计算，我们的算法不能把公式直接输进去，而理应设计出解题的步骤和过程 即设计的算法是计算工具所能够正常解决问题的过程 （3）有穷性 算法的有穷性，即在确定的时间是能够完成的，即算法理应在计算有限个步骤后能够正常终止。

例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的 （4）拥有足够的情报 算法的执行与输入的数据和供给的初始条件相关，不同的输入或初始条件会有不同的输出结果，供给切实的初始条件和数据，才能使算法正确执行 2）算法的根本要素 一是数据对象的运算和操作，二是算法的操纵布局 （1）算法中对数据的运算和操作 算法实际上是按解题要求从环境能举行的全体操作中选择适合的操作所组成的一组指令序列即算法是计算机所能够处理的操作所组成的指令序列 （2）算法的操纵布局 算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺 第4页 全国计算机等级考试二级公共根基学识 序有关 在算法中，操作的执行依次又称算法的操纵布局，一般的算法操纵布局有三种：依次布局、选择布局和循环布局 在算法描述是，有相关的工具对这三种布局举行描述，常用的描述工具有：流程图、N-S布局图和算法描述语言等 3）算法设计的根本方法 为用计算机解决实际问题而设计的算法，即是计算机算法 通常的算法设计有如下几种： （1）列举法 列举法的根本思想是，根据提出的问题，列举出全体可能的处境，并用问题中给定的条件检验哪些是得志条件的，哪些是不得志条件的。

列举法通常用于解决“是否存在”或“有哪些可能”等问题 例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法举行解决 使用列举法时，要对问题举行细致的分析，将与问题有关的学识条理化、完备化、系统化，从中找出规律 （2）归纳法 归纳法的根本思想是，通过列举少量的特殊处境，经过分析，结果找出一般的关系归纳是一种抽象，即从特殊现象中找出一般规律但由于在归纳法中不成能对全体的处境举行列举，因此，该方法得到的结论只是一种推测，还需要举行证明 （3）递推 第5页 — 6 —。