计算机二级级公共基础知识课件

1、计算机二级级公共基础知识课件计算机二级级公共基础知识课件计算机二级考试公共基础知识大纲计算机二级考试公共基础知识大纲 q 数据结构与算法数据结构与算法q 程序设计基础程序设计基础q 软件工程基础软件工程基础q 数据库设计基础数据库设计基础全国计算机等级考试二级公共基础知识不单独考试，与其他二级科目组全国计算机等级考试二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。合在一起，作为二级科目考核内容的一部分。考试方式考试方式:题型：选择题（题型：选择题（ 注：注：10 道选择题，占道选择题，占 总分值的总分值的10%）第一章 数据结构与算法(30%)n 考试大纲1

2、. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。算法的定义算法的定义算法是程序设计的核心算法是程序设计的核心 算法是在有限步骤内求解某一问题所使用的

3、一组定义明确算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程的规则。通俗点说，就是计算机解题的过程( (计算的方法计算的方法) )。在。在这个过程中，无论是形成解题思路这个过程中，无论是形成解题思路( (推理实现的算法推理实现的算法) )还是编还是编写程序写程序( (操作实现的算法操作实现的算法) )，都是在实施某种算法。，都是在实施某种算法。例：例： n个数从大到小进行排序。个数从大到小进行排序。 有多种排序方法有多种排序方法 ，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。 算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特

4、征：一个算法应该具有以下五个重要的特征：u 有穷性有穷性u 确定性确定性u 输入输入u 输出输出u 可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成 算法的两个基本要素：算法的两个基本要素：n 算术运算算术运算n 关系运算关系运算n 逻辑运算逻辑运算n 数据传输数据传输n 顺序顺序n 选择选择n 循环循环 一是对数据对象的运算

5、和操作； 二是算法的控制结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法 评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的计算工作量时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计

6、算机执行一种简单操作所需的平均时间与算法中进行简单操作的时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分的存储空间这三个部分 计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量计算机在进行数据处理时，实际需要处理的数据元素一般有很

7、多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个

8、数据元素之间存在有某种关系（一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。即联系），这种关系反映了该集合中的数据元素所固有的一种结构。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。u 1. 数据的数据的逻辑结构逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻

9、辑结构是指反映数据元素之间逻辑关系的数据结构。春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿u 数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。u 与数据在计算机中的存储位置无关，是独立于计算机的。 常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。 线性结构线性结构 结构中的每个元素之间存在一个结构中的每个元素之间存在一个对一个的关系；对一个的关系； 树形结构树形结构 结构中的每个元素之间存在一个结构中的每个元素之间存在一个对多个的关系；对多个的关系； 图形结构或网状结构图形结

10、构或网状结构 结构中的每个元素之间存在多个结构中的每个元素之间存在多个对多个的关系。对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。示，也可以直观地用图形来表示。 数据的存储结构（物理结构）数据的存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系储空间中，并且，各数据元素在计算机存储空间

11、中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。不一定是相同的，而且一般也不可能相同。存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n 顺序存储结构顺序存储结构n 链式存储结构链式存储结构n索引存储结构存储结构u只抽象地反映数据元素之间的关系的结构，只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构而不管其存储方式的数据结构称为逻辑结构。u一种数据结构可以根据需要表示成一种或多种存储一种数据结构可以根据需要表示成一种或多种存储结构。结构。常见的数据结构： 线性结构和非线

12、性结构线性结构u 在数据元素的非空有限集合中，线性结构的逻辑特征如下：u 存在一个唯一的被称为“第一个”的数据元素u 存在一个唯一的被称为“最后一个”的数据元素u 除第一个之外，集合中的每个数据元素均有且只有一个直接前驱u 除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构u 非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。 线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。春春夏夏秋秋冬冬记录记录1 020XX001 张三张三 男男记录记录2 020XX003 李四李四 女

13、女 记录记录3记录记录4线性表的存储结构有两种：线性表的存储结构有两种：顺序存储结构、链式存储结构顺序存储结构、链式存储结构n线性表的顺序存储结构用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素，即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址基地址 一个数据元素所占存储量一个数据元素所占存储量 线性表的顺序存储结构称为顺序表线性表的顺序存

14、储结构称为顺序表。u 顺序表的插入运算顺序表的插入运算u 顺序表的删除运算顺序表的删除运算 在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的线性表是合适的。u 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各元素的存储顺序也链式存储结构不要求逻辑上相邻的数据元素

15、物理位置也相邻，而且各元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。是任意的。各数据元素的先后关系是由各结点的指针域指示。u 链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：u 单链表的插入运算单链表的插入运算 u 单链表的删除运算单链表的删除运算采用链式存储结构，存储空间开销较大，但是进行插入和删除运算采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点循环链表是

16、加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。的指针域指向头结点。 a1a2a5a3a4HEAD319510HEAD31510 a2 a3 a4 a1双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。趋。 u 顺序存储结构顺序存储结构注意：注意：u 数据元素在计算机存储空间中的位置关系数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。与它们的逻辑关系不一定是相同的。u 一个逻辑数据结构可以有多种存储一个逻辑数据结构可以有多种存储结

17、构，且不同的存储结构影响数据处结构，且不同的存储结构影响数据处理的效率理的效率 。u链式存储结构链式存储结构 线性表线性表 : a1，a2，a3，a4，a5 栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。 栈栈n顺序栈的进栈和出栈运算：顺序栈的进栈和出栈运算：栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。n栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种先进后出（后进先出）的线性表。n通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的物理存储结构可以用顺序结

18、构，也栈的物理存储结构可以用顺序结构，也可以用链表结构。可以用链表结构。n栈的基本运算有三种：入栈、栈的基本运算有三种：入栈、退栈和读栈顶元素退栈和读栈顶元素队列队列n队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。n队列是一种先进先出先进先出的数据结构。n向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。栈的物理存储结构可以用顺序结构，也可以用链表结构。栈的物理存储结构可以用顺序结构，也可以用链表结构。队列队列的基本运算有三种的基本运算有三种：入

19、队出队读队首元素：入队出队读队首元素 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首进行删除的一端称做队首(front)。 u 线性表线性表 线性结构u 栈栈 是特殊的线性表 u 队列队列 也是一种操作受限的特殊的线性表u 树树 （树型结构）（树型结构）是一种重要的非线形数据结构常见数据结构的逻辑结构常见数据结构的逻辑结构一个非空的数据结构若满足下面的两个条件，则这种数据结构即一个非空的数据结构若满足下面的两个条件，则这种数据结构即为为。 有且仅有一个根结点；有且仅有一个根结点； 除

20、第一个结点外，每一个结点最多有一个直接前驱结点；除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。 线性结构与非线性结构线性结构与非线性结构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为一个数据结构不是线性结构，则称其为。a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u 树的概念树的概念u 二叉树的概念二叉树的概念u 二叉树的存储二叉树的存储u 二叉树

21、的遍历二叉树的遍历树及其基本概念树及其基本概念n树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。n树是树是(n0)(n0)个结点的有限集合个结点的有限集合，在任意一棵非空树中： (1)有且仅有一个特定的结点称为根结点。 (2)当n1时，其余的结点可分为m个互不相交的子集T1,T2,Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。n集合为空的树简称为空树；树中的元素称为结点。ABDFECGHIJKM1)度：结点拥有的子树数。度：结点拥有的子树数。2)叶子节点叶子节点(终端结点终端结点)：度为：度为0的结点。的结点。3)层次：结点的层次从根开始定义，根层次：结点的

22、层次从根开始定义，根为第一层，根的孩子为第二层。为第一层，根的孩子为第二层。4)深度：树中结点的最大层次称为树的深深度：树中结点的最大层次称为树的深度或高度度或高度。 树中根结点的层次为树中根结点的层次为1，根，根结点子树的根为第结点子树的根为第2层，以此类推；层，以此类推；树中所有结点层次的最大值树中所有结点层次的最大值；n二叉树是n(n0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。n二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒

23、。二叉树是一种有序的树形结构。它与一般树形结构的区别二叉树是一种有序的树形结构。它与一般树形结构的区别是：是： 1)每个结点最多有两棵子树；每个结点最多有两棵子树； 2)子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。【性质1】 在二叉树的第在二叉树的第K层上最多有层上最多有2k-1个结点（个结点（k1）【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h -1个结点（个结点（h 1）【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点满二叉树满二叉树 最大层的结点最大层的结点均向左靠齐均向左靠齐 完全二

24、叉树完全二叉树 ADCBEF满二叉树和完全二叉树满二叉树和完全二叉树如果一个深度为如果一个深度为h的二叉树拥有的二叉树拥有2h-1个结点，则将它称为个结点，则将它称为满二叉树。满二叉树。有一棵深度为有一棵深度为h，具有，具有n个结点的二叉树，若将它与一棵个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结的结点位置一一对应，则称这棵二叉树为完全二叉树。点位置一一对应，则称这棵二叉树为完全二

25、叉树。u 在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGE A G E F B C Dt二叉树的遍历二叉树的遍历n二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由得知，二叉树是由 根结点根结点 、 左子树左子树 和和 右子树右子树 三部分构成，则遍历二叉三部分构成，则遍历二叉树的操作可分解为树的操作可分解为 访问根结点访问根结点 、 遍历左子树遍历左子树 和和 遍历右子树遍历右子树 三个

26、子操作，三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样二叉树一样 递归递归 进行。进行。 前序遍历二叉树前序遍历二叉树中序遍历二叉树中序遍历二叉树后序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则(1) (1) 访问根结点；访问根结点；(2) (2) 先序遍历左子树；先序遍历左子树；(3) (3) 先序遍历右子树。先序遍历右子树。 若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则(1) (1) 中序遍历左子树；中序遍历左子树；(2) (2) 访问根结点；访问

27、根结点；(3) (3) 中序遍历右子树。中序遍历右子树。 若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则(1) (1) 后序遍历左子树；后序遍历左子树；(2) (2) 后序遍历右子树；后序遍历右子树；(3) (3) 访问根结点。访问根结点。 查找是数据处理的重要内容。查找是数据处理的重要内容。u 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。u 若找到了满足条件的结点，称查找成功；否则称查找失败。若找到了满足条件的结点，称查找成功；否则称查找失败。 u 衡量一个查找算法的主要标准是查找过程中对关键字进行的平

28、均比较次数。衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。 u 通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：1）顺序查找：）顺序查找：线性表中最简单的查找方法。线性表中最简单的查找方法。 最坏情况下需比较最坏情况下需比较n次次2）二分查找（折半查找）：）二分查找（折半查找）：是一种效率较高的查找方法，但是只适合顺序存储是一种效率较高的查找方法，但是只适合顺序存储的有序表。的有序表。 最坏情况下需比较最坏情况下需比较log2nu 排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。排序指将一个无序序列整理成按关键字值递增或

29、递减排列的有序序列。u 排序方法中其排序对象一般是顺序存储的线性表。排序方法中其排序对象一般是顺序存储的线性表。 u 根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：u插入类排序法插入类排序法 简单插入排序简单插入排序 希尔排序希尔排序n选择类排序法选择类排序法简单选择排序简单选择排序堆排序堆排序n交换类排序法交换类排序法 冒泡排序冒泡排序 快速排序快速排序(15%)u考试大纲u1. 程序设计方法与风格。2. 结构化程序设计。3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。 u结构化程序设计方法的四条原则是

30、结构化程序设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3. 模块化；4. 限制使用goto语句。u 结构化程序的基本结构和特点：结构化程序的基本结构和特点：（1）顺序结构：）顺序结构： 简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）：）选择结构（分支结构）： 包括简单选择和多分支选择结构，（3）重复结构（循环结构）：）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。 1、对象：是面向对象方法中最基本的概念。、对象：是面向对象方法中最基本的概念。n属性即对象所包含的信息属性即对象所包含的信息n操作描述了对象执行的功能，操作也称为方法或服务。

31、操作描述了对象执行的功能，操作也称为方法或服务。2、类类：是指具有共同属性、共同方法的对象的集合。是指具有共同属性、共同方法的对象的集合。u 所以类是对象的抽象，对象是对应类的一个实例。所以类是对象的抽象，对象是对应类的一个实例。3、消息消息：是一个实例与另一个实例之间传递的信息。是一个实例与另一个实例之间传递的信息。消息的组成包括消息的组成包括 （1）接收消息的对象的名称；）接收消息的对象的名称； （2）消息标识符，也称消息名；）消息标识符，也称消息名； （3）零个或多个参数。）零个或多个参数。4、继承继承：是指能够直接获得已有的性质和特征，而不必重复定义他们。是指能够直接获得已有的性质和特

32、征，而不必重复定义他们。n 单继承指一个类只允许有一个父类单继承指一个类只允许有一个父类n 多重继承指一个类允许有多个父类。多重继承指一个类允许有多个父类。5、多态性多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。第三章第三章 软件工程基础软件工程基础u考试大纲 1. 软件工程基本概念，软件生命周期的概念，软件工具与软件开发环境。 2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3. 结构化设计方法，总体设计与详细设计。 4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测

33、试、集成测试和系统测试。 5. 程序的调试，静态调试与动态调试。 软件工程概念软件工程概念u软件工程是应用于计算机软件的定义、开发和维护的软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。一整套方法、工具、文档、实践标准和工序。软件工程包括软件工程包括3个要素：方法、工具和过程。个要素：方法、工具和过程。u软件周期：软件产品从提出、实现、使用维护到停止软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。使用退役的过程。软件生命周期三个阶段软件生命周期三个阶段:软件定义、软件开发、运行维软件定义、软件开发、运行维护，主要活动阶段是：护，主要活动阶段是

34、：（1）可行性研究与计划制定；可行性研究与计划制定；（2）需求分析；）需求分析；（3）软件设计；）软件设计；（4）软件实现；）软件实现；（5）软件测试；）软件测试；（6）运行和维护。）运行和维护。：着眼于数据流，自顶向下，逐层分解，建立系统的处着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。建立系统的逻辑模型。结构化分析的常用工具结构化分析的常用工具:1)数据流图数据流图；2)数据字典数据字典；3)判定树；判定树； 判定表。判定表。 软件设计包括：总体设计与详细设计软件设计包括：总体设计与详细设计

35、在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。合。常见的过程设计工具有：常见的过程设计工具有：图形工具（程序流程图图形工具（程序流程图,N-S,PAD）表格工具（判定表）表格工具（判定表）语言工具（语言工具（PDL伪码）伪码） 程序流程图程序流程图N-S图图PAD图图u 软件测试的目的软件测试的目的：发现错误而执行程序的过程。u 软件测试方法：软件测试方法：1)静态测试：静态测试：包括代码检查、静态结构分析、代码质量度量。不实际 运行软件，主要通过人工进行。2)动态测试：动态测试： 是基本计算机的测试

36、，主要包括白盒测试白盒测试方法和黑盒黑盒 测试测试方法 白盒测试白盒测试方法有：逻辑覆盖；基本路径测试黑盒测试黑盒测试方法有：等价类划分法；边界值分析法；错误推测法u 软件测试过程测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。第42页 u程序调试的任务是诊断和改正程序中的错误，主要程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。在开发阶段进行。 u软件调试软件调试n静态调试主要是指通过人的思维来分析源程序代静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。码和排错，是主要的设计手段。n动态调试是辅助静态调试。主要调试方法有：动态

37、调试是辅助静态调试。主要调试方法有：（1）强行排错法；）强行排错法；（2）回溯法；）回溯法；（3）原因排除法。）原因排除法。第四章 数据库设计基础n考试大纲n1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。实际上就是描述事物的符号记录。实际上就是描述事物的符号记录。：是数据的集合，具有统一的结构形式并存放于统一的存储介质：是数据的集合，具有统一的结构形式并存放于统一

38、的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。内，是多种应用数据的集成，并可被各个应用程序共享。：一种系统软件，负责数据库中的数据组织、数据操纵、：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据维护、控制及保护和数据服务等，是数据库的核心。：由数据库（数据）、数据库管理系统（软件）、数据库管：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。运行实体。：由数据库系统、应用软件及应用界面三者组成

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

40、的特点n数据的集成性n数据的高共享性和低冗余性n数据的独立性n数据统一管理和控制。(1)人工管理人工管理阶段阶段：人工管理阶段人工管理阶段：存储设备比较落后 第一代计算机：输入 处理 输出(2)文件文件系统阶段系统阶段 ：按名存取（出现数据与程序的概念） 实现了以文件为单位的数据共享实现了以文件为单位的数据共享(3) 数据库系统管理阶段数据库系统管理阶段:实现了以记录和数据项为单位的文件共享实现了以记录和数据项为单位的文件共享 特点：特点：1）提高数据的共享性）提高数据的共享性 2）减少数据的冗余（但并没有消除）减少数据的冗余（但并没有消除） 3）增加了数据余程序的独立性）增加了数据余程序的独

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

42、型按不同的应用层次分成三种类型：n概念数据模型n逻辑数据模型n物理数据模型（1）实体实体：现实世界中的事物现实世界中的事物；（2）属性属性：事物的特性；事物的特性；（3）联系联系：现实世界中事物间的关系。现实世界中事物间的关系。u 联系：联系反映概念世界中的实体集之间存在的一定关系。n一对一联系(1:1)n一对多联系(1:M)n多对多联系(M:N)ER模型图示法模型图示法nERER图是实体联系模型的直观图形表示图是实体联系模型的直观图形表示。nE-R模型之间的联接关系：模型之间的联接关系：实体是概念世界中的基本单位，实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值属性有属性域

43、，每个实体可取属性域内的值。一个实体的所有属性值叫元组。一个实体的所有属性值叫元组。nE-R模型的图示法：模型的图示法：（1）实体集表示法）实体集表示法：用长方形（2）属性表法）属性表法：用椭圆形（3）联系表示法）联系表示法：用菱形层次模型（采用树型结构）层次模型（采用树型结构）图图1-4 层次模型示例层次模型示例网络模型（采用无向图型结构）网络模型（采用无向图型结构）关系模型（采用二维表结构）关系模型（采用二维表结构）u 关系模型用关系模型用二维表结构二维表结构来表示实体来表示实体之之间联系间联系的模型的模型，简称表，由表框架及表的元，简称表，由表框架及表的元组组成。一个二维表就是一个关系。组组成。一个二维表就是一个关系。关系关系 二维表（等价）二维表（等价） 关系的组成：关系的组成：1）元组：二维表的每一行）元组：二维表的每一