全国计算机培训第一课讲义

1、全国计算机二级考试C语言基础知识讲义第一部分 数据结构第一章 算法和数据结构 一、算法概述 1.算法概念：一系列解决问题的清晰的指令 2.算法基本特征：有穷性（步骤有限）、确定性（动作明确）、可行性（动作可行）。 3.算法基本要素：（1）对数据的运算和操作：算术运算加、减、乘、除等 逻辑运算与、或、非 关系运算大于、小于、等于、不等于 数据传输赋值、输入、输出（2）控制结构：各操作之间的执行顺序顺序、选择、循环4.算法设计基本方法：递推法、递归法、穷举搜索法、贪婪发、分治法、动态规划法、迭代法5.良好算法的设计要求：正确性、可读性、健壮性、高效率、低存储6.算法的复杂度（考点） 时间复杂度：执

2、行算法所需要的计算工作量，即基本运算次数 空间复杂度：执行算法所需要的内存空间 注：同一个算法用不同语言实现，或用不同编译程序编译，或在不同计算机上运行，效率不同。 一个算法所占用的存储空间包括算法程序所占存储空间、输入的初始数据所占存储空间和算法执行过程中所需要的额外空间。二、数据结构概述1.相关概念 数据：描述客观事物的数字、字符以及所有能够输入到计算机中并被计算机处理的信息的总称。表示形式除了数字、字符之外，还可以是英文、汉字或其他语种字母组成的词组、语句、以及表示图形、图象和声音等。数据元素：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素除了可以是一个数字或一个字符

3、串以外，它也可以由一个或多个数据项 （数据项：有独立含义的数据的最小单位，有时也称为字段） 组成。【例 1.1】如图1-1中每个学生的学籍信息作为一个数据元素，在表中占一行。每个数据元素由序号、学号、姓名、性别、英语成绩等7个数据项组成。图1-1学籍表数据对象：具有相同性质的数据元素的集合，是数据的一个子集。图1-1中的整个学籍表可以看成一个数据对象。数据的逻辑结构：数据元素间的逻辑上的联系，是对数据元素之间的逻辑关系的描述。如：线性结构（学籍表）、树结构（家族谱系）、图结构（交通或通信网问题）。数据逻辑结构根据其前后件关系的复杂程度分为线性结构和非线性结构两类。 线性结构：有且只有一个根结点

4、、每个结点最多只有一个前件，最多只有一个后件。非线性结构：不是线性结构，即为非线性结构。特点：逻辑结构体现数据元素间的抽象化相互联系，并不涉及数据元素在计算机中具体的存储方式，是独立于算机的。 数据的存储结构(物理结构)：数据的逻辑结构在计算机存储器里的实现，又称物理结构。数据的存储结构依赖于计算机。 数据的存储结构可用以下四种基本存储方法得到：(1) 顺序存储法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 顺序存储法主要应用于线性的数据结构（如图1-2）。非线性的数据结构也可

5、通过某种线性化的方法实现顺序存储。图1-2顺序存储注：顺序存储的地址是连续的，逻辑结构与物理结构相吻合。(2) 链接存储法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述（如图1-3）。两种表示形式如下：李四张三张三二元关系：若用D表示数据元素的集合，R表示数据元素之间的前后件关系，则一个数据结构可以表示为B=（D，R）。 图形表示：数据结点或结点 数据元素前后件关系单链表 二叉列表 图1-3 链接存储注：数据结构中，没有前件的结点称为根结点、没有后件的结点称为终端结点。(3)索引存储法

6、：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。(4)散列存储法：该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 小结：四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 总结：同一逻辑

7、结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。第二章 线性表一、线性表 1.线性表的定义：一个含有n(n0)个结点的有限序列，该结点集合中有且仅有一个开始结点（只有一个后继，没有前驱）和一个终端结点（只有一个前驱，没有后继），其余结点均有一个前驱和一个后继。 2.线性表的顺序存储：用一组连续的存储单元依次存储线性表的数据元素。当线性表以顺序存储的方式存储时又叫做顺序表。 顺序表的基本特征：（1） 线性表中的所有元素所占用的存储空间是连续的（2） 线性表中的所有元素存储顺序是按逻辑顺序依次存放的 顺序表可执

8、行的基本操作：（1）插入：在顺序表中指定位置插入一个新的元素（2）删除：在顺序表中删除指定的元素（3）查找：在顺序表中查找某个特定元素（4）排序：对顺序表中的元素进行排序3.线性表的链接存储3.1单链表1.单链表的定义：单链表是一种链式存储的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。单链表的逻辑结构如图2-1所示。表示空表的单链表只有一个单元，即表头单元head，其中的指针是空指针null。单链表是链式存取的结构，为

9、找第 i 个数据元素，必须先找到第 i-1 个数据元素。图2-1 单链表2.单链表的类定义typedef int ElemType;/假设结点的数据类型为整型struct NodeType/结点类型定义 ElemType data; /结点的数据域 NodeType *next;/结点的指针域;建立单链表的过程是一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表，其时间复杂度为O(n)。 3.单链表的插入(1)插入操作的三种情况：在已知P指针所指向的结点后插入一个元素x。在p指针所指向的结点前插入一个元素x。在线性表中值为y的元素插入一个值为x的数据元素。(2

10、)操作目标：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。 (3)插入步骤： 找到ai-1存储位置p 生成一个数据域为x的新结点*s 令结点*p的指针域指向新结点 新结点的指针域指向结点ai。 (4)插入操作代码实现在已知P指针所指向的结点后插入一个元素x。 s=new NodeType; s-data=x; s-next=p-next; p-next=s;在p指针所指向的结点前插入一个元素x。q=head;while(q-next!=p)q=q-next;s=new NodeType;s-data=x;s-next=p-next;q-next=s; 在线

11、性表中值为y的元素插入一个值为x的数据元素。q=head; p=q-next;while(p!=NULL)&(p-data!=X)q=p; p=p-next;s=new NodeType;s-data=x;s-next=p-next;q-next=s; 4.单链表的删除(1)删除操作的三种情况：删除p所指向结点的后继结点（假设存在）删除p所指向的结点。删除线性表中值为x的数据元素。 (2)操作目标：删除运算是将表的第i个结点删去。(3)操作步骤： 找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中） 令p-next指向ai的直接后继结点（即把

12、ai从链上摘下） 释放结点ai的空间，将其归还给存储池。 (4)删除操作代码实现 删除p所指向结点的后继结点（假设存在）q=p-next;p-next=q-next;delete q;删除p所指向的结点。q=headwhile(q-next!=p)q+;q-next=p-next;delete p;删除线性表中值为x的数据元素 q=head; p=q-next; while(p!=NULL)&(p-data!=x) q=p; p+; q-next=p-next; delete p;注：设单链表的长度为n，则删去第i个结点仅当1in时是合法的。 当i=n+1时，虽然被删结点不存在，但其前趋结点却

13、存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-next！=NULL）时，才能确定被删结点存在。3.2循环链表循环链表是另一种形式的链式存储结构，将单链表稍加改动，让表中最后一个结点的指针指向单链表的表头结点，这样就形成了一个环链表。图2-2 单循环链表1.单循环链表在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可（如图2-2）。判断空链表的条件是head=head-next;2.双向链表 双向链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前

14、趋的指针域。图2-3 双向循环链表注意： 双链表由头指针head惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双向循环链表（如图2-3）。二、栈（考点）1.栈的定义 栈（Stack）是一种“特殊的”线性表，这种线性表上的插入和删除运算限定在表的某一端进行的。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的操作是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入

15、的是被放在栈的底部，要到最后才能删除(如图2-4)。 图2-4 栈 上图中元素是以a1，a2，an的顺序进栈，退栈的次序却是an，an-1，a1。2.栈的存储：与线性表类似栈也有两种存储结构，即顺序存储结构和链表存储结构。注：栈支持子程序调用。2.1顺序栈 栈的顺序存储结构亦称为顺序栈，它是运算受限的顺序表。 1. 顺序栈的类型定义 const int MAXSIZE=100; /假定预分配的栈空间最多为100个元素 typedef int ElemType;/假定栈元素的数据类型为整型 struct SqStack ElemType elemMAXSIZE; /一维数组 int top;/变

16、量top指向最后进栈元素的位置 SqStack就是栈的顺序存储结构的类型标识符。 顺序栈中元素用向量存放，即数组。 栈底位置是固定不变的，可设置在向量两端的任意一个端点，一般为向量低端，即数组首栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置图2-5 顺序栈进栈例:假设MAXSIZE取值为，图2-5展示了顺序栈S中数据元素和栈顶指针的关系。图a为空栈，指针top=-1；图b为元素a1进栈，指针top=0；图c为元素a2、a3、a4依次进栈，指针top依次递增，top=3；图d为元素a4退栈，指针top减一，top=2。2. 顺序栈的基本操作

17、前提条件：若栈底位置在向量的低端，即S0是栈底元素。（1）进栈操作：进栈时，需将top加1top=MAXSIZE-1表示栈满上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。（2）退栈操作：退栈时，需将top减1top1 时，该结点的双亲结点编号为【i/2】； 若 2in ，它有编号为 2i 的左孩子，否则没有左孩子； 若 2i+1n ，则它有编号为 2i+1 的右孩子，否则没有右孩子。3.满二叉树和完全二叉树(1)满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树(如图3-3(a)。满二叉树的特点：每一层上的结点数都达到最大值。即对给定的高度，它是

18、具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。图3-3满二叉树和完全二叉树(2)完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树(如图3-3(b)。注：(1) 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。(2) 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。(3) 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 4.二叉树的存储结构在计算机中，二叉树通常

19、采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后继结点，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子节点的存储地址，称为左指针域；另一个用于指向该结点的右子节点的存储地址，称为右指针域。5.二叉树的遍历所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，并且每个结点仅被访问一次。（1）先序遍历若二叉树为空，则结束遍历操作；否则：i. 访问根结点；ii. 先序遍历左子树；iii. 先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则i. 中序遍历左子树；ii. 访问根结点；iii.

20、 中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则i. 后序遍历左子树；ii. 后序遍历右子树；iii. 访问根结点。【例3.1】写出图3-4所示的二叉树的前序、中序和后序遍历的序列。图3-4例3.1二叉树前序遍历序列：ABCDEF 中序遍历序列：CBDAEF 后序遍历：CDBFEA第四章 查找和排序一、查找查找(Searching)的定义是：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。通常，不同的数据结构，将采用不同的查找方法。1.顺序查找 顺序查找又称顺序搜索，一

21、般是指在线性表中查找指定的元素，查找方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若线性表中所有的元素与被查元素进行了比较但都不相等，则表示查找失败。顺序查找算法的时间复杂度如下：对于大的线性表来说，顺序查找的效率是很低的，但在如下两种情况下只能采用顺序查找。（1） 无序线性表（表中元素的排列是无序的），不管是顺序存储，还是链式存储。（2） 链式存储的有序线性表。2.二分法查找二分法查找只适用于顺序存储的有序表，所谓有序表是指线性表中的元素按值从小到大排列。设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：将x与线性表的中间项进行比较。

22、（1） 若中间项的值等于x，则说明查找成功，查找结束。（2） 若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。（3） 若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。重复如上查找过程，直到查找成功或子表长度为0为止。log2n在最好情况下，二分法查找只需比较一次即查找成功，最坏情况下需要比较log2n次。二、排序 在排序技术方面，主要考查简单插入排序、简单选择排序、冒泡排序、堆排序等方法。1. 简单插入排序法每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。【例4.1】设有一组关键字序列55，22，4

23、4，11，33，这里 n=5，即有5个记录。请将其按由小到大的顺序排序。排序过程如图4-1所示。图4-1 插入排序示例 2. 简单选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。【例4.2】图4-2是使用选择排序法对序列3,4,1,5,2按照由小到大排序过程的示意图。图4-2 选择排序示例3. 冒泡排序两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。【例4.3】图4-3是使用冒泡排序对3、4、2、1、5按照从小到大排序过程的示意图。图4-3 冒泡排序示例4. 堆排序首先

24、，将一个无序序列建成堆，然后，将堆顶元素与堆中的最后一个元素交换。不考虑已经换到最后的那个元素，将剩下的狀个元素重新调整为堆，重复执行此操作，直到所有元素有序为止。注：冒泡排序、简单插入排序与简单选择排序法在最坏的情况下需要比较n(n-1)/2次，而堆排序在最坏情况下需要比较的次数是nlog2n。第二部分 软件工程一、 软件工程概述1.软件的含义软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整集合。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序的开发、维护和使用有关的图

25、文资料。软件的分类（考点）：软件按功能可以分为应用软件、系统软件和工具软件（或支撑软件）。应用软件是为解决特定领域的应用而开发的软件；系统软件是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件；工具软件是介于两者之间，协助用户开发软件的工具性软件2.软件工程20世纪60年代计算机领域爆发“软件危机”，表现在如下方面：软件需求的增长得不到满足，软件开发成本和进度无法控制，软件质量难以保证，软件可维护性差，软件的成本不断提高，软件开发生产率的提高赶不上硬件的发展和应用需求的增长。（考点）软件工程的概念主要针对软件危机提出来的，软件工程是指，采用工程的概念、原理、技术和方法指导

26、软件的开发与维护。软件工程包括3个要素：方法、工具和过程。软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科。软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。3.软件生命周期（考点）软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程。可以将软件生命周期分为如下3个时期8个阶段：（1）软件定义期：包括问题定义、可行性研究和需求分析3个阶段；（2）软件开发期：包括概要设计、详细设计、实现和测试4个阶段；（3）运行维护期：即运行维护阶段。软件生命周期各阶段的主要任务如下： 问题定义：确定要求解决的问题是什么可行性研究与计划制定：决定该问题是否存

27、在一个可行的解决办法，确定待开发的软件系统的开发目标和总体要求，给出它的功能、性能、可靠性及接口等方面的方案，制订完成开发任务的实施计划。需求分析：对待开发软件提出的需求进行分析并给出详细定义，编写软件需求规格说明书、初步的用户手册和系统测试计划提交评审。软件设计：通常又分为概要设计和详细设计两个阶段，在本环节，程序设计人员给出软件的结构、模块的划分、功能的分配以及处理流程。需要编写概要设计说明书、详细设计说明书和测试计划初稿（集成测试计划和单元测试计划），提交评审。软件实现：在软件设计的基础上编写程序。同时需完成用户手册、操作手册等面向用户的文档。软件测试：在设计测试用例的基础上，检验软件的

28、各个组成部分。编写测试分析报告。运行维护：将已交付的软件投入运行，同时不断的维护，进行必要而且可行的扩充和删改。二、 软件需求分析（考点）需求分析所要做的工作就是深入描述软件的功能和性能，确定软件设计的限制和软件同其他系统元素的接口细节。1. 结构化分析法结构化分析法是需求分析中使用最多的一种方法，它分析的对象是数据流，采用自顶向下、逐层分解、建立系统的处理流程，强调开发方法的结构合理性及所开发软件的结构合理性的软件开发方法。结构化分析法的工具（考点）：数据流图（Data Flow Diagram，DFD）（如表1）、数据字典（Data Dictionary，DD）、结构化语言、判定表和判定树

29、等。表1 数据流图中主要图形元素及说明2. 软件需求规格说明书（以下简称“需求说明书”）软件需求规格说明书是需求分析阶段的最终成果，是软件开发中的重要文档之一。（1） 需求说明书的作用：便于用户、开发人员进行理解和交流；反映出用户问题的结构，可以作为软件开发工作的基础和依据，作为确认测试和验收的依据。（2） 需求说明书的内容：把在软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他与要求有关的数据。具体包括系统概述、数据描述、功能描述、性能描述、参考文献、附录等部分。（3） 需求说明书的特点：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改

30、性、可追踪性。三、 软件设计软件设计就是把软件的需求分析变成软件表示的过程，设计方法为结构化设计法，按自顶向下，对各个层次的过程细节和数据细节逐层细化，直到用程序设计语言能够实现为止，从而最后确定整个体系结构。注：面向对象具有封装性、继承性和多态性三个特点，设计工具为UML语言。1. 模块模块是指把一个待开发的软件分解成若干个小的简单的部分，解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。模块独立性是指，每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准，衡量指标为内聚性和耦合性。（1） 内聚性。一个模块内部各个元

31、素间彼此结合的紧密程度。包括偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚七种。内聚性越强，模块独立性越强。（2） 耦合性。模块间互相连接的紧密程度的设置。包括内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合七种。耦合性越弱，模块独立性越强。总之，优秀软件设计的原则为：高内聚、低耦合。（重要考点）2. 概要设计概要设计的主要任务是把需求分析得到的DFD转换为软件结构和数据结构。设计软件结构的具体任务是：将一个复杂系统按功能进行模块划分、建立模块的层次结构及调用关系、确定模块间的接口及人机界面等。数据结构设计包括数据特征的描述、确定数据的结构特性、以及

32、数据库的设计。显然，概要设计建立的是目标系统的逻辑模型，与计算机无关。典型的数据流类型有两种：变换型和事务性面向数据流的设计方法：变换型系统结构图和事务性数据流面向数据流设计方法的过程：（1）精化DFD。（2）确定DFD类型。（3）分解上层模块、设计中、下层模块结构。（4）根据优化准则对软件结构求精。（5）描述模块功能、接口及全局数据结构。（6）复查，进入详细设计。3. 详细设计详细设计的主要任务是设计每个模块的实现算法、所需的局部数据结构。详细设计的目标有两个：实现模块功能的算法要逻辑上正确和算法描述要简明易懂。详细设计的基本任务：（1）为每个模块确定采用的算法，选择某种适当的工具表达算法的

33、过程，写出模块的详细过程性描述。（2）确定每一模块使用的数据结构。（3）确定模块接口的细节，包括对系统外部的接口和用户界面、对系统内部吉他模块的接口，以及模块输入、输出数据及局部数据的全部细节。（4）为每一个模块设计出一组测试用例。详细设计的工具：图形工具程序流程图(PDF)、N-S图、问题分析图(PAD)和HIPO图表格工具判定表语言工具PDL（伪码）四、 软件测试软件测试就是利用测试工具按照测试方案和流程对产品进行功能和性能测试，甚至根据需要编写不同的测试工具，设计和维护测试系统，对测试方案可能出现的问题进行分析和评估。执行测试用例后，需要跟踪故障，以确保开发的产品适合需求。1. 软件测试

34、概述软件测试的分类：（1） 从软件的内部结构和具体的实现角度划分，分为白盒测试、黑盒测试。（2） 从执行程序的角度划分，分为静态测试和动态测试。（3） 按软件开发过程阶段划分，分为单元测试、集成测试、确认测试(验收测试)和系统测试。软件测试的步骤：(1) 单元测试 （2）集成测试 （3）确认测试 （4）系统测试。2. 软件测试技术（1） 静态测试：包括代码检查、静态结构分析、代码质量度量等。可以由人工进行，也可以借助软件工具自动进行。（2） 动态测试：是基于计算机的测试，目的是为了发现错误而执行程序的过程。（3） 白盒测试：也称结构测试或逻辑驱动测试，它是按照程序内部结构进行测试的程序，通过测

35、试来检测产品内部是够按照设计规格说明书的规定正常进行。白盒测试的主要方法有逻辑覆盖测试、基本路径测试。（4） 黑盒测试：也称功能测试，设计测试用例着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能测试，在测试中，把程序看成一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试。主要测试方法有等价类划分法、边界值分析法、错误推测法、因果法等。五、 程序的调试程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。程序调试的方法：静态调试和动态调试程序经常出现的

36、错误类型：编辑错误、编译错误、运行错误和逻辑错误。第三部分 数据库设计基础第一章 数据库的基本概念一、数据库相关概念数据处理包括对数据进行收集、存储、传送、整理、检索、计算、输出等各种加工和管理。数据库(DataBase,DB)是数据的集合，它有统一的结构系统，存放于统一的存储介质内，是多种应用数据的集成，并可被各种应用程序所共享。1.数据库系统数据库系统(Database System,DBS)由数据库、数据库管理系统、数据库管理员、硬件平台、软件平台五部分组成。硬件平台包括计算机和网络，软件平台包括操作系统和数据库系统开发工具。2.数据库管理系统数据库管理系统(Database Manag

37、ement System,DBS)是数据库的机构，用来帮助用户建立、使用、管理、加工和维护数据库而配置的专用系统软件，它在操作系统的支持下对数据库进行统一的管理和控制，并且其结构复杂。它的具体功能如下：（1）数据模式定义 （2）数据存取的物理构建 （3）数据操作（4）数据的完整性、安全性定义与检查 （5）数据库的并发控制与故障恢复 （6）数据的服务为完成以上六个功能，数据库管理系统一般提供相应的数据语言，包括数据定义语言（Data Definition Language，DDL）、数据操纵语言（Data Manipulation Language，DML）、数据控制语言（Data Contro

38、l Language，DCL）。3.数据库应用系统数据库应用系统（Database Application System，DBAS）是程序员根据用户的需要在数据库管理系统的支持下，用数据库管理系统提供的命令编写、开发并能够在数据库管理系统的支持下运行的程序和数据库的总称，如人事管理系统、物质管理系统，包括硬件、操作系统、数据库管理系统、应用开发工具、应用系统五个方面。二、数据库系统的发展1.数据管理发展至今经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。目前，根据数据之间的联系方式划分，数据库系统先后经历层次数据库、网状数据库和关系数据库三种类型。2.数据库系统具有如下特点：(1)

39、数据的集成性 (2)数据高共享性与低冗余性 (3)数据独立性 (4)数据的统一管理与控制3.关于数据库的新技术，下面三种比较重要：（1）面向对象数据库系统 （2）知识库系统 （3）关系数据库系统的扩充三、数据库系统的内部体系结构数据库系统的内部结构主要体现在三级模式和两级映射上。1.数据库系统的三级模式（考点） 数据模式是数据库系统中数据结构的一种表示形式，包括概念模式（又称模式或逻辑模式）、外模式、内模式三个层次结构，如图1-1.图1-1 三级模式图模式的3个级别层次反映了模式的3个不同环境及它们的不同要求，其中内模式处于底层，它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式，

40、概念模式处于中层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。一个数据库只有一个概念模式和内模式，可以有多个外模式。概念模式是数据库的中心和关键。内模式依赖于概念模式，独立于外模式和存储设备；外模式面向具体的应用，独立于内模式和存储设备；应用程序依赖于外模式，独立于概念模式和内模式。2.数据库系统的两级映射外模式/模式映射：把基于外模式的用户操作转换成对模式中数据的访问。模式/内模式映射：把模式中数据的逻辑定位映射成内模式中数据的物理存储位置。第二章 数据模型一、数据模型概述 1.数据模型是现实世界中数据特征的抽象，为数据库系统的信息表达与操作提供一个抽象的

41、框架。数据模型所描述的内容包括3个部分：数据结构、数据操作和数据约束。 2.数据模型分类：概念模型、逻辑数据模型（又称数据模型）和物理模型。 3.数据库领域中最常用的四种数据模型：层次模型、网状模型、关系模型和面向对象模型。二、E-R模型 概念模型中被广泛使用的模型是E-R模型，该模型将现实世界的要求转化成实体、联系、属性等几个基本概念，以及它们间的两种基本连接关系，并且可以用一种图非常直观地表示出来。 1.E-R模型的基本概念 （1）实体。现实世界中的事物都可以抽象成实体，实体是概念世界中的基本单位，它们是客观存在的且又能相互区别的事物。凡是有共性的实体可组成一个集合称为实体集。 （2）属性

42、。现实世界中事物的特性。 （3）联系。现实世界中事物间的关联称为联系。两个实体集间的联系实际上是实体集间的函数关系，这种函数关系有三种：一对一的联系、一对多或多对一联系、多对多联系。(如图1-2)图1-2联系的三种类型2.E-R模型的图示法 E-R模型可以用一种非常直观的图的形式表示，这种图称为E-R图。 （1）实体集表示法。在E-R图中用矩形表示实体集，如图1-3。 （2）属性表示法。在E-R图中用椭圆形表示属性，如图1-4。 （3）联系表示法。在E-R图中用菱形表示联系，如图1-5。 图1-3 实体集表示法 图1-4 属性表示法 图1-5联系表示法三、关系模型关系模型采用二维表来表示，简称表（如图1-6）。二维表由表框架及表的元组组成。表框架由n个命