计算机二级公共基础知识部分基本内容系统

1、本文由Daisytxs贡献 doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 二级计算机等级考试公共基础知识大纲要求 基本要求 掌握算法基本概念 掌握基本数据结构及其操作 掌握基本排序和查找算法 掌握逐步求精的结构化程序设计算法 掌握工程的基本算法,具有初步应用相关技术进行软件开发能力 考试内容 一 基本数据结构与算法 1 算法的基本概念,算法复杂度概念和意义(时间复杂度和空间复杂度 2 数据结构的定义,数据的逻辑结构和存储结构,数据结构的图形表示,线性结构与非线性结构的概念 3 线性表的定义,线性表的顺序存储结构极其插入与删除的运算 4 栈和队列的定义:栈

2、和队列的顺序存储结构及其基本运算 5 线性单链表多向链表与循环链表及其基本运算 6 树的基本概念,二叉树的定义及其存储结构,二叉树的前序,中序,后序遍历 7 顺序查找与二分法查找,基本排序算法(交换类,选择类,插入类 二 程序设计基础 1 程序设计方法与风格 2 结构化程序设计 3 面向对象的程序设计方法,对象,方法,属性及继承与多态性 三 软件的工程基础 1 软件工程基本概念,软件声明周期概念,软件工具与软件开发环境 2 结构化分析方法,数据流图,数据字典,软件需求规格说明书 3 结构化程序设计方法总体设计与详细设计 4 软件测试方法:白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测

3、试,集成测试和系统测试 5 程序的调试;静态调试与动态调试 四 数据库设计基础 1 数据库的基本概念;数据库,数据库管理系统,数据库系统,数据模型,E-R 图,从导出关系数据模型 2 关系代数运算包括集合运算及选择,投影,连接运算,数据库规范化理论 3 数据设计方法和步骤;需求分析,概念设计,逻辑设计,和物理设计的相关策略 公共基础知识各章掌握重点归纳 一 数据结构与算法 算法定义：所谓算法是解题方案的准确而完整的描述 算法的特征：可行性、确定性、有穷性、拥有足够的情报 算法的二要素；一是对数据对象的控制和操作，二是算法的控制结构 算法的三种基本控制结构：顺序，选择，循环 算法复杂度包括时间复

4、杂度和空间复杂度 时间复杂度是指执行算法所需要的计算工作量 可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量 算法的空间复杂度是指执行这个算法所需要的内存空间 数据结构是指相互关联的数据元素的集合 数据元素之间的前后件关系是指他们的逻辑关系，而与他们在计算机中的存储位置无关 数据的存储结构：数据的呒峁乖诩扑慊娲占渲械拇娣判问匠莆莸拇娲峁?BR数据结构的两大类型： 线性结构和非线性结构 线性结构与非线性结构都可以是空的数据结构 在计算机中存放线性表一种最简单的方法是顺序存储 栈是先进后出的线性表（栈顶 top 栈底 bottom） 队列是先进先出的线性（表排头指针 front 尾指

5、针 rear） 链式存储方式中每个结点由两部分组成：数据域和指针域 当从线性链表中删除一个元素后该元素存储结点就变为空闲，应将该空闲结点送回到可利用栈 循环链表增加了一个表头结点 HEAD 在二叉树的第 K 层上最多有 2 的 K-1 次方个结点 深度为 M 的二叉树最多有 2 的 M 次方-1 个结点 具有 N 个结点的二叉树，其深度至少为log2N+1，其中对数部分取整数 满二叉树与完全二叉树 二叉树的遍历；前序，中序，后序遍历 遍历方法：可先按要求逐个遍历个子树，然后进行排序 顺序查找最坏需比较 N 次 二分法查找最坏需比较 log2N 次 冒泡排序法最坏需比较 N（N-1）/2 次 简

6、单插入排序法最坏需比较 N（N-1）/2 次 希尔排序法最坏需比较 O（N 的 1.5 次方）次 简单选择排序法最坏需比较 N（N-1）/2 次 堆排序法最坏需比较 O（Nlog2N）次 二 程序设计基础 程序设计方法主要经过了结构化程序设计和面向对象的程序设计阶段 注释分为序言性注释和功能性注释 结 程序的质量与 GOTO 语句的数量成反比 构 程 顺序结构 化 三种基本结构 选择结构 当型循环结构先判断后执行 序 重复结构（循环结构） 设 直到型循环结构先执行后判断 计 选用的控制结构只准许有一个入口和一个出口 面向对象的方法和技术以对象（类）为核心 面 1 创建该类的实例，从而直接使用

7、向 对 两种方法可以重复是用一个对象类 2 从它派生出一个满足当前需要的新类 象 对象的基本特点：标识惟一性、分类性、多态性、封装性，模块独立性好 的 对象是类的实例，消息是实例之间传递的信息 程 消息构成：接收消息的对象的名称，消息名，零个或多个参数 序 （例如：MyCircle.show(GREEN） MyCircle 是接收对象名称 show 是消息名 GREEN 是参数 设计 继承具有传递性，继承分单继承和多重继承 三 软件工程基础 计算机软件是包括程序，数据及相关文档的完整集合 计算机软件定义：与计算机系统的操作相关的计算机程序，规程，规则以及可能有的文件文档及数据 软件按功能可以分

8、为；应用软件，系统软件，支撑软件（工具软件） 软件工程的三个要素：方法，工具，过程 软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程 软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件技术管理 软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性 、完备性、可验证性 软件开发环境是全面支持软件开发全过程的软件工具集合 结构化分析方法： 软件开发方法包括：分析方法，设计方法，程序设计方法 需求分析将创建所需的数据模型，功能模型，控制模型 需求分析阶段的工作：需求获取，需求分析，编写需求规格说明书，需求评审 需求分析方法：结构化分析方法（包括面向数据流的结构化分

9、析方法、面向数据结构的 Jackson 方法、面向数据 结构的结构化数据系统开发方法） ，面向对象的分析方法 结构化方法包括；结构化分析方法，结构化设计方法，结构化编程方法 结构化分析方法常用工具：数据流图（图符：加工，数据流，存储文件，源或潭） ，数据字典，判定树，判定表 数据字典是结构化分析方法的核心 数据字典的作用是对 DFD 中出现的被命名的图形元素的确切解释 判定表或判定树是以图形的形式描述数据流图的加工逻辑 结构化设计方法： ?软件设计是确定系统的物理模型 ?软件设计包括软件结构设计，数据设计，接口设计，过程设计 ?软件设计分两步：概要设计和详细设计 ?衡量软件的模块独立性使用耦合

10、性和内聚性两个定性的度量标准 ?内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量 ?耦合性是模块间相互连接的紧密程度的度量 1.概要设计 ?常用的软件结构设计工具是结构图（图符：一般模块，数据信息，控制信息） ?经常使用的结构图有四种模块类型：传入模块，传出模块，变换模块，协调模块 ?数据流类型：变换型，事务型 ?变换型系统结构图由输入，中心变换，输出三部分组成 2.详细设计 ?常见的过程设计工具有 图形类：程序流程图（图符：控制流，加工步骤，逻辑条件） N-S 图 PAD 图 语言类：PDL ?型：顺序型，选择型，先判断重复型，后判断重复型，多分支选择型 软件测试 测试是以查找错误为中

11、心 按是否需执行被测软件的角度分静态测试，动态测试 按功能划分可分为白盒测试，黑盒测试 白盒测试在程序内部进行 白盒测试的主要方法有：逻辑覆盖，基本路径测试 逻辑覆盖方式：语句覆盖（是逻辑覆盖中基本的覆盖） ，路径覆盖，判定覆盖，条件覆盖，判定-条件覆盖 黑盒测试是在软件接口处进行，完成功能验证 软件测试过程 4 步：单元测试，集成测试，验证测试，系统测试 集成测试分非增量方式组装和增量方式组装 自顶向下的增量方式，自底向上的增量方式，混合增量方式 程序调试 程序调试的任务是诊断和改正程序中的错误 主要调试方法：强行排序法，回溯法，原因排除法 四 数据库设计基础 数据分为：临时性数据和持久性数

12、据，数据 库系统处理的就是持久性数据 数据有型与值之分 数据库是数据的集合 数据库管理系统是数据库系统的核心 数据的完整性与安全性的维护是数据库管理系统的基本功能 数据库系统的组成部分：数据库、数据库管理系统、数据库管理员、系统平台之一硬件平台、系统平台之二软件 平台 数据库应用系统是数据库系统在加上应用软件及应用界面组成 数据管理发展经历三阶段：人工管理阶段、文件系统阶段、数据库系统阶段 数据独立性一般分为物理独立性与逻辑独立性两级 数据库在其内部具有三级模式及二级映射，三级模式分别是概念级模式、内部级模式和外部级模式，二级映射是 概念级到内部级的映射以及外部级到概念级的映射 数据模型所描述的内容有三部分：数据结构、数据操作、数据约束 数据模型按不同的应用层次分为：概念数据模型、逻辑数据模型、物理数据模型，其中概念数据模型是整个数据 模型的基础 E-R 模型关系：一对一，一对多，多对多 实体 联系 属性 E-R 图中两个实体间必然有一个联系 层次模型得到基本结构是树形结构 网状模型 关系模型采用二维表来表示 关系中的主键不允许出现空值 关系模型允许定义三类数据约束是实体完整性约束、参照完整性约束、用户自定义的完整性约束，其中实体完整 性约束和参照完整性约束是关系数据库所必须遵守的规则 插入、删除、修改的集合运算