计算机二级公共基础知识考前培训班

1、1 二级公共基础知识二级公共基础知识 全国计算机等级考试全国计算机等级考试 2 第一章 数据结构与算法(30%) 考试大纲 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复 杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表 示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序 和后序遍历。 7. 顺序查找与二分法查找算法；基本排序

2、算法（交换类排序，选择类 排序，插入类排序）。 3 知识点归纳 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。严格来说，一 个算法必须具有以下五个主要特征： 可行性 确定性 有穷性 输入 输出 综上，所谓算法，是一组严格定义运算顺序的规则，而且每 一个规则都是有效且明确的，此顺序将在有限的次数终止。 4 算法的基本概念 算法的组成要素 算法中对数据的运算和操作 算法的控制结构 算法设计基本方法 列举法 归纳法 递推 递归 减半递推 回溯法 5 算法的复杂度 算法的复杂度可分为时间复杂度和空间复杂度，是 衡量算法优劣的量度。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的工

3、作量。 一般情况下，算法中的基本操作重复执行的次数是 问题规模n的某个函数f(n)f(n)。算法的时间量度记作： T(n)=O(f(n)T(n)=O(f(n)，表示随问题规模n n的增大，算法执行 时间的增长率和f(n)f(n)的增长率相同，称为算法的(渐 进)时间复杂度。 6 算法的复杂度 何估算算法的时间复杂度？ 任何一个算法都是由一个“控制结构”和若干“原操作原操作” 组成的，因此一个算法的执行时间可以看成是所有原操作的执 行时间之和 ( ( 原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间 ) ) 则算法的执行时间与所有原操作的执行次数之和成正比

4、。 从算法中选取一种对于所研究的问题来说是基本操作的原操作， 以该基本操作在算法中重复执行的次数作为算法时间复杂度的 依据。这种衡量效率的办法所得出的不是时间量，而是一种增 长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效 率的优劣。 7 算法的复杂度 算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内 存空间。空间复杂度作为算法所需存储空间的量 度，记作：S(n)=O(g(n)S(n)=O(g(n)，其中n n为问题的规模， 表示随问题规模的增大，算法运行所需存储量的 增长率与g(n)g(n)的增长率相同。 8 数据结构 利用计算机进行数据处理是计算机应用的一 个重要领域。数

5、据结构主要研究和讨论以下 三个方面的问题： 数据集合中各数据元素之间的逻辑关系，即 数据的逻辑结构。 在对数据进行处理时，各数据元素在计算机 中的存储关系，即数据的存储结构。 1.对各种数据结构进行的运算。 9 数据的逻辑结构 数据逻辑结构是对数据元 素之间存在的逻辑关系的 描述，它可以用一个数据 元素的集合和定义在此集 合上的若干关系表示。 与数据在计算机中的存储 位置无关，是独立于计算 机的。 10 数据的存储结构 数据的存储结构是数据元素及其关系在计算机存储器中 的表示。存储结构的主要内容是指在存储空间中使用一 个存储结点来存储一个数据元素，在存储空间中建立各 存储结点之间的关联，来表示

6、数据元素之间的逻辑关系。 常见的存储结构： 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 11 线性结构和非线性结构 线性结构 在数据元素的非空有限集合中，线性结构的逻辑特征如 下： 存在一个唯一的被称为“第一个”的数据元素 存在一个唯一的被称为“最后一个”的数据元素 除第一个之外，集合中的每个数据元素均有且只有一个 直接前驱 除最后一个之外，集合中的每个数据元素均有且只有一 个直接后继 非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直接前 驱和直接后继，树和图都属于非线性结构。 12 线性表 通常以下列 n 个数据元素的序列”表示线性表线性表 ： (a1,a2 ,.,ai

7、,.,an) 序列中数据元素的个数 n 定义为线性表的表长表长；n=0 时的线性表被称为空表空表。称 i 为ai在线性表中的位序位序。 13 线性表的顺序存储 线性表的顺序存储结构用一组地址连续地址连续的存储单元依次存放依次存放线 性表中的数据元素，即以“存储位置相邻存储位置相邻”表示“位序相继的 两个数据元素之间的前驱和后继的关系，并以表中第一个元素 的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址基地址 一个数据元素所占存储量一个数据元素所占存储量 14

8、 线性表的插入和删除运算 插入运算是指在线性表的某个指定位置增加一个新 结点。 一般情况下，要在第i(1in)个元素之前插入一 个新元素时，首先要从最后一个元素开始，直到第 i个元素之间共n-i+1个元素依次向后移动一个位置， 然后将新元素插入到第i项。 删除运算是指撤销结构中的某个结点。 一般情况，要删除第i(1in)个元素，要从第 i+1个元素开始，直到第n个元素，共n-i个元素依 次向前移动一个位置。 15 栈 栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和 删除的一端称为栈顶，另一端称为栈底。 栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈 底元素总是最先被插入

9、，也是最后被删除的元素。因此，栈是一种 后进先出后进先出的线性表。 通常用指针top指示栈顶位置，用指针bottom指示栈底位置。 16 栈的顺序存储及运算 用一维数组S(1:m)作为栈的顺序存储空间，m为栈 的最大容量。top=0表示栈为空，top=m表示栈满。 栈的操作 入栈：在栈顶位置插入一个新元素，栈顶指针top加1。 退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针 top减1。 取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删 除栈顶元素，栈顶指针不变。 17 队列 队列是一种先进先出的线性表，它只允许在表的一端插入元 素(队尾)，在另一端删除元素(队头)。通常定义头指针fro

10、nt 指向队头元素的前一个位置，定义尾指针rear指向队尾元素 的位置。 队列是一种先进先出先进先出的数据结构。 向队尾插入一个元素的操作称为入队，从队头删除一个元素 的操作称为退队。 18 循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成 逻辑上的环状空间。 循环队列初始状态为空，即front=rear=m。 入队操作时，rear加1，若rear=m+1，则置rear=1； 退队操作时，front加1，若front=m+1，则置front=1。 在循环队列为空或为满时，均有front=rear，因此需要 设置标志s进行区分，定义s=0表示队列为空，s=1表示 队列非空。 19 单链

11、表 线性表的链式存储结构的特点是用一组任意的存 储单元(可以连续，也可以不连续)存储线性表的 数据元素，为了表示每个数据元素ai与其直接后继 元素ai+1之间的逻辑关系，对数据元素ai来说，除 了存储其本身的信息(数据域)之外，还需要存储 其后继元素的存储位置信息(指针域)。 指针域中存储的信息称为指针或链，N个结点链接 成一个链表，即为线性表的链式存储结构。由于 结点中只包含一个指针域，故称为单链表。 20 单链表 通常以单链表中第一个数据元素的存储地址 作为作为单链表的地址，称为头指针。整个 链表的存储必须从头指针开始(顺序存取)， 头指针指示链表中第一个结点的存储位置。 最后一个数据元素

12、没有直接后继，其指针域 为空。 21 单链表的插入和删除 22 双向链表和循环链表 在双向链表中的结点包含两个指针域，其中一个指向直接后继，另 一个指向直接前驱。 循环链表的特点是表中最后一个结点的指针域指向第一个结点，整 个链表成为一个由链指针相链接的环。据此，从表中任一节点出发 均可找到表中其它结点。在循环链表中增加了一个表头结点，其指 针域指向第一个元素结点，头指针则指向头结点。 HEADHEAD HEADHEAD HEADHEAD 23 树及其基本概念 树是一种简单的非线性结构，在树 中，所有的数据元素之间具有明显 的层次性关系。 树是(n0)个结点的有限集合，在 任意一棵非空树中：

13、(1)有且仅有一个特定的结点称为根 结点。 (2)当n1时，其余的结点可分为m个 互不相交的子集T1,T2,Tm，其中每 个有限子集本身又是一棵树，并且 称为根的子树。 集合为空的树简称为空树；树中的 元素称为结点。 24 树的主要术语 结点的度：结点拥有的子树数。 叶节点(终端结点)：度为0的结点。 双亲、孩子和兄弟：结点的子树的根节点称为 该结点的孩子，该结点称为孩子结点的双亲结 点。同一个双亲结点的孩子互称为兄弟。 层次：结点的层次从根开始定义，根为第一层， 根的孩子为第二层。 深度：树中结点的最大层次称为树的深度或高 度。 25 二叉树 二叉树是n(n0)个数据元素的 有限集，它或为空

14、集,或者含有 唯一的称为根的元素，且其余元 素分成两个互不相交的子集，每 个子集自身也是一棵二叉树，分 别称为根的左子树和右子树。 二叉树是另一种树型结构，其特 点是每个结点至多有两棵子树， 并且二叉树的子树有左右之分， 其顺序不能任意颠倒。 26 二叉树的基本性质 性质性质1 1 在二叉树的第i层上至多有2i-1个结点 （i1） 性质性质2 2 深度为k的二叉树至多有2k -1个结点 （k1） 性质性质3 3 对任何一棵二叉树T，如果其终端结点数为n0， 度为2的结点数为n2 ，则：n0 =n2+1 性质性质4 4 具有n个结点的二叉树，其深度至少为log2n +1 27 满二叉树和完全二叉

15、树 满二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是 说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结 点，且深度为m的满二叉树有2m-1个结点。 完全二叉树完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一 层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为 log2n +1。 从以上定义可知，满二叉树也是完全二叉树，反之则不然。 满二叉树满二叉树 最大层的结点最大层的结点 均向左靠齐均向左靠齐 完全二叉树完全二叉树 A D CB EF 28 二叉树的基本性质 性质性质5 5 如果对一棵有 n 个结点的完全二叉树（其深度为 lo

16、g2n +1）的结点按层序（从第1层到第log2n +1 层，每 层从左到右）从1起开始编号，则对任一编号为 i 的结点 (1in)，则: (1) 如果 i=1，则编号为 i 的结点是二叉树的根，无双亲； 如果 i1，则其双亲结点 parent(i)的编号是i/2。 (2) 如果 2in，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 lChild(i) 的编号 是 2i 。 (3) 如果 2i+1n，则编号为 i 的结点无右孩子；否则其右 孩子结点 rChild(i) 的编号是结点 2i+1。 29 二叉树的链式存储结构 在二叉树的链式存储结构中，每个结点设置

17、三个域， 即数据域，左指针域和右指针域，两个指针域分别存 储左右子树根节点的存储位置，即指针。 LchildvalueRchild L(i)V(i)R(i) 30 二叉树的链式存储结构 31 二叉树的遍历 二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结 构定义得知，二叉树是由根结点、左子树和右子树三部分 构成，则遍历二叉树的操作可分解为访问根结点、遍历左子树 和遍历右子树三个子操作，并且由二叉树的递归定义可知，遍 历左子树和遍历右子树可如同遍历二叉树一样递归进行。 先序遍历二叉树先序遍历二叉树中序遍历二叉树中序遍历二叉树后序遍历二叉树后序遍历二叉树 若二叉树为空，则空操作； 否则 (

18、1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。 若二叉树为空，则空操作； 否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 若二叉树为空，则空操作； 否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 32 二叉树的遍历 先序遍历：ABDEGHCFIJ 中序遍历：DBGEHACIJF 后序遍历：DGHEBJIFCA 33 查找 查找是指在一个给定的数据结构中查找某个指定的元素。 顺序查找 顺序查找一般是指在线性表中查找指定元素，基本方法如下： 从线性表的第一个元素开始，依次将线性表中的元素与被查 找元素进行比较，

19、若相等则表示找到，即查找成功；若线性 表中的所有元素与被查找元素都不相等，则查找失败。 如果线性表为无序表，即表中元素的排列是无序的，则不管 线性表采用顺序存储还是链式存储，都必须使用顺序查找。 如果线性表有序，但采用链式存储结构，则也必须使用顺序 查找。 34 查找 二分查找(折半查找) 二分查找法只适用于顺序存储的有序表。先确定 待查目标元素所在范围(区间)，然后逐步缩小范 围直至找到该元素，或者当查找区间缩小到0也没 有找到目标元素为止。 查找过程中，给定值首先和处于待查区间中间位 置的关键字进行比较，若相等，则查找成功，否 则将查找区间缩小到前半个区间 或 后半个区 间 之后继续进行查

20、找。 35 折半查找 二分查找 36 排序 排序是指将一个无序序列整理成按值递增或递减(本 章均采用递增规则)的有序序列。 排序可以在各种不同的存储结构上实现，本章所介 绍的算法以顺序存储的线性表为排序对象，在程序 设计语言中就是一维数组。 排序的算法种类很多，主要包括交换类排序、插入 类排序、选择类排序等。 37 交换类排序 冒泡排序 基本思想：从表头开始扫描线性表，在扫描的过程中依次比较相 邻两个元素的大小，若前面的元素大于后面的元素，则交换它们 的位置。显然，在扫描过程中，不断地将将相邻元素间较大的向 后移动，最后将线性表中最大的元素移到表尾。 然后，从后向前扫描剩下的线性表，同样在扫描

21、的过程中依次比 较相邻两个元素的大小，若后面的元素小于前面的元素，则交换 位置。在扫描过程中，不断地将将相邻元素间较小的向前移动， 最后将线性表中最小的元素移到表头。 对剩下的线性表重复上述过程，直到剩余线性表为空为止，此时 线性表变为有序。 38 冒泡排序示例 第一遍第一遍( (从前向后从前向后) ) 第一遍第一遍( (从后向前从后向前) ) 第二遍第二遍( (从前向后从前向后) ) 第二遍第二遍( (从后向前从后向前) ) 39 快速排序 基本思想：从线性表中选取一个元素，设为T，将线性表后面 小于T的元素移动到前面，将前面大于T的元素移动到后面， 将线性表分为两个部分(子表)，T放到分界

22、线的位置，这个过 程称为线性表的分割，通过一次分割，就以T为分界将线性表 分为两个子表，前面的子表中的所有元素均不大于T，而后面 子表中的元素均不小于T。按照上述原则对子表继续进行分割， 直到子表为空，则整个线性表有序。 40 快速排序 操作步骤： 首先，在表的第一个元素、最后一个元素和中间元素中选 取一个中值，设为P(k)，并将P(k)赋值给T，再将表中的 第一个元素移到P(k) 的位置。设两个指针i，j分别指向 表的起始和最后位置，反复操作以下两步： 将j逐渐减小，并逐次比较P(j)和T，直到发现一个P(j)T为止， 并将P(i)移到 P(j)的位置上。 上述两步操作交替进行，直到i和j指

23、向同一个位置，再将 T移动到P(i)的位置上，完成一次分割。 41 31 68 45 90 23 39 54 12 87 76 31暂存枢轴记录暂存枢轴记录T T： low highhighhigh 12 12 low 68 68 highhighhigh 23 23 low 45 45 highhigh 31 31 快速排序的一次分割过程快速排序的一次分割过程 31 42 插入类排序 简单插入排序 基本思想：将待排序列表分成两部分：已排序部分和 未排序部分。每次扫描将未排序列表中的第一个元素 取出并插入到已排序列表中的合适位置。包含n个元 素的列表最多需要n-1次扫描。 43 简单插入排序示

24、例 原始序列 第1趟 第2趟 第3趟 第4趟 第5趟 44 希尔排序 基本思想：将整个无序序列分割成若干个小的 子序列分别进行插入排序。 子序列的分割方法：将相隔某个增量h的元素构 成一个子序列，在排序过程中，逐次减小这个 增量，最后当h减到1时，进行一次插入排序， 排序完成。 增量序列一般取ht=n/2k(k=1,2log2n) 45 希尔排序 h=6h=6 h=1h=1 h=3h=3 完成完成 46 选择类排序 简单选择排序 基本思想：将待排序列表分成两部分：已排序 部分和未排序部分。找到未排序部分中的最小 元素并把它和未排序部分中的第一个元素进行 交换。经过一次选择和交换，列表中已排序部

25、 分增加一个元素，未排序部分减少一个元素。 每次把一个元素从未排序部分移动到已排序部 分称为完成一次分类扫描分类扫描或称为一趟排序一趟排序。 一个包含n个元素的列表需要进行n-1次扫描完 成排序。 47 简单选择排序示例 原始序列 第1趟 第2趟 第3趟 第4趟 第5趟 48 第二章 程序设计基础(15%) 考试大纲 1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属 性及继承与多态性。 49 知识点归纳 程序设计方法 程序设计是一门技术，需要相应的理论、方法和工 具来支持。就程序设计方法和技术的发展而言，主 要经历了结构化的程序设计和面向对象的程

26、序设计 阶段。 在程序设计中，通常采用“自顶向下，逐步求精” 的方法，即把一个模块的功能逐步分解，细化为一 系列具体的步骤，进而转换成一系列用某种程序设 计语言编写的程序。 50 程序设计风格 除了程序设计设计方法和技术之外，程序风格也 是非常重要的。良好的程序设计风格概括起来包 括以下及格方面： 源程序文档化 数据说明的方法 语句的结构 输入和输出 51 程序设计风格 源程序文档化 标识符的命名 程序的注释 序言性注释 功能性注释 程序的视觉组织 数据的说明 数据说明的次序应该规范化 说明语句中变量的安排有序化 使用注释说明复杂的数据结构 52 程序设计风格 语句结构语句结构 在一行内只写一

27、条语句 程序编写应优先考虑清晰性 除非对效率有特殊要求，程序编写要做到清晰第一，效率第二 首先要保证程序正确，然后才要求提高速度 避免使用临时变量而使程序的可读性下降 避免不必要的转移 尽可能使用库函数 避免使用复杂的条件语句 尽量减少使用“否定”条件的条件语句 数据结构要有利于程序的简化 要模块化，使模块功能尽可能单一化 利用信息隐蔽，确保每一个模块的独立性 从数据出发构造程序 不要修补不好的程序，要重写编写 53 程序设计风格 输入和输出 对所有输入数据检验合法性 检查输入项的各种重要组合的合法性 输入格式要简单，以使输入的步骤和操作尽可能简单 输入数据时，应允许使用自由格式 应允许缺省值

28、 输入一批数据时，最好使用输入结束标志 在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符 明确提示输入的请求，同时在数据输入结束时，应在屏幕上给 出状态信息 当程序设计语言对输入格式有严格要求时，应保持输入格式与 输入语句的一致性；给所有的输出加注释，并设计输出报表格 式。 54 结构化程序设计 结构化程序设计的原则 自顶向下。程序设计时，应先考虑总体，后考虑细节；先考 虑全局目标，后考虑局部目标。不要一开始就过多追求细节， 先从最上层总目标开始设计，逐步使问题具体化。 逐步求精。对复杂的问题，应设计一些子目标过渡，逐步细 化。 模块化。一个复杂问题肯定是有若干简单问题构成。模块化 是

29、把程序要解决的总目标分解为分目标，再进一步分解为具 体的小目标，每个小目标成为一个模块。 严格限制GOTO语句的使用。 55 结构化程序设计的基本结构和特点 程序由一些基本结构组成，任何一个程序都可以用 三种基本控制结构组成：顺序结构、选择结构和循 环结构，并且具有如下特点：单入口、单出口、结 构中无死循环，程序中三种基本控制结构之间形成 顺序执行关系。 一个大型程序应按功能分割成一些模块，并把这些 模块按层次关系进行组织。 在程序设计时应采用自顶向下、逐步细化的实施方 法。 56 面向对象程序设计 面向对象方法的基本概念 1.对象、类和属性 在面向对象程序设计中，对象是程序的基本单位。对象可

30、 以表示客观世界中的任何实体，是对问题域中某个实体的抽象。 每个对象可以用它本身的一组属性和它可以执行的一组操作来 定义。类是对一组具有共同属性和相似行为的对象的一种抽象， 描述了属于该类的所有对象的性质。 2.方法 方法有称为操作或服务，它描述了对象执行的功能，若通 过消息传递，还可为其他对象使用。 57 面向对象方法的基本概念 3.继承：继承是对象方法的一个重要特征。指一个类(子类)直接使用另一个 类(父类)的所有属性和方法。它可以减少相似类的重复说明，从而体现一般 性和特殊性的原则。 4.多态性：多态性可以用“一个对外界面，多个内部实现”来表示。可以通 过方法重载和方法重写来实现多态。重

31、载指一个类中可以有多个具有相同名 称的方法，由传递给它们的不同个数和类型的参数来决定执行那个方法。重 写指子类可以重新实现父类的某些方法，使其具有自己的特征。多态性机制 增加了面向对象软件系统的灵活性，提高了软件的可重用性和可扩充性。 5.消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的，消息 是一个对象与另一个对象之间传递的信息，它请求对象执行某一处理或回答 某一要求的信息。 58 面向对象程序设计的特点 按照人的思维方式对客观世界进行抽象 稳定性好 可重用性好 易于开发大型软件 可维护性好 59 第三章 软件工程基础 考试大纲 1. 软件工程基本概念，软件生命周期的概念， 软件工

32、具与软件开发环境。 2. 结构化分析方法，数据流图，数据字典，软 件需求规格说明书。 3. 结构化设计方法，总体设计与详细设计。 4. 软件测试的方法，白盒测试与黑盒测试，测 试用例设计，软件测试的实施，单元测试、集 成测试和系统测试。 5. 程序的调试，静态调试与动态调试。 60 知识点归纳 软件定义和特点 计算机软件式计算机系统中与硬件相互依存的另一 部分，是包括程序、数据及相关文档的完整集合。 计算机软件具有如下特点： 软件是一种逻辑实体，具有抽象性 软件生产没有明显的制造过程 软件在运行、使用期间不存在磨损、老化问题 软件的开发、运行对计算机系统具有依赖性 软件复杂性高，成本昂贵 软件

33、开发涉及诸多社会因素 61 软件危机 所谓软件危机是指在计算机软件开发和维护过程中 所遇到的一系列严重问题，包括： 软件需求的增长得不到满足 软件开发成本和进度无法控制 软件质量难以保证 软件不可维护或可维护性低 软件成本不断提高 软件开发生产率的提高赶不上硬件的发展和应用需 求的增长。 62 软件工程 为了消除软件危机，提出了软件工程学。软件工程是 应用于计算机软件定义、开发和维护的一整套方法、 工具、文档、实践标准和工序。 软件工程的三要素 方法 工具 过程 63 软件工程过程 软件工程过程是把输入转化为输出的一组彼此相关的资 源和活动。它包括两方面含义： 1. 软件工程过程是指为获得软件

34、产品，在软件工具支 持下由软件工程师完成的一系列工程活动。通常包括四 种基本活动： P(Plan)：软件规格说明 D(Do)：软件开发 C(Check)：软件确认 A(Action)：软件演进 2.从软件开发的观点看，软件工程过程是使用适当的资 源，为开发软件进行的一组开发活动，在活动结束时将 输入(用户需求)转化为输出(软件产品)。 64 软件生命周期 软件从提出、实现、使用、维护到停止使 用的过程称为软件的生命周期。一般包括 以下几个阶段： 可行性研究与计划制定 需求分析 软件设计 软件实现 软件测试 运行和维护 65 软件工程目标与原则 软件工程的目标是在给定成本、进度的前提下，开发出

35、具有有效性、可靠性、可理解性、可维护性、可重用性、 可适应性、可移植性、可追踪性和可互操作性且满足用 户需求的软件产品。 为达到上述目标，在软件开发的过程中，必须遵循软件 工程的基本原则： 抽象 信息隐蔽 模块化 局部化 确定性 一致性 完备性 可验证性 66 软件开发工具与软件开发环境 软件开发工具对过程和方法提供自动或半自 动的支持。当这些工具被集成起来使得一个 工具产生的信息可以被另外一个工具使用时， 一个支持软件开发的系统就建立起来了，称 为计算机辅助软件工程(CASE)。CASE集成了 软件、硬件和一个软件工程数据库(包含了有 关分析、设计、程序构造和测试的重要信息) 从而创建了一个

36、软件开发环境。 67 结构化分析方法 结构化分析方法大多使用自顶向下、逐层分解的系统分 析方法来定义系统需求。在结构化分析的基础上，完成 系统的规格说明，建立系统的一个自顶向下的任务分析 模型。结构化分析方法是一种建模技术，模型的核心是 数据辞典，它描述了所有在目标系统中使用和生成的数 据对象。结构化分析常用的工具： 数据流图(DFD):描述数据在系统中如何被传送或变换以及 描述如何对数据流进行变换的功能，用于功能建模。 数据字典 判定树 判定表 68 数据流图 数据流图是描述数据处理过程的工具，它从数据传 递和加工的角度，来刻画数据流从输入系统到从系 统输入的移动变换过程。 数据流图的基本元

37、素 外部实体 数据流 处理(加工) 数据存储 69 数据字典 数据字典是关于数据的信息的集合，对数据流图中的 各个元素进行完整的定义和说明。数据流图和数据字 典共同构成系统的逻辑模型。 数据字典通常包含的信息有：名称、别名、何处使用、 如何使用、内容描述以及补充信息等。 70 软件需求 软件需求包括：功能需求、性能需求、环境需求、可 靠性需求、安全保密需求、用户界面需求、资源使用 需求、成本消耗需求、开发进度需求等。 需求分析应交付的主要文档是软件需求规格说明书 (SRS)。 71 结构化设计 结构化设计就是采用最佳的可能方法设计系统的各个组成部 分以及个成分之间的内部联系的技术。也就是说，结

38、构化设 计是这样一个过程：它决定用哪些方法把哪些部分联系起来， 才能解决好某个具体的有清楚定义的问题。从工程管理的角 度看，软件设计分两步完成： 1.概要设计，即总体设计。将软件需求转化为数据结构和软 件的系统结构。常用的软件结构设计工具是结构图 (Structure Chart)。 2.详细设计：即过程设计。通过对结构表示进行细化，得到 软件详细的数据结构和算法。过程设计常用的工具有：程序 流程图、N-S图、PAD图、过程设计语言PDL(伪码)。 72 软件测试 定义： 使用人工或自动手段来运行或测定某个系统的过程，其目的 在于检验它是否满足规定的需求或弄清预期结果与实际结果 之间的差别。

39、软件测试是为了发现错误而执行程序的过程。 一个好的测试用例是指可能找到迄今为止尚未发现的错误的 用例。 一个成功的测试是发现了至今尚未发现的错误的测试。 测试不能表明软件中不存在错误，它只能说明软件中存在错 误。 73 测试技术与方法综述 从是否需要执行被测试软件的角度，可将测试分为 静态测试和动态测试。 静态测试主要包括代码检查、静态结构分析、代码 质量度量等。 动态测试是基于计算机的测试，是为了发现错误而 执行程序的过程，或者说，是根据软件开发的各个 阶段的规格说明和程序的内部结构而精心设计的一 批测试用例，并利用这些测试用例去运行程序，以 发现程序错误的过程。 74 测试技术与方法综述

40、按照功能划分，可将软件测试分为黑盒测试和白盒测试。 黑盒测试将测试对象看作一个黑盒，不考虑程序内部的 逻辑结构和内部特性，只依据程序的需求规格说明，检 查程序的功能是否符合它的功能说明。这种测试又称为 功能测试或数据驱动测试。 白盒测试把测试对象看作一个透明的盒子，利用程序内 部的逻辑机构及有关信息，设计或选择测试用例，对程 序的所有逻辑路径进行测试。通过在不同点检查程序的 状态，确定实际的状态是否与预期的一致。这种测试又 称为结构测试或逻辑驱动测试。 75 软件测试的实施 软件测试按四个步骤进行： 单元测试：对软件设计的最小单位模块进行正确性的测试， 其目的是发现各模块内部可能存在的各种错误

41、。 集成测试：是测试和组装软件的过程，它是在把模块按照设 计要求组装起来的同时进行测试，主要目的是发现与接口有 关的错误。 确认测试：任务是验证软件的功能和性能以及其他特性是否 满足了需求规格说明中确定的各种需求，以及软件配置是否 完全、正确。 系统测试：将通过确认测试的软件，作为整个计算机系统的 一个元素，与计算机硬件、外设、支持软件、数据以及人员 等其他系统元素组合在一起，在实际运行环境中对其进行一 系列的集成测试和确认测试。 76 程序调试 程序调试的任务是诊断和修正程序中的错误。 调试的方法： 强行排错法 回溯法 原因排除法 77 第四章 数据库设计基础 考试大纲 1. 数据库的基本概

42、念：数据库，数据库管理系 统，数据库系统。 2. 数据模型，实体联系模型及E-R图，从E-R图 导出关系数据模型。 3. 关系代数运算，包括集合运算及选择、投影、 连接运算，数据库规范化理论。 4. 数据库设计方法和步骤：需求分析、概念设 计、逻辑设计和物理设计的相关策略。 78 知识点归纳 数据库的定义 1.长期存放在计算机内，有组织的、可共享的数据 集合。数据库中的数据按一定的数据模型组织、描 述和存储，具有较小的冗余度、较高的数据独立性 和易扩展性。 2.数据库是由一个互相关联的数据的集合和一组用 以访问这些数据的程序组成的。 79 数据库管理系统(DBMS) 数据库管理系统是一个帮助用

43、户创建和管理数据库的应 用程序的集合。因此，数据库管理系统也就是一个可以 帮助完成定义、构造和操纵数据库等处理目的的通用软 件系统。其主要功能如下： 数据模式定义 数据存取的物理构建 数据操纵 数据的完整性、安全性定义和检查 数据库的并发控制和故障恢复 数据的服务 为完成上述功能，DBMS提供了相应的语言： 数据定义语言(DDL) 数据操纵语言(DML) 数据控制语言(DCL) 80 数据库系统 数据库系统是由数据库、数据库管理系统、数据库管 理员、硬件平台和软件平台等几个部分组成的完整的 运行实体。 数据库系统的特点 数据的集成性 数据的高共享性和低冗余性 数据的独立性 数据统一管理和控制

44、81 数据库系统的内部体系结构 三级模式 概念模式：数据库系统中全局数据逻 辑结构的描述，全体用户的数据视图 外模式：又称为用户模式，是每个用 户的局部数据描述，用户的数据视图 内模式：又称为物理模式，是数据库 物理存储结构和物理存取方法的描述 二级映射 概念模式到内模式的映射 外模式到概念模式的映射 82 数据模型 数据是现实世界符号的抽象，数据模型是现实世界数据 特征的抽象，它从抽象层次上描述了系统的静态特征、 动态行为和约束条件，为数据库系统的信息表示和操作 提供一个抽象的框架。数据模型描述的内容包括三部分： 数据结构 数据操作 数据约束 数据模型按不同的应用层次分成三种类型： 概念数据

45、模型 逻辑数据模型 物理数据模型 83 实体联系(ER)模型 概念模型是面向现实世界的，其出发点是有效地 模拟显示世界，给出数据的概念化结构。实体联 系模型是一种广泛使用的概念模型，该模型将现 实世界的要求转化为实体实体、联系联系和属性属性等几个基 本概念，并用ER图直观地表示出来。 84 ER模型的基本概念 实体：概念世界中的基本单位，它们是客观存在且 能相互区别的事物。凡具有共性的实体可以组成一 个集合称为实体集实体集。 属性：属性用来描述实体的特征。一个实体可以有 多个属性，每个属性可以有值，一个属性的取值范 围称为该属性的值域值域。 联系：联系反映概念世界中的实体集之间存在的一 定关系。 一对一联系(1:1) 一对多联系(1:M)