全国计算机等级考试 计算机二级考试 公共基础知识 老师给的资料.pdf

第一讲 第一讲 数据结构与算法 数据结构与算法 考点一 算法的基本概念 考点1在笔试考试中考核的几率 为30%，主要是以选择题的形式 出现，分值为2分，此考点为识记 内容。 算法算法: 指解题方案准确而完整的描述指解题方案准确而完整的描述。 算法的基本特征算法的基本特征： ： 可行性 可行性 确定性 确定性 有穷性 有穷性 拥有足够的情报拥有足够的情报。 考点2 算法复杂度 算法的时间复杂度算法的时间复杂度 执行算法所需要的计算工作量, 即所需基本运算的执行次数 算法的空间复杂度算法的空间复杂度 执行算法所需要的内存空间 d a a d 考点3 数据结构的定义 数据集合中各数据的逻辑关系,即 逻辑结构逻辑结构 各数据元素在计算机中的存储关系, 即存储结构存储结构 考点4 线性结构与非线性结 构 如果一个非空的数据结构满足下列两 个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件， 也最多有一个后件。 则称该数据结构为线性结构 线性结构又称线性表。在一个线性 结构中插入或删除任何一个结点后 还应是线性结构。如果一个数据结 构不是线性结构，则称之为非线性 结构。 考点5 栈及其基本运算 栈是限定只在一端进行插入与删除 的线性表，通常称插入、删除的这 一端为栈顶，另一端为栈底。当表 中没有元素时称为空栈。 栈 a 1 b 2 c 3 d 4 e 5 f 6 bottom top 出栈 出栈 入入 栈 栈 栈顶 栈顶 栈底栈底 栈的特点：先进后出先进后出(filo,fist in last out). 栈中元素个数的求法：栈中元素个数的求法： topbottom+1 b c b b a 队列 e d c b a 退队 退队 入队入队 front rear 队头队头 队尾 队列的特点： 队列的特点： 先进先出先进先出(fifo,fist in last out) 队列中元素个数求法队列中元素个数求法 rearfront d 线性表的存储结构线性表的存储结构： ： 顺序存储结构 顺序存储结构 链式存储结构链式存储结构 顺序表的操作 优点：读取方便 缺点：插入、删除操作 时需要移动 7 6 5 4 3 2 1 线性链表 当元素(数据)变化频繁度大线性表 不宜用顺序存储结构 链式存储结构： 每个结点由两部分组成：数据域、 指针域 a1 a2 a3 a1 a2 a3 head a4 a5 a6 0 a1 a2 a3 head a4 a5 a6 单链表 循环链表 a1 a2 a3 双向链表双向链表 d 考点7 树与二叉树及其基 本性质 树是一种简单的非线性 结构 a b c d e f h g 根根 结结点点的度 的度 树树的的度 度 层层 深深度度 119 113 109 099 093 089 083 079 073 063 结点拥有的子树数称为结点的度度。 树的度树的度是树内各结点的度的最大值。 树中结点的最大层次称为树的深度深度 或高度。 度为0的结点称为叶子结点叶子结点。 二叉树：二叉树：它的特点是每个结点至多只有 两棵子树(二叉树中不存在度大于2的结 点)并且，二叉树的子树有左右之分， 其次是次序不能任意颠倒。 考试要点： (1)结点个数 (2)遍历顺序 a b e f c k m l 二叉树的性质： 性质1：在二叉树的第i层上至多有 个结点。 性质2：深度为k的二叉树的最多 结点数为 i 1 2 满二叉树与完全二叉树满二叉树与完全二叉树 a b e f c k m a b e f c k c b a c 25 h 满二叉树 满二叉树 是指这样的一种二叉树： 是指这样的一种二叉树： 除最后一层外除最后一层外，每一层上的所 每一层上的所 有结点都有两个子结点。有结点都有两个子结点。 是指这样的二叉树是指这样的二叉树：除最后一层 ：除最后一层 外，外，每一层上的结点数均达到最 每一层上的结点数均达到最 大值大值；在最后一层上只缺少右边 ；在最后一层上只缺少右边 的若干结点。的若干结点。 满二叉树与完全二叉树满二叉树与完全二叉树 a b e f c k m a b e f c k 考点考点1 二叉树的遍历（重点二叉树的遍历（重点） 1.先根遍历(前序遍历)特点是：先 访问根结点，接着访问左子树， 最后访问右子树。 abefck 2.中跟遍历(中序遍历)特点是：先 访问左子树，再访问根结点，最后 访问右子树。 ebfakc 3.后根遍历(后序遍历)特点是：先 访问左子树，再访问右子树，最后 访问根结点。 efbkca 先根遍历先根遍历(根左右根左右) 中根遍历中根遍历(左根右左根右) 后根遍历后根遍历(左右根左右根) a b c d e f h g a b e f c k m l 先根遍历： abeflckm 中根遍历： eblfak mc 后根遍历： elfbmkc a dbxea yfzc d 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 st.length 顺序表的查找过程顺序表的查找过程： ： 假设给定值 假设给定值 e = 64, e = 64, 问问: i = ?: i = ? i i 66 i i 线性表为无序表时，对于长度为n的 无序表，最坏的情况下比较n次。 表采用链式存储结构时，对于长度为 n的无序表，最坏的情况下比较n次。 b 二分法查找(对半查找)查找只适合用 于顺序存储的有序表，对于长度为n 的有序线性表，最坏的情况下比较 次。 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 st.elem st.length 例如: 例如: key = 64 key = 64 的查找过程如下的查找过程如下 low high mid low mid high mid low low 指示查找区间的下界指示查找区间的下界; ; high high 指示查找区间的上界指示查找区间的上界; ; mid mid = (low+high)/2。= (low+high)/2。 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 st.elem st.length 例如: 例如: key = 66 key = 66 的查找过程如下的查找过程如下 low high mid low mid high mid low low 指示查找区间的下界指示查找区间的下界; ; high high 指示查找区间的上界指示查找区间的上界; ; mid mid = (low+high)/2。= (low+high)/2。 high low mid highlow 1、什么是排序什么是排序？ ？ 排序是计算机内经常进行的一种操作，排序是计算机内经常进行的一种操作，其目的是 其目的是 将一组将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。 的记录序列。 例如例如：将下列关键字序列将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为调整为: 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 13 38 49 65 76 97 6 6 97 76 65 49 38 13 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 6 简单插入排序法 简单插入排序法：最坏的情况需要比较 的次数为 n(n1) 2 d 程序设计原则： 清晰第一，效率第二。 注重易读性，易理解，可以添加 注释。 结构化程序设计方法的主要原则 为： 自顶向下 逐步求精 模块化 限制使用goto语句。 a a 模块独立性要高，有两原则 高内聚（模块内） 低耦合（两模块之间） b a b 对象 对象具有如下特征：标识惟一 性、分类性、多态性、封装性、 模块独立性。 a 类 是具有共同属性、共同方法的对象的 集合。它描述了属于该对象类型的所 有对象的性质，而一个对象则是其对 应类的一个实例。 消息 消息是一个实例和另一个实例之 间传递的信息。 继承继承 继承是指类之间共享的属性和 操作机制。 继承分单继承和双继承。 单继承指一个类只允许有一个 父类，多重继承是指一个类允 许有多个父类。 d 多态性多态性 多态性是指同样的消息被不同 的对象接受时可以导致完全不 同的行动现象。 1 软件定义与软件特点 软件指的是程序程序、数据数据和相关文档相关文档 的完整集合。 根据应用目标的不同，软件可分应 应 用软件用软件、系统软件系统软件和和支撑软件支撑软件（或 工具软件）。 程 程 序序 d c b 软件工程包括三个三个要素：方法、方法、工 工 具、具、过程。过程。 软件工程包括3个要素：方法、工 具和过程。软件工程方法为软件开 发提供了“如何做“的技术。工具支持 软件的开发、管理、文档生成；过 程支持软件开发的各个环节的控制、 管理。 过程过程 2 软件工程过程与软件生命周期 软件工程过程与软件生命周期 软件生命周期软件生命周期是指软件产品从提出、是指软件产品从提出、实 实 现现、使用维护到停止使用退役的过程使用维护到停止使用退役的过程 一般包括可行性分析研究与需求分析、 设计、实现、测试、交付使用以及维护 等活动， a 可行性研究 可行性研究 初步项目计划 初步项目计划 需求分析 需求分析 使用 使用 测试 测试 详细设计 详细设计 概要设计 概要设计 实现 实现 维护 维护 退役 退役 开发 开发 阶段 阶段 定义 定义 阶段 阶段 维护 维护 阶段阶段 c 开发开发 需求 需求 分析分析 软件生命周期分三个阶段：软件定 义、软件开发、运行维护。 生命周期的主要活动阶段是：可行 性研究与计划制定、需求分析、软 件设计、软件实施、软件测试及运 行与维护。 面向数据流的结构化分析方法，就是 使用数据流图（dfd）、数据字典 （dd）、结构化英语、判定表和判 定树等工具，来建立一种新的、称 为结构化规格说明的目标文档。 结构化分析方法结构化分析方法的常用工具： 的常用工具： ?数据流图（数据流图（dfd） ） ?数据字典（数据字典（dd） ） ?判定表 判定表 ?判定树判定树 c 从工程管理角度来看，软件设计包 括： 概要设计 概要设计 详细设计详细设计 a b 典型的数据流类型有两种：典型的数据流类型有两种：变 变 换型换型和和事物型事物型。 详细过程设计的常用工具有： 详细过程设计的常用工具有： （1）图形工具：）图形工具：程序流程图程序流程图，n s，pad，hipo。 。 （2）表格工具：）表格工具：判定表。 判定表。 （3）语言工具：）语言工具：pdl（伪码）。伪码）。 b 数据流 数据流 程图程图 3 软件测试 软件测试是为了发现错误而执行程 序的过程。 软件测试的软件测试的目的目的是是： ： 发现软件中的错误发现软件中的错误。 软件测试分为软件测试分为静态测试静态测试和动态测试动态测试。 也可分为也可分为：白盒测试白盒测试和黑盒测试黑盒测试。 静态测试无须执行被测代码。静态测试无须执行被测代码。静态测试 一般是指人工评审软件文档或程序，借 以发现其中的错误。由于被评审的文档 或程序不必运行，所以称为静态测试。 动态测试是使被测代码在相对真实环境 动态测试是使被测代码在相对真实环境 下运行。下运行。 静态测试静态测试 白盒测试的主要方法有逻辑覆盖逻辑覆盖、 、 基本路径基本路径等。 黑盒测试方法有等价划分法，边界 黑盒测试方法有等价划分法，边界 值分析法、错误推测法、因果图等。值分析法、错误推测法、因果图等。 黑盒 黑盒 测试测试 白盒白盒 白盒 白盒 测试测试 软件测试过程分4个步骤，即 单元测试 单元测试 集成测试 集成测试 验收测试 验收测试 系统测试系统测试 单元单元 软件调试 在对程序进行了成功的测试之后将 进入程序调试（通常称debug，即 排错）。程序的调试任务是诊断和 改正程序中的错误。 软件测试的目的是发现软件中的错 软件测试的目的是发现软件中的错 误。 误。 软件调试目的是发现并改正程序中 软件调试目的是发现并改正程序中 的错误。 的错误。 软件测试贯穿整个软件生命周期软件测试贯穿整个软件生命周期。 。 软件调试主要在开发阶段。软件调试主要在开发阶段。 a b d a a 基本概念 数据（data） 数据库（database） 数据库管理系统（dbms） 数据定义语言（ddl）、数据操纵语 言（dml）、数据控制语言（dcl） c 数据模型 数据模型 ? 数据库系统的三级模式： （1）概念模式：数据库系统中全局数据逻辑结构 的描述，全体用户公共数据视图； （2）外模式：也称子模式与用户模式。是用户的 数据视图，也就是用户所见到的数据模式； （3）内模式：又称物理模式，它给出了数据库物 理存储结构与物理存取方法。 数据库系统的两级映射： （1）概念模式到内模式的映射； （2）外模式到概念模式的映射。 外模式 （用户数据库） 概念模式 （概念数据库） 外模式 （用户数据库） 外模式 （用户数据库） 内模式 （物理数据库） 应用 数据库 应用 应用 外模式-概念模式映射 概念模式-内模式映射 层次模型 ?基本结构：树形结构 ?特性：每棵树的且仅的一个无双亲结点 （根）；树中除根外所有结点有且仅有 一个双亲 ?支持的操作主要有：查询、插入、删除、 更新 网状模型 ?基本结构：简单二级树（系），其基本 数据单位为记录（实体集） o m1 m2 m4 m3 1 n n n n 一个系的实例 成员 记录 首记录 关系模型 ?数据结构：采用二维表二维表来表示，其由表 框架及表的元组组成；表框架由n（属 性元数）个命名的属性组成。 ?关系模型：以二维表为基本所建立的模 型 s# 2001001 sn sd sa 2001002 2001003 2001004 张浩然张浩然 ee 李一明 李一明 王 王 伟 伟 赵坚强赵坚强 ee ee ee 18 19 18 20 二维表 ?数据库设计生命周期 需求分析 概念设计 逻辑设计 物理设计 dbms模型 dbms模型 硬件、os支持 需求说明书 概念数据模型 逻辑数据模型 数据库内模式 概念设计 ?方法：