二级公共基础知识new

1、二级公共基础知识1第一章数据结构与算法第二章程序设计基础 第三章软件工程基础第四章数据库设计基础2第一章数据结构与算法1.1算法1.2数据结构的基本概念1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表1.6树与二叉树1.7查找技术1.8排序技术3考试大纲1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树

2、的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。41.1算法1.1.1 算法的基本概念算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。1、算法的基本特征：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报51.1算法2、算法的基本要素：一是对数据对象的运算和操作；二是算

3、法的控制结构。（1）算法中对数据的运算和操作指令系统：一个计算机系统能执行的所有指令的集合。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。61.1算法（2）算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、NS结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。71.1算法3、算法设计基本方法（1）列举法：根据提出的问题，列举所有可能的情况，并用问题 中给定的条件检验哪 些 是需要的，哪 些是不需要的。（2）归纳法：通过列举少

4、量的特殊情况，经过分析，最后找出一般的关系。（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4）递归：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决当最后那些最简单的总是后，再沿着原来分解的逆过程逐步进行综合，（5）减半递推技术：所谓“减半”，是指将问题材的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。（6）回溯法：通过对问题的分析，找出一个解决总是的线索，然后沿着这个线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。81.1算法1.1.2算法的复杂度算法

5、复杂度：算法时间复杂和算法空间复杂度。1.算法的时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。91.1算法(1)平均性态： 是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义：(2)最坏情况复杂性：是指在规模为n时，算法所执行的基本运算的最大次数。101.1算法2.算法空间复杂度算法空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。111.2数据结构的基本概念 数据结构研究的三个方面：（1）数据集合

6、中和数元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 讨论以上问题的主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。121.2.1什么是数据结构数据结构是指相互有关联的数据元素的集合。1、数据的逻辑结构数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。132、数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

7、 数据的存储结构有顺序、链接、索引等。141.2.3 线性结构与非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度、一般讲数据结构分为两大类型：线性结构与非线性结构 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。栈、队列、串都是线性结构。非线性结构：不满足线性结构条件的数据结构。数组、广义表、数和图都是非线性结构15线性表线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i

8、-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。16顺序表的基础要点1、线性表是具有n个数据元素的有限序列。2、线性表的顺序存储结构具有三个弱点：在插入和删除时，需移动大量元素由于难以估计，必须预先分配较大的空间表的容量难以扩充 (如何解决？）3、顺序存储结构通过元素的相对存储地址来表示元素之间的关系4、线性表顺序存储的优点是可随机存取元素。5、顺序表中逻辑上相邻的元素的物理位置必定紧邻。 6、顺序表是一种随机存取的存储结构。7、在顺序表中插入或删除一个元素时，需要平均移动表的一半元素，具有移动的元素个数与该元素的位置有关。8、在长度为n的顺序表中插入一个元素的时间复杂

9、度为O(n)，删除一个元素的时间复杂度为O(n)。171.3 栈栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示： 进行插入和删除的表尾端是浮动端，通常被称为栈顶， an 为栈顶元素， 并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底， a1 为栈底元素。经常将栈用下图的形式描述：a1, a2, a3, ., an 插入和删除端18结论：后进先出（Last In First Out），简称为LIFO线性表。 举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面

10、的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。19栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化201.如果进栈序列为A,B,C,D,则可能的出栈序列是（）A.)C,A,D,B B)B,D,C,A C) C,D,A,B D)任意顺序2.栈中允许插入和删除的一端叫做【栈顶】3.关于栈的描述，正确的是A.在栈中只能插入元素B.在栈中只能删除元素C.只能在一端插入或删除元素D.只能在一端插入元素，在另一端删除元素。21BADCABDCA221.4 队列及其基

11、本运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。23下图是队列的示意图： a1a2an 插入端和删除端都是浮动的。通常我们将插入端称为队尾，

12、用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。 结论：先进先出（First In First Out），简称为FIFO线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 出队入队241.5.1 线性链表的基本概念线性表顺序存储结构的特点它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充

13、分的利用；线性表的容量难以扩充。1.5 线性链表25 线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构： datalink指针域，用来存放结点的直接后继的地址数据域，用来存放结点的值26例如 ：线性表 （a, b,c,d)27 术语表示每个数据元素的两部分信息组合在一起被称为结

14、点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。 headd cba单链表结构示意图datalink28其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：Head=NULL或0称为空表带头结点的单链表结构示意图head空表headd cba29

15、链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。30循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-link=NULL循环链表p或p-link=Hhh空表31双向链表（double linked lis

16、t）单链表具有单向性的缺点L空双向循环链表：非空双向循环链表：LABbcapp-prior-next= p= p-next-proir;32数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。33栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈

17、元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。34 top3516 树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数

18、称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。36(C)是有13个结点的树，其中A是根37结点： 数据元素的内容及其指向其子树根的分支统称为结点。结点的度 （Degree): 结点的分支数，即结点拥有的子树数。终端结点（叶子leaf）: 度为0的结点。非终端结点: 度不为0的结点。结点的层次: 树中根结点的层次为1，根结点子树的根为第2 层，以此类推。树的度: 树中所有结点度的最大值。树的深度: 树中所有结点层次的最大值。有序树、无序树: 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。术语381.6.2二叉数及其基本性质1. 定

19、义 定义：二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。 二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。39G HD E FB CA第一层第二层40二叉树的5种形态：(a)(b)(c)(d)(e)(a)空树 (b)只有根结点的二叉树 (c) 右子树为空的二叉树 (d) 左子树为空的二叉树 (e) 左、右子树均非空的二叉树41 2二叉树的性质二叉树具有下列5个重要的性质。【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。 【性质2】 深度为K的二叉树最多有2K-1个

20、结点(K1）。【性质3】 对于任意一棵二叉树BT，如果度为0的结点（叶子）个数为n0，度为2的结点个数为n2，则n0=n2+142 8 9 10 11 12 13 14 154 5 6 72 3143满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层只缺少右边的若干结点。44 8 9 10 11 12 4 5 6 72 31 7 8 94 5 6 2 31一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。完全二叉树非完全二叉树45完全二叉树的特点： （1）叶子结点只可能在层次最大的两层上出现 （2）对任

21、意结点，若其右分支下的子孙的最大层次是l ，则其左分支下的子孙的最大层次必是l 或l+146【性质4】 具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1in），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；如果i 1其双亲结点的编号为 i/2。（2）如果2in，则结点i没有左孩子（结点i为叶子结点）；否则其左孩子结点的编号为2i。（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。47二叉

22、树的基本性质： （1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；（5）具有n个结点的完全二叉树的深度为log2n+1；48 （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)； 若2kn，则编号为k的结点的左子结

23、点编号为2k；否则该结点无左子结点（也无右子结点）； 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。491.6.4二叉树的遍历 遍历二叉树的过程中，一般先遍历左子树、再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历、后序遍历。50（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。51（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。下面是一棵

24、二叉树及其经过三种遍历得到的相应序列。52G HB CAD E F先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA5317 查找技术 1.7.1顺序查找顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。顺序查找的使用情况：（1）线性表为无序表；（2）表采用链式存储结构。541.7.2二分法查找二分法查找只适用

25、于顺序存储的有序表。对于长度为n的有序线性表，最坏情况只需比较log2n次。55假设查找表存放在数组a的a1an中，且升序，查找关键字值为k。 折半查找的主要步骤为： （1）置初始查找范围：low=1，high=n; （2）求查找范围中间项：mid=(low+high)/2 （3）将指定的关键字值k与中间项amid.key比较 若相等，查找成功，找到的数据元素为此时mid 指向的位置；56若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1; 若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;（4）重复步骤（2）、（3）直

26、到查找成功或查找范围空（lowhigh），即查找失败为止。（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。571.8排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1.8.1交换排序所谓交换类排序法是指借助数据元素之间的互相交换进行的排序的一种方法。581.冒泡排序冒泡排序是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序。冒泡排序法，需要比较的次数为n(n-1)/2； .快速排序59.8.2插入排序简单插入排序法最坏情况需要n(n-1)/2次比较； .希尔排序法最坏情况需要O(n1.5)次比较。60例

27、如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 61.选择类排序法（1）简单选择排序法最坏情况需要n(n-1)/2次比较；（2）堆排序法最坏情况需要O(nlog2n)次比较。62第2章 程序设计基础2.1 程序设计方法与风格如何形成良好的程序设计风格1、源程序文档化；符号化命令：命名应具

28、有一定的实际含义。程序注释：增加正确的注释，包括序言性注释和功能性注释。视觉组织：程序中添加一些空格、空行和缩进使程序结构一目了然 2、数据说明的方法；（次序规范化；变量安排有序化；使用注释）3、语句的结构；（结构应尽量简单） 4、输入和输出。632.2 结构化程序设计1.原则:自顶向下、逐步求精、模块化和限制使用goto语句。2.结构化程序的基本结构顺序结构、选择结构、循环结构642.3 面向对象方法面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。1.对象：用来表示客观世界中的任何实体，对象是实体的抽象。面向

29、对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。对象的基本特点：（1）标识惟一性；（2）分类性；（3）多态性；（4）封装性；（5）模块独立性好。652.类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。3.消息是一个实例与另一个实例之间传递的信息。消息的组成包括（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。4.继承：能够直接获得已有的性质和特征，而不必重复定义他们

30、。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。5.多态性：同样的消息被不同的对象接受时可导致完全不同的行动的现象66第3章 软件工程基础3.1 软件工程基本概念1.软件的概念：计算机软件是包括程序、数据及相关文档的完整集合。2.分类：软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。为了摆脱软件危机，提出软件工程的概念，软件危机主要体现在：成本、质量、生产率等问题 。3.软件工程：软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。673.2 软件生命周期1.概念：软件

31、产品从提出、实现、使用维护到停止使用退役的过程 。2.软件生命周期三个3个时期8个阶段:软件定义：问题定义、可行性研究和需求分析软件开发：概要设计、详细设计、实现和测试运行维护：运行维护阶段主要阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。软件生命周期各阶段的活动可以重复，执行时也可以有迭代。683.3 软件设计1.软件设计基本概念（1）按技术观点分：结构设计：定义软件各主要部件之间的关系数据设计：将分析时创建的模型转化为数据结构的定义接口设计：描述软件内部、软件和协作系统之间及软件与人之间如何通信。过程设计：把系统结构部

32、件转化为软件的过程性描述。（2）按工程管理角度分概要设计：将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式详细设计：确定每个模块的实现算法和局部数据结构。692.软件设计的基本原理（1）软件设计中应该遵循的基本原理和与软件设计有关的概念抽象：软件设计中考虑模块化解决方案时，可以定出多个抽象级别，抽象的层次从概要设计到详细设计逐步降低。模块化：将待开发的软件分解成若干小的简单的部分信息隐蔽：一个模块内包含的信息对于不需要这些信息的其他模块来说是不能访问的。模块独立性：每个模块只完成系统要求的独立的子功能。（2）衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准内聚：描述

33、模块内的功能联系耦合：模块间的互相连接的紧密程度的度量。优秀软件尽量做到高内聚，低耦合。703.4 结构化分析方法1.结构化分析方法的定义：使用数据流图（DFD）数据字典（DD）结构化英语、判定表、判定树的工具来建立一种新的、称为结构化规格说明的目标文档。结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析的常用工具（1）数据流图； （2）数据字典； （3）判定树； （4）判定表。71数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。数据字典：对所有与系统相关的数据元素

34、的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。判定树：从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。数据字典是结构化分析的核心。722.软件需求规格说明书的特点：（1）正确性；（2）无岐义性；（3）完整性；（4）可验证性；（5）一致性；（6）可理解性；（7）可追踪性。 73

35、3.5 软件测试1.软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。软件测试的目的：发现错误而执行程序的过程。软件测试方法：静态测试和动态测试。静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。白盒测试：在程序内部进行，主要用于完成软件内部CAO作的验证。主要方法有逻辑覆盖、基本基路径测试。黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方

36、法有等价类划分法、边界值分析法、错误推测法、因果图等。软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。743.6 程序的调试程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。75第四章 数据库设计基础41 数据库系统的基本概念数据：实际上就是描述事物的符号记录。数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合定型的值，如整型值15。数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库