计算机考级公共基础

1、1、算法的定义：算法:是指解题方案的准确而完整的描述。算法实际上是解决问题的有限运算序列。如：求圆的面积R=45S=pi()*r*r ?s 1.1 算法2、算法的基本特征可行性：对实际问题而设计的算法，执行后能够得到满意的结果。确定性：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。有穷性：算法必须在有限的时间内做完，即算法必须能执行有限个步骤后终止。拥有足够的情报：要使算法有效必须提供足够的情报。如使所编的程序能执行，算法中的运算要施加对象，所以这些对象的输入或定义，直接影响到运算的结果。如：对变量进行初始化，s=0;i=1;s=s+i;(1)算法中对数据的运算和操作算

2、术、逻辑、关系、数据传输（主要包括赋值、输入、输出）(2)算法控制结构：算法中各操作之间的执行顺序称为算法的控制结构。一个算法是由顺序、选择和循环三种结构组合而成。3、算法的基本要素（两个）传统流程图 N-S图AB成立成立不成立不成立条件条件P条件条件语句序列语句序列1语句序列语句序列2ENDIF后面的语句后面的语句真真假假4、算法的设计基本方法：(1)例举法基本的算法，特点比较简单，例举所有可能情况，工作量大。是计算机算法中最基础的算法，例如：路径的查找、搜索。(2)归纳法：从简单的特殊情况，最后总结出一般性的关系。如求水仙花数100999的水仙花数，以153为例(3)递推：是从已知的条件出

3、发，逐次推出要求的各种中间结果和最后结果。(4)递归：将问题逐层分解，最后归结为一些最简单的问题。递归分为直接递归和间接递归，如图：F函数或过程 f1函数或过程 f2函数 调用调用f f函数函数调用调用F2F2函数函数调用调用f1 f1函数函数自己调用自己自己调用自己间接调用间接调用(5)减半递推技术：将问题的规模减半，而问题的性质不变，递推重复减半的过程。(6)回溯法：在工程中很难归纳出简单的递推公式或求解的步骤，也不能无限的举例，这时就用一种有效的方法是“试”，找到求该问题的线索去探索，若试探成功，就得到问题的解，若失败，就逐步回退，换别的线索在逐步试探。12+（）=45如编写下棋游戏的程

4、序aa总结算法：1 1、算法的基本概念、算法的基本概念2 2、算法的特征（、算法的特征（4 4个）个）3 3、算法的两个基本要素、算法的两个基本要素4 4、算法设计的基本方法、算法设计的基本方法1.2 算法的复杂度包括以下内容 算法时间的复杂度 算法空间的复杂度1、算法时间的复杂度算法的时间复杂度，是指执行算法所需的计算工作量（基本的运算次数）。表示为：f(n)2、算法的空间复杂度算法的空间复杂度是指执行这个算法所需的内存空间（存储空间）。注意：不是执行算法程序所需的内存空间。因为算法所占空间包括算法程序所占空间、输入数据算占空间和算法执行过程中所需额外空间（临时数据)3、算法分析：是指对一个

5、算法的运行时间和占用空间做定量分析。算法分析的主要目的：降低时间复杂度（运算次数）和空间复杂度（占用存储空间），提高算法的执行效率。 （1）数据结构包括以下三方面内容(三要素)：p7w数据的逻辑结构 (前后件关系)w数据的存储结构(顺序、链式、索引)w对各种数据结构进行的运算(插入、删除、查找、更改)(2)、数据结构操作(运算)p8例1.3p8无序表的顺序查找和有序表的对分查找如图：p8 图1-1所示无序表只能用顺序查找，查找次数最多n次。有序表可以用顺序查找也可以用对分查找，对分查找效率高。（3）定义：数据结构是相互关联的数据元素的集合。 即数据的组织形式。P10家庭：父亲、儿子、女儿特点：

6、与计算机的硬件无关。数据的逻辑结构包括：数据元素之间的前后件关系即逻辑关系，数据之间的逻辑关系称逻辑结构。一个数据逻辑结构有两个要素：数据元素的集合，记为D（DATE)；数据之间的前后件关系，记为R(RELATION)。一个数据结构可表示为：B=(D,R)3、 数据的逻辑结构P11例题p12例1.6家庭成员的数据结构可以表示成：B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子），（父亲，女儿）其中D表示数据的集合，R表示数据间的前后件关系，父亲是儿子的前件，儿子是父亲的后件。 4、数据存储结构P12(物理结构）w数据的数据的逻辑结构逻辑结构在计算机存储空间中的存放形式在计算机存储空间中的存放

7、形式(或在计算机中的表示）或在计算机中的表示）p13（存放元素信息和前（存放元素信息和前后件关系信息），后件关系信息），可以与逻辑顺序不同。可以与逻辑顺序不同。w数据结构的图形表示：数据结构的图形表示：D=d1,d2,d3,d4,d5,d6,d7 R=d1,d3,d1,d7,d2,d4, d3,d6,d4,d5d1d3d7d6d2d4d5父亲儿子女儿4、数据存储结构P14数据结构的几个概念例1-8下面：w根结点：没有前件的结点；如图：d1,d2w终端结点（叶子结点）：没有后件的结点。如图：d7和d6,d5内部结点：其他结点。d3,d4d1d3d7d6d2d4d5 按照数据结构中各数据元素之间的

8、前后件关系的复杂程度，一般数据结构分为两类：线性结构( (又称线性表) )：a.a.数据结构非空。b.b.只有一个根结点。c. c.每个结点最多有一个前件，最多有一后件。d.d.插入和删除一个结点后仍满足此条件。非线性结构：不是线性结构。1.2.3 分清线性结构和非线性结构P14d1d3d7d6结点结点根结点1.3、 线性表及顺序存储结构p16线性表( (一组数据元素构成) )的特征：有且只有一个根结点，无前件；有且只有一个终端结点，无后件除根结点和终端结点外，其他结点只有一个前件，也只有一个后件。线性表中结点个数为线性表的长度。如长度为n n的线性表: :其表示为：( (a1,a2,a1,a

9、2,.,an).,an)，n n为0 0空表d2d4d5线性表的顺序存储结构：w线性表中的所有元素占有的连续的存储空间。w线 性 表 中 的 所 有 元 素 在 存 储 空 间 按 逻 辑 次 序 存 放 。 即 逻 辑 相 邻 ， 物 理 上 相 邻 。D=2,4,6,1,3w线性表顺序存储结构的特点：数据的物理地址和逻辑地址相同且连续。一个长度为5的线性表的顺序存储:246 131001 1002 1003 1004 1005内存状态内存状态 。 。a1存储地址a2anADR(a1)ADR(a1)+kaiADR (ai)+(i-1)kADR(ai)+(n-1)k线性表顺序存储结构示意图：线

10、性表顺序存储结构示意图：程序设计语言中，定义一维数组来表示线性程序设计语言中，定义一维数组来表示线性表的顺序存储空间。表的顺序存储空间。插入运算：向后移动数据元素。如在第i个元素之前插入，则从第i个元素及以后所有元素都要后移。P18图1.7删除运算：向前移动数据元素。如删除第i个元素，则从第i+1个元素开始及以后所有元素都要前移。(3)顺序表的运算p17顺序存储结构下的插入元素的操作2918566335243147298718566335243147298718566335243114471234567891087123456789101412345678910顺序存储结构下的删除元素的操作8

11、72918566335243147871856633524314787185663352447123456789删除删除29后的线性表后的线性表删除删除31后的线性表后的线性表长度为长度为8的线性表的线性表1234567891234567891.4 栈和队列(线性结构）p191 1、栈的特征栈的特征：是一种特殊的：是一种特殊的线性表线性表。插入。插入和删除只能在一端进行，此端称为和删除只能在一端进行，此端称为栈顶栈顶。另一端封闭另一端封闭, ,不能执行任何操作，称为不能执行任何操作，称为栈底栈底。topbottoma0an-1进栈出栈运算规则：运算规则：先进后出，先进后出，后进先出。后进先出。

12、栈支持栈支持子程序子程序的调用的调用入栈：是指在栈顶位置插入一个新元素。Top栈顶指针+1，再将新元素插入到top指针指定位置,当栈顶指针指向最后一个存储位置时，说明栈满，发生上溢错误。2、栈的运算p21Top=0Top+1bottomAbottomtop A B C D E F G栈空正常栈满B（2）、退栈定义：退栈是指取出栈顶元素定义：退栈是指取出栈顶元素赋给赋给一个指一个指定的变量，定的变量，该元素在栈中不存在。该元素在栈中不存在。top-1,栈顶指针为栈顶指针为0时，说明栈空，发生下溢错时，说明栈空，发生下溢错误。误。topbottom-1 G B Btop读栈顶元素是将栈顶元素赋给一

13、个指定的变量。其特点：该运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时,说明栈空，读不到栈顶元素。(3)、读栈顶元素1、队列是一种特殊的线性表，只允许在一端插入，另一端删除，允许插入的一端称队尾，允许删除的一端称队头。运算规则：先进先出，或后进后出1.5队列特征p21出队出队入队入队队尾队尾rear队头队头frontFEDCBA排头指针指向头元素的前排头指针指向头元素的前一个位置一个位置队列运算示意图一个队列一个队列fontrearfontrear A C DBBDCBEDC删除一个元删除一个元素后的队列素后的队列插入元素插入元素E E后的后的队列队列font

14、rear队头队尾在实际应用中常采用循环队列方式。定义：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环绕空间。如图：2、循环队列及其运算p22Rearfrontm21循环队列的循环队列的队头队尾均队头队尾均相等相等Front=rear=m初状态初状态为空为空两种运算：入队:在循环队列的队尾加入一个新元素。Rear=rear+1,当循环队列已满称为上溢。退队:在循环队列的队头位置退出一个元素并赋给一个变量front=front+1。当循环队列为空时称为下溢2、循环队列及其运算p233、栈和队列的异同w相同点：都是特殊的线性表，都可以在端点处进行插入和删除运算。w区别：栈只允许在表的一端

15、进行插入和删除操作，是一种“后进先出”的线性表。而队列允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出,后进后出”的线性表。FEDCBA（1 1）线性表顺序存储的缺点）线性表顺序存储的缺点在删除和插入元素时需要移动大量的数据元素。在删除和插入元素时需要移动大量的数据元素。顺序结构的线性表的存储空间不易扩充。上溢顺序结构的线性表的存储空间不易扩充。上溢错误。错误。线性表的顺序存储不便对存储空间的动态分配。线性表的顺序存储不便对存储空间的动态分配。线性链表p25（2 2）线性链表线性链表：线性表：线性表 的的链式存储结构链式存储结构，（3 3）每个存储结点有两部分组成：）每个存储

16、结点有两部分组成：数据域数据域：存放数据元素的值：存放数据元素的值指针域指针域：表示前后件关系表示前后件关系指向后件的结点。指向后件的结点。最后元素无后件，最后元素无后件，0,0,nullnull数据数据 存储结点地址存储结点地址数据域数据域 指针域指针域d4 d5N nullhead举例p26p26如图1.181.18例题总结：线性链表的存储结构在逻辑上相邻，物理上并不一定相邻。指向线性链表的第一个结点的指针为头指针。Head,当head=null或0时，称为空表。栈和队列都可以采用链式存储结构。1.5.3循环链表p30线性单链表不能对空表和第一个结点的处理必须单独考虑，使空表和非空表运算不

17、统一，若要统一，采用循环链表结构。特点：w循环链表增加一个表头结点，其数据域为任意，指针域指向线性表的第一个结点。循环链表的头指针head指向表头结点。w循环链表中最后一个结点的指针域不是空，而是指向表头结点。一个长度为n的循环链表其结点数为：n+11、树的特征：非线性数据结构，具有层次关系。1.6树与二叉树p31ABCDEF2、几个概念：P32(1)根结点：没有前件，只有一个，称为根。如：A是根节点。(2)子结点：每个结点可以有多个后件。如C是子结点(3)叶子结点:没有后件结点。如：B,E,F,D(4)度：一个结点所拥有的后件个数。如：A:3,B,E,D,F:0,C:2ABCDEF2、几个概

18、念：(5)(5)树的度树的度：所有结所有结点的最大的度。如点的最大的度。如本树的度为：本树的度为：3 3(6)(6)树的深度树的深度：树的树的最大层次称为树的最大层次称为树的深度。本树层次为深度。本树层次为3 3层。层。ABCDEF树树（1）二叉树的特征p34：是一种很有用的非线性结构，只有一个根结点，每个结点最多有两棵子树，称为左子树，右子树。所有子树也均为二叉树。3、二叉树和性质p34ABCDEF二叉树二叉树 在k层上最多有2(k-1)次方个结点。 (2)、二叉树的性质ABCDEF如图：树的深度：如图：树的深度：3 3第三层由：第三层由：2 2(3-1)(3-1)=4=4个结个结点。点。树

19、的度为：树的度为：2 2( (1,21,21 1,2,22 2,8,16,8,16.2.2(K-1)(K-1) ) )(2)、二叉树的性质深度为m的二叉树，最多为2m-1次方个结点。ABCDEF如：深度为如：深度为3层，则最层，则最多有多有23-1=7个结点。个结点。20+2+4+8+2(m-1) =(A1-a1*qm)/(1-q)= 2m-1(2)、二叉树的性质度为0的结点（叶子结点）总比度为2的结点多一个。如图：叶子结点总比具有两个后件的结点多一个。度为0的结点：4个度为2的结点：3个ABCDEFG举例1、深度为5 的二叉树至多有多少结点？A.16 B.32 C.31 D.1025-1=3

20、12、对一个满二叉树，m个树叶，n个结点,深度为h,则（）A.n=h+m B.h+m=2n C.m=h-1 D.n= 2h-1(2)、二叉树的性质p35 具有n个结点的二叉树，其深度（层数）至少为log2n+1(其中log2n表示log2n的整数部分） 如图：有4个结点 深度至少：log24+1=4层ABCD(3)满二叉树和完全二叉树p35满二叉树是指除最后一层外每一层上所有结点都有两个子结点的二叉树。ABCDEFG完全二叉树w完全二叉树是指除最后一层外每一层上结点数均达到最大值；在最后一层上只缺少右边的若干结点。ABCDEF完全二叉树w特点：一个完全二叉树共有N个(偶数)结点，那么这个完全二

21、叉树的叶子结点数是N/2。ABCDEFABCD满二叉树也满二叉树也是完全二叉是完全二叉树，而完全树，而完全二叉树一般二叉树一般不是满二叉不是满二叉树。树。p36p36（3）二叉树的存储结构和二叉树的遍历采用链式存储结构，有两个部分组成：数据域和指针域(左指针域右指针域)p36下面二叉树遍历P38：以根节点为基准，指不重复的访问二叉树的所有结点。w前序遍历（DLR访问二叉树）：访问根结点、前序遍历左子树与前序遍历右子树。如图：前序为：ABDECFABCDEFABCDEF中序遍历LDR： 首先访问中序左子树，再访问根结点，最后中序遍历右子树。如图：中序遍历：DBEAFC后序遍历LRD：后序左子树、

22、后序右子树、根结点如图：后序遍历：DEBFCA（3）二叉树的遍历）二叉树的遍历遍历举例1、如图二叉树，其中序遍历的结果为（ ）A.abcdef B.abdefc C.dbefac D.defbcaabcdef前序遍历：前序遍历：abdefc后序遍历：后序遍历：dfebca遍历举例 一棵二叉树的前序遍历序列为abgdcfk,中序遍历序列为gbdafck,则结点的后序遍历序列是：( gdbfkca） 由前序遍历可以知道根结点是a,所以在中序遍历中dgb为左子树，fck右子树。 后序遍历是LRD 最后一结点是根结点。 是aabcgdfk1.7查找技术p39(1)顺序查找：逐个查找，无排序要求，若线性

23、表为无序表，则不管是顺序存储还是链式存储只能采用顺序查找，最多比较n次。若是有序的线性表，如果采用链式存储结构(各元素逻辑相邻，物理上不一定相邻)，也只能顺序查找。若有序的顺序存储结构即可以顺序查找也可以二分查找. 。p7图1.1123456X=671.7查找技术二分查找：折半查找，事先排序，只能对顺序存储的有序线性表，次数最多是log2n , p7图1.1。例如：顺序表(3,6,8,10,12,15,16,18,21,25,30 )中，用二分查找关键码值11，所需要的关键码比较次数为（ ） 。比较的次数为4例题有序表(1,3,9,12,32,41,45,62,75,77,82,95,100

24、)中，用二分查找关键码值82,所需要的关键码比较次数为（ ） 比较的次数为4定义：把无序序列整理成按值递减或递增的顺序排列。5 1 7 2 8（1）交换类排序：冒泡排序法：相邻数据元素交换实现排序，最多比较次数为n*(n-1)/2，最少比较次数:n-11+2+3+4+.+(n-1)=(1+n-1)*(n-1)/2,排序效率最低。5 1 1 1 1 1 1 11 5 5 5 5 2 2 27 7 7 2 2 5 5 62 2 2 7 7 7 7 78 8 8 8 8 8 8 81.8排序技术p40快速排序法w定义：按某个元素值分成两部分定义：按某个元素值分成两部分。效率比冒效率比冒泡排序效率要高

25、。泡排序效率要高。1 5 7 6 81 5 7 6 8思想：从线性表中取一个元素如思想：从线性表中取一个元素如7 7进行交换比进行交换比较，小于较，小于7 7的移到前面，大于的移到后面。的移到前面，大于的移到后面。 1 5 6 1 5 6 T T（7 7） 8 8 1 T(5) 6 7 8 1 T(5) 6 7 81 T(1) 5 6 7 81 T(1) 5 6 7 8例题一组记录关键码(46,79,56,38,40,84),则利用快速排序方法，以第一个记录为基准得到的一次划分结果为:以46(T)为基准,把46后面的数据，大于46的数据放到46的后面，小于46的数据按原来顺序放到46前面。第一

26、次划分完成。38，40，46，79，56，84（2）插入类排序：p42简单插入排序法：插入到一个排好的序列中。比较次数为：n*(n-1)/2，如图1-38所示。51732,有序表：515第二个元素第二个元素1 1放入中间变量放入中间变量T T中中, ,T T与与5 5比较，若小，则插入比较，若小，则插入到到5 5的前面，若大插入到的前面，若大插入到5 5的后面。则下图：的后面。则下图：用用T=7T=7与与5 5比较比较, ,若若T5T5插入到插入到5 5的后面，的后面，T T再与再与1 1比较若大比较若大插入插入1 1后面，若小插入后面，若小插入1 1前面，比较两次，前面，比较两次，1+2+1

27、+2+.+(.+(n-1)n-1)（2）插入类排序希尔排序法：将整个无序序列分割成若干小的子序列分别进行插入排序。最多比较次数为O(n 1.5)N排序序列长度，增量：h=n/2kK=1,2,.,log2n(2k=n)P36 图1.39插入类排序效率最高（3）选择类排序：p44简单选择排序：选择一个最大（最小）的数放在前面，以此类推，直到表为空，最多比较次数为n*(n-1)/2。如图1.405 1 7 6 8 ，4+3+2+1 堆排序：堆顶元素必为最大项。比较次数为O(n*log2n)。各种排序方式的效率高低插入类排序选择类排序快速排序冒泡排序冒泡排序最多比较次数：n*(n-1)/2简单插入类排

28、序：n*(n-1)/2简单选择排序：n*(n-1)/2希尔排序：O(n 1.5)堆排序：比较次数为O(n*log2n)，比较次数最少。程序设计经历的阶段：程序设计主要经历了结构化程序设计和面向对象的程序设计。1、良好的编程风格应注意的因素：w源程序的文档化:符号名的命名,程序注释(包括序言性注释和功能性注释),视觉组织(程序中加空格、空行、缩进)。程序容易理解2.1 2.1 程序设计的方法和风格程序设计的方法和风格1、良好的编程风格应注意的因素：w数据说明的方法：数据说明次序的规范化，变量安排有序化，使用注释来说明复杂数据结构。易于理解和维护main() int n,m, p , r, t；

29、printf (请输入两个正整数n, m:); scanf (%d,%d,&n,&m); if(n500500金额金额=500500未未过期过期500已已过期过期=500未过期未过期=500已已过期过期发出批准单发出批准单发出提货单发出提货单发出通知单发出通知单 三、软件需求规格说明书1、作用：w便于用户、开发人员进行理解和交流。w反映出用户问题的结构，可以作为软件开发工作的基础和依据。w作为确认测试和验收的依据。2、内容包括：概述、数据描述、数据流图、数据字典、功能描述、性能描述；参考文献目录；附录。3.3 结构化设计方法软件工程的第一个要素：软件工程的第一个要素：方法中的第

30、二种方法。方法中的第二种方法。一、软件设计的基本概念1、软件设计：是把一个软件需求转换为软件表示的过程。2、软件设计的基本目标：软件设计确定系统的目标3、从工程管理角度来看：软件设计分两步w软件设计包括概要设计（结构设计）：进行系统级设计，将软件需求转化为软件体系结构。w 详细设计：进行模块局部设计软件开发过程中，概要设计是描述软件的体系结构。二、软件设计的基本原理1、软件设计的规则：抽象化、模块化、信息隐蔽、模块独立性。衡量模块独立性的两个标准：耦合性和内聚性。要求高内聚，低耦合内聚性：模块内各元素间的彼此结合的紧密程度。由弱到强。越强越好。偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、

31、顺序内聚、功能内聚。二、软件设计的基本原理耦合性：是模块间的互相连接的紧密程度的度量。特点：由高到低排列。分类：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合。要求高内聚，低耦合三、概要设计p751、概要设计的任务：w设计软件系统结构，划分模块和模块的层次结构。w数据结构及数据库设计w编写概要设计文档。(概要设计说明书、数据库设计说明书、集成测试计划)w概要设计文档评审。三、概要设计p76常见软件设计的工具：1）结构化设计图：p76由模块、数据信息、控制信息组成。常使用的结构图有四种模块类型：分传入模块、传出模块、变换模块、协调模块。2、面向数据流设计方法：数据流类型：

32、变换型、事务型。P77-78传入数据 变换数据 传出数据2、详细设计p80w主要任务：为软件结构图中的每一个模块确定其算法和局部数据结构。w常用的软件过程设计工具：P69图形工具：程序流程图、N-S图、PAD图、HIPO图、PDL图。表格工具：判定表语言工具：PDLAB图形工具（1）程序流程图控制流控制流加工步骤加工步骤逻辑条件逻辑条件优点：简单优点：简单易学易学缺点：随意缺点：随意调动，违反调动，违反程序设计原程序设计原则，不易表则，不易表示数据结构示数据结构（2）N-S图p82为了避免流程图再描述程序逻辑时的随意性与灵活性，提出了N-S图，是用方框图来代替传统的程序流程图。AB成立成立不成

33、立不成立条件条件P语句组语句组1ENDIF后面的语句后面的语句条件条件真真假假(3)PAD图(问题分析图)p83ABAB条件条件PADPAD图的特点：图的特点：结构清晰、结构化程度高、易于阅读、程结构清晰、结构化程度高、易于阅读、程序执行从最左边的主干线端点开始，序执行从最左边的主干线端点开始，自上自上而下、自左而右依次执行。而下、自左而右依次执行。（4）PDLPDL过程设计语言也称结构化的英语 或伪代码。用PDL语言表示控制结构：条件：IF/THEN/ELSE/ENDIF循环：DO WHILE/ENDDO可要注意听课啊！3.4软件的测试P851）软件测试是为了发现错误而执行程序的过程，是保证

34、软件质量的重要手段。软件测试目的：发现错误。2、软件测试方法分类p86(1)若从是否需要执行被测软件的角度分：静态测试：代码检查、静态结构分析、代码质量度量。不需要运行程序，主要通过人工进行。动态测试：基于计算机测试，用测试用例去运行程序，发现错误。设计高效、合理的测试用例是动态测试的关键。测试用例的组成：(输入值集),(输出值集)(2)动态的白盒和黑盒测试方法 ：p86白盒测试：w把测试的对象看成是一个透明的盒子，它允许测试人员利用程序内部的逻辑结构或有关信息，设计和选择测试用例，对程序的所有逻辑路径进行测试。w因此白盒测试又称结构测试或逻辑驱动测试。w白盒测试主要方法有：逻辑覆盖、基本路径

35、测试。白盒测试：白盒测试的主要原则：w保证所测模块中的每一独立路径至少执行一次；w保证所测模块所有判断的每一分支至少执行一次。w保证所测模块每一循环都在边界条件和一般条件下至少执行一次；w验证所有内部数据结构的有效性。黑盒测试p90黑盒测试：也称功能测试或数据驱动测试，对软件已经实现的功能测试。黑盒测试特点：不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查是否符合即可。黑盒测试方法：等价划分法、边界值分析法、错误推测法等。3、软件测试的实施过程p93-96测试过程按4个步骤：单元测试：发现各模块内可能存在的错误。集成测试：测试和组装软件过程，发现与接口有关的错误。确认测

36、试：验证软件功能和性能是否满足要求。系统测试：在系统环境下验证软件是否与系统正确连接。3.5程序的调试P96在程序测试完后进行程序调试。任务：诊断与改正程序中的错误，开发阶段。步骤：错误定位、修改设计代码，排除错误、进行回归测试，防止新的错误。方法：强行排错法（设置断点和监视表达式，使用多，效率低），回溯法(小规模程序排错)、原因排除法（例举所有出错原因进行排错）。4.1数据库系统的基本概念p1001、数据：描述事物的符号记录。计算机中数据分两部分：w存放在计算机内存中的临时性数据w对系统起着长期持久作用的永久性数据。（数据库系统中处理的数据）w软件中的数据是有结构的，数据有型(Type)和值

37、(Value)。4.1数据库系统的基本概念2、数据库数据库的英文缩写：DB数据库的特点：集成和共享3、数据库管理系统：缩写：DBMS它是数据库系统的核心。具有以下功能：数据模式的定义、数据存取的物理构件、数据操纵、数据的完整性、安全性定义和检查、数据的并发控制和故障恢复、数据服务。4.1数据库系统的基本概念为了完成以上功能，DBMS提供了相应的语言：数据定义语言：DDL数据操作语言：DML数据控制语言：DCL以上语言使用方式：w交互式命令语言w宿主型语言(嵌入到高级语言中)4.1数据库系统的基本概念4、数据库管理员：DBA主要的工作：数据库设计、数据库维护、改善系统功能，提高系统效率。5、数据

38、库系统 DBS数据库系统的组成：数据库、数据库管理系统、数据库管理员、系统平台（计算机软硬件）6、数据库应用系统：DBAS数据库系统、应用软件、应用界面。4.2数据库系统的发展p105w人工管理阶段，文件管理阶段、数据库系统阶段（层次数据库和网状数据库系统阶段、关系数据库系统阶段）。如表4.1数据库管理三个阶段的比较P1064.3数据库系统的基本特点：p107数据的集成性、数据的共享性和低冗余性、数据的独立性，数据的统一管理和控制。数据库的安全性：数据的完整性检查、数据的安全保护性、并发控制、数据的恢复。4.4数据库系统的内部结构体系p108数据库系统在其内部具有三级模式及二级映射。有利于保证

39、数据库的独立性。1、三级模式：概念模式：是数据库系统中全部数据逻辑结构的描述，是全体用户公共数据视图。概念模式主要描述数据的记录类型以及他们间的关系，数据间的语义约束，用DBMS的DDL语言定义。4.4数据库系统的内部结构体系(2)外模式：(子模式或用户模式)它是用户的数据视图。是用户所见到的数据模式。由概念模式推出。(例如我们用查询设计器检索表或视图中的内容，所得到的结果)(3)内模式：物理模式，给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引存取方法和路径。p108如图： 4-3内模式最底层、概念模式处于中层、外模式最外层。4.2数据模型p109一、数据模型的基本概念1、数据模型描述的内容有三个部分：数据结构、数据操作与数据约束。2、数据模型按照不同应用层次分为：概念数据模型、逻辑数据模型、物理数据模型。3、其中逻辑数据模型种类：层次、网状模型、关系模型、面向对象等。概念模型：E-R模型。（实体联系模型）4.2数据模型p110二、E-R模型（实体联系模