全国VFP计算机二级公共基础知识

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

2、法；基本排序算法(交换类排序、选择类排序、插入类排序)。,考试大纲,考试内容 二、程序设计基础1、程序设计方法与风格。2、结构化程序设计。3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。,考试大纲,考试内容 三、软件工程基础1、软件工程的基本概念；软件生命周期概念；软件工具与软件开发环境。2、结构化分析方法；数据流图，数据字典，软件需求规格说明书。3、结构化设计方法； 总体设计，详细设计。4、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实施；单元测试，集成测试，系统测试。5、程序的调试，静态调试与动态调试。,考试大纲,考试内容 四、数据库设计基础1、数据库的基本概念

3、；数据库，数据库管理系统，数据库系统。2、数据模型；实体联系模型及E-R图，从E-R图导出关系数据模型。3、关系代数运算，包括集合运算及选择、投影、连接运算；数据库规范化理论。4、数据库设计方法和步骤；需求分析、概念设计、逻辑设计和物理设计的相关策略。,考试大纲,考试题型 选择题10 题每题 2 分共 20 分 填空题5 题每题 2 分共 10 分 合计30 分,数据结构与算法,关键考点 算法基本概念及算法复杂度 数据的存储结构 栈和队列 线性链表 二叉树基本概念及其特性 查找技术,第1节 数据结构与算法,算法的基本概念 1、算法算法是指解题方案的准确而完整的描述。注意：算法与数学上的计算方法

4、不是同一个概念。算法要考虑计算机的特点，要考虑计算方法的可行性。算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时，总是先设计算法，然后进行编程。 2、算法的基本特征可行性确定性有穷性拥有足够的情报算法是一个动态概念，强调实际的执行过程。数学上的计算方法是一个静态概念，注重理论上的正确性。数学上的计算方法是设计算法的基础。,例题： 算法的有穷性是指 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度 D算法只能被有限的用户使用,1. 算法的基本概念,第1节 数据结构与算法,算法的基本概念 3、算法的基本要素算法中对数据的运算和操作基本的运算和操作有：算术

5、运算、逻辑运算、关系运算、数据传输。算法的控制结构控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。 4、算法设计基本方法列举法 列举所有可能情况，检测其中符合条件的结果。归纳法 列举若干特殊情况，分析归纳出一般规律。递推 从已知初始条件出发，逐步推导出中间及最后结果。递归 将复杂问题归结为简单问题，在归结为更简单问题， 。减半递推技术 将问题规模“减半”，并重复该“减半” 的过程。回溯法 分析问题，找出某些线索，沿线索逐步试探。若试探成功，则继续，若试探失败，则回退。直至问题解决。,第1节 数据结构与算法,算法的基本概念 5、算法的时间复杂度指执行算法所需要的计算工作量算法工作量的

6、度量应与计算机、编程语言、编程细节等无关。算法的工作量用算法所执行的基本运算次数衡量。算法工作量是问题规模的函数：算法的工作量= f (n)度量方法有：平均性态分析 计算其加权平均值最坏情况分析 计算其基本运算的最大次数 6、算法的空间复杂度指执行算法所需要的存储空间包括：算法程序所占据的存储空间待处理数据所占据的存储空间算法程序执行中所需要的额外存储空间如果额外存储空间大小不随问题规模变化，则称之为算法原地工作。降低算法的空间复杂度，应从数据的存储空间和额外空间入手。,例题： 下列叙述中正确的是 A算法的效率只与问题的规模有关，而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计

7、算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关 算法的空间复杂度是指 A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量 C.算法程序中的语句货指令条数 D.算法在纸箱过程中所需要的临时工作单元数 4.算法的时间复杂度是指 A.算法的执行时间 B.算法所处理的数据量 C.算法程序中的语句或指令条数 D.算法在执行过程中所需要的基本运算次数,第2节 数据结构的基本概念,计算机处理数据，主要考虑两个方面： 一 、提高数据处理的速度？ 二 、节省存储空间？ 数据结构主要研究三个方面的问题： （1）数据的逻辑结构：各数据元素间所固有的逻辑关系

8、（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系 （3）对各种数据结构进行的运算。,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,数据结构与算法,数据结构的基本概念 数据结构的表示二元关系表示：两个要素：数据元素的集合D，该集合上的关系R。即：B=(D,R)如：D=春,夏,秋,冬 R=(春,夏),(夏,秋),(秋,冬)图形表示：标有元素值的方框表示结点，有向线段表示逻辑关系。春 夏 秋 冬 线性结构和非线性结构线性结构：一个非空的线性结构有且只有一个根结点，每个结点最多只有一个直接前驱、最多只有一个直接后继。非线性结构：

9、不是线性结构的数据结构。,1.下列叙述中正确的是 A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C.顺序存储结构能存储有序表，链式存储结构不能存储有序表 D.链式存储结构比顺序存储结构节省存储空间 2.下列数据结构中，属于非线性结构的是 A.循环队列B.带链队列 C.二叉树D.带链栈 3.数据的存储结构是指_。 A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据,第3节线性表和顺序存储结构 1 线性表的基本概念 线由一组数据元素组成。是

10、最简单、最常用的一种数据结构. 线性表是一种线性结构。 非空线性表有如下结构特征： （1）有且只有一个根结点 （2）有且只有一个终结节点 （3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。,2 线性表的顺序存储结构 具有如下特点逻辑相临，物理相临 （1）线性表中所有元素所占的存储空间是连续的。 （2）数据元素在存储空间中是按逻辑顺序依次存放的。,张三 70 70,李四 65 90,王五 68 80,线性表的顺序存储结构是一种随机存取的存储结构 。可随机访问任意一个结点,3 线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,1

11、4,3、线性表的插入运算,结论： （1）如果在线性表的末尾进行，即在第n个元素之后插入新元素，则只要增加一个元素即可，不需要移动元素 （2）如果要在线性表的第1个元素之前插入，则需要移动表中n个的元素。 （3）在一般情况下，如果在第i个元素之前进行，则第i个元素之后的所有元素都必须移动。 在平均情况下，需要移动表中一半的元素。 因此算法的平均时间复杂度为O(n).,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,注意： 如果为线性表开辟的存储空间已经满了，不能再插入元素，否则会造成“上溢”错误,1 如果删除第n个元素，则不需要移动其

12、他元素； 2 如果删除第1个元素，则需要移动所有的元素。 3 在一般情况下，若要删除第i个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。 平均要移动表中一半的元素。 算法的平均时间复杂度为O(n).,结论： 线性表顺序存储，插入或删除一个元素，效率很低，特别是线性表比较大的情况，由于数据元素的移动而消耗较多的处理时间。 线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。,对线性表，描述的是（） A 存储空间不一定连续，且各元素的存储顺序是任意的 B存储空间不一定连续， 且前件元素一定存储在后件元素前面 C存储空间必须连续， 且前件

13、元素一定存储在后件元素后面 D存储空间必须连续，且各元素的存储顺序是任意的,数据结构与算法,线性链表 1、链式存储方式 结点由两部分组成：数据域(存储数据)、指针域(指向其前件或后件)。 数据结构的存储空间可以不连续，存储顺序与逻辑关系可以不一致。 链式存储方式既可以用来表示线性结构，也可以表示非线性结构。 2、线性链表线性表的链式存储结构称为线性链表。(栈的链式存储结构称为链栈、队列的链式存储结构称为链队列)常用的线性链表有：单链表 (一个指针域，指向直接后继)双向链表 (两个指针域，指向直接后继及后继) 循环链表 (所有结点的指针构成循环链) 3、线性链表的基本运算查找：在线性链表中查找指

14、定元素。插入：在线性链表中插入新结点。删除：在线性链表中删除指定结点。,例题： 1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的 链式 存储结构。 2.下列叙述中正确的是 A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D.上述三种说法都不对,3.线性表的顺序存储结构和线性表的链式存储结构分别是_。A. 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存取的存储

15、结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构4.用链表表示线性表的优点是_。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取 5.在单链表中，增加头结点的目的是_。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现,数据结构与算法,栈及其基本运算 1、栈栈(stack)是限定在一端进行插入和删除的线性表允许进行插入或删除的一端称为栈顶。不允许进行插入或删除的另一端称为栈底。其特点为“先入后出”(FILO)或“后入先出”(LIFO)。(记忆作用

16、)通常设置指针top指向栈顶，指针bottom指向栈底。 2、栈的顺序存储结构栈的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在栈顶一端进行，所以不需要移动数据元素。 3、栈的基本运算入栈：在栈顶位置插入新元素。出栈：取出栈顶位置的元素。读栈顶元素：读出栈顶位置的元素。“上溢”：入栈时堆栈已满。“下溢”：出栈时堆栈已空。,第4节 栈和队列 1 栈及其运算 栈是限定在一端进行插入与删除的线性表。 入栈原则：先进后出，后进先出。,栈顶,栈底,6 4,入栈（插入数据）,栈顶,栈底,6,栈顶,栈底,入栈（插入数据）,栈顶,栈底,出栈（删除数据）,栈顶,栈底,出栈（删除数据）,栈顶,栈底,

17、出栈（删除数据）,2 栈的特点,1 栈顶元素总是最后被插入的元素，也是最早被删除的元素。 2 栈底元素总是最早被插入的元素，也是最晚被删除的元素。 3 栈具有记忆作用。 4 在顺序存储结构下，栈的插入与删除运算不需要移动表中其他数据。 5 栈顶指针，top动态反映了栈中元素的变化情况。 6 栈和线性表实现方法类似顺序和链接,下列关于栈的描述正确的是（）A 在栈中只能插入元素而不能删除元素 B 在栈中只能删除元素而不能插入元素 C 栈是特殊的线性表，只能在一端插入或删除元素 D 栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素,下列关于栈的描述中错误的是（） A 栈是先进后出的线性表 B

18、 栈只能顺序存储 C 栈具有记忆作用 D 对栈的插入与删除操作中，不需要改变栈底指针,0809： 一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则出栈序列是_。 A) 12345ABCDE B) EDCBA54321 C) ABCDE12345 D) 54321EDCBA,1 若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ） A 1，4，3，2 B 2，3，4，1 C 3，1，4，2 D 3，4，2，1 2 若进栈序列是1，2，3，4，假定进栈和出栈可以穿插进行，则可能的出栈序列是（） A 2，4，1，3 B 3

19、，1，4，2 C 3，4，1，2 D 1，2，3，4,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进选出，后进后出”的原则,front,rear,入队（插入数据）,front,rear,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进选出，后进后出”的原则,入队（插入数据）,front,rear,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,入队（插入数据）,front,rear,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原

20、则,出队（删除数据）,front,rear,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,出队（删除数据）,front,rear,栈和队列的共同点是（ ） A 都是先进先出 B 都是后进先出 C 只允许在端点处插入和删除元素 D 没有共同点,一个队列的入队序列是1，2，3，4，则队列的输出序列是 A 4，3，2，1 C 1，4，3，2 D 3，2，4，1,B 1，2，3，4,front,rear,下列叙述中正确的是（） B 栈与队列是非线性结构 C 线性链表是非线性结构 D 二叉树是线性结构,下列关于队列的叙述中正确的是（） A 在队列中

21、只能插入数据 B 在队列中只能删除数据 D 队列是先进后出的线性表,出队（删除数据）,C 队列是先进先出的线性表,A 线性表是线性结构,例题： 1. 设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有 24 个元素。 实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6、7、829这24个空间存有元素。,5,6,7,29,50,1,数据结构与算法,队列及其基本运算 1、队列队列(queue)是限定在一端进行插入另一端进行删除的线性表允许进行插入的一端称为队尾。允许进行删除的另

22、一端称为队头。其特点为“先入先出”(FIFO)或“后入后出”(LILO)。(先来先服务)通常设置指针rear指向队尾，指针front指向队头。 2、队列的顺序存储结构队列的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在队列的两端进行，所以不需要移动数据元素。 3、队列的基本运算在实际应用中常常使用循环队列。入队：在队尾位置插入新元素。 出队：取出队头位置的元素。 “上溢”：入队时队列已满。“下溢”：出队时队列已空。,数据结构与算法,树的基本概念 1、树树是一种简单的非线性结构。元素间的关系具有明显的层次结构。 2、相关的术语根结点叶节点父结点子结点子树结点的度树的度树的深度,数据

23、结构与算法,二叉树 1、二叉树的特点非空二叉树只有一个根结点。每个结点最多有左右两棵子树。 2、二叉树的基本性质 第 k 层上最多有 2 k-1个结点 深度为 m 的二叉树最多有 2m-1个结点 任何二叉树叶结点总比度为 2 的节点多一个 n 个节点的二叉树的深度为 log2n+1 3、满二叉树 4、完全二叉树 5、二叉树的遍历 先序遍历 中序遍历 后序遍历 ABDEGCFHI DBGEACHFI DGEBHIFCA,一棵二叉树第六层的结点数最多为 （ ） 个 某二叉树中，度为2的结点有18个，则有（ ）个叶子结点。一棵完全二叉树有700个结点，该二叉树中有（ ）个叶子结点,32,19,350

24、,N0+N2+N1=700 N1=1 N0=N2+1 2*N2+N1+1=700 N2=349 N0=350,6 二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。,C,遍历分三种方式：前序、中序和后序遍历。,前序遍历法 首先访问根结点,再访问左子树,最后访问右子树，并且在访问左子树和右子树时,仍然是先访问根，再左子树，最后右子树。,例：用前序法访问：,FCADBEGHP,ACBDFEHGP,中序遍历法 首先访问历左子树，再访问根结点，最后中序右子树。 并且在访问左子树和右子树时,仍然是先访问左子树，再访问根，最后是右子树。,例：用中序法访问：,后序遍历 首先后序遍历左子树，再右子树，最后访

25、问根结点，并且在访问左子树和右子树时,仍然是先访问左子树，再访问右子树，最后是根。,ABDCHPGEF,例：用后序法访问：,A bdc,F,HPGe,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc,c,e,a,d,b,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc 由后序由以知道根节点是C； 而C又在中序的最后，说明 没有右子树。,c,e,a,d,b,实例：已知二叉

26、树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc,c,e,a,d,b,设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为_。,如图所示的二叉树，其中序遍历的结果为（ ） A abcdef B abdefc C dbefac D defbca,a,b,c,e,f,d,数据结构与算法,查找技术 1、顺序查找从线性表的第一个元素开始，依次与指定数据比较，若相等则查找成功，若比较的所有元素都不相等，则查找失败。最坏情况的比较次数为表长n，平均情况为n/2。无序顺序表的

27、查找只能采用顺序查找的方法。线性表在链式存储时也只能采用顺序查找的方法。 2、二分法查找在顺序存储的线性表为有序的情况下，可以使用二分法查找。方法为：将待查数据与线性表的中间项比较：若相等，则查找成功；若小于，则在线性表的前半部分进行二分法查找；若大于，则在线性表的后半部分进行二分法查找；反复进行直到相等(查找成功)或子表长度为0(查找失败)。,数据结构与算法,排序技术 1、交换类排序起泡排序最坏情况下的比较次数为 n(n-1)/2 。 快速排序最坏情况下的比较次数为 n(n-1)/2 。 2、插入类排序简单插入排序最坏情况下的比较次数为 n(n-1)/2 。 希尔排序最坏情况下的比较次数为

28、O( n 1.5) 。 3、选择类排序简单选择排序最坏情况下的比较次数为 n(n-1)/2 。堆排序最坏情况下的比较次数为 O( n log2n) 。,数据结构与算法,本章重点 1、算法是问题处理方案正确而完整的描述，算法的效率与数据的存储结构有密切的关系。 2、数据的逻辑结构在计算机中的表示(存储方式)称为数据的存储结构(物理结构)。一种逻辑结构可以有多种存储结构。 3、在长度为 n 的顺序表中，插入或删除一个元素平均需要移动一半元素。 4、栈是特殊的线性表，具有记忆作用。特点是“先进后出(后进先出)”。栈顶指针动态反映了栈中元素的变化情况。 5、队列是特殊的线性表。特点是“先进先出(后进后

29、出)”。队头和队尾指针动态地反映了队列中元素的变化情况。 6、线性链表是线性表的链式存储结构。在线性链表中，各元素节点的存储空间可以不连续，存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需要移动数据元素。 7、二叉树是一种非线性结构。主要性质有：第k层上最多有 2 k-1 个结点 深度为 m 时，最多有2 m 1 个结点度为0的结点比度为2的多一个 深度至少为 log2n +1,数据结构与算法,本章重点 8、满二叉树是二叉树的特殊形态，满二叉树的各层结点都达到最大值，叶结点只出现在最后一层。 9、完全二叉树是二叉树的特殊形态，完全二叉树除最后一层外，各层结点都达到最大值，叶结点只出现

30、在最后两层。满二叉树属于完全二叉树。 10、根据扫描根结点的顺序，按照先左后右的原则，遍历二叉树有三种方法：前序遍历、中序遍历、后序遍历。 11、在长度为 n 的线性表中进行顺序查找，最坏情况需要比较 n 次。 12、在长度为 n 的线性表中进行对分查找，最坏情况需要比较 log2n 次。但对分查找只适用于有序顺序表。 13、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况下需要比较的次数为 n(n-1)/2 。,程序设计基础,关键考点 结构化设计的原则 面向对象方法的基本概念,程序设计基础,程序设计方法与风格 1、程序设计方法就程序设计的方法和技术的发展而言主要经历了结构化程序

31、设计和面向对象程序设计两个阶段 2、程序设计风格程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序的结构清晰合理，使程序代码便于维护。程序设计风格的主导：“清晰第一，效率第二”。主要因素：源程序文档化数据说明的方法语句的结构输入和输出,程序设计基础,结构化程序设计 1、结构化程序设计要求把程序的结构限制为顺序、选择和循环三种基本结构。 2、结构化程序设计的原则自顶向下先总体后细节，先全局后局部。逐步求精对复杂问题设计子目标过度，逐步细化。模块化将复杂问题分解为若干简单问题。限制使用GOTO语句防止造成程序逻辑结构

32、混乱。 3、三种基本结构顺序结构 选择结构循环结构 4、特点所有控制结构由三种基本结构组成各个模块单入口单出口模块的内聚性强 模块间的偶合性低,程序设计基础,面向对象的程序设计 1、面向对象面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现实生活中常用的思维方法来描述客观事物，是系统中的对象及对象间的关系能如实反映事物及其关系。 2、主要优点与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好 3、基本概念对象类和实例消息继承多态性,程序设计基础,本章重点 1、程序设计并不等于编程，编程只是程序设计过程中的一小步。 2、结构化程序设计要求把程序的结构限制为顺序、

33、选择、循环三种基本结构。 3、模块化设计是指把一个大程序按人们能理解的大小规模进行分解。划分模块的基本原则是使每个模块都易于理解。在按功能划分模块时，要求各模块功能尽量单一，各模块之间的联系尽量的少。 4、客观世界是由实体及其联系所组成的。客观世界中的实体称为问题域的对象。 5、类描述的是具有相似性质一组对象。一个对象称为类的实例。 6、允许作用于某个对象上的各种操作称为方法。 7、消息是用来请求对象执行某一处理或回答某些信息的要求。 8、继承是表示类之间的相似性的一种机制。 9、封装是一种信息隐蔽机制，目的是将对象的使用者与对象的设计者分开。用户只需了解对象封装界面上的信息，不必知道内部的具

34、体细节。,软件工程基础,关键考点 软件定义与特点 软件开发过程的过程化原则 结构化分析方法 结构化设计方法 软件测试技术与方法 程序调试基本概念,软件工程基础,软件工程基本概念 1、软件软件是包括程序、数据及相关文档的完整集合。 2、软件的特点抽象性可大量拷贝无磨损及老化问题受计算机系统限制(移植问题)复杂性高成本昂贵开发过程涉及诸多社会因素 3、软件工程软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。三个要素方法：完成软件工程项目的技术手段。工具：支持软件的开发、管理、文档生成。过程：支持软件开发各个环节的管理、控制。目标：在给定成本、进度的前提下，开发

35、出具有有效性、可靠性、可理解性、可维护性、可适应性、可追踪性、可互操作性满足用户要求的软件产品。,软件工程基础,软件开发过程的过程化原则 1、软件工程过程 为获得软件产品，在软件工具支持下的一系列软件工程活动。Plan软件规格说明。Do软件开发。Check软件确认。Action软件演进。 使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将用户要求转化为软件产品。软件工程过程应确定方法使用的顺序、要求交付的文档资料、为保证质量与适应变化所需要的管理、软件开发各阶段要完成的任务。 2、软件生命周期 定义阶段可行性研究及项目计划需求分析 开发阶段概要设计详细设计实现测试 维护阶段使用维护退

36、役,软件工程基础,结构化分析方法 在系统分析阶段，结构化分析方法用来对系统进行逻辑设计。 1、需求分析需求分析的任务是发现需求、求精、建模和定义需求。 常见的需求分析方法：结构化分析方法 面向对象的分析方法 2、结构化分析方法 结构化分析就是使用数据流图(DFD)、数据字典(DD)、结构化英语、判定表和判定树等工具，来建立一种被称为结构化规格说明的目标文档。 结构化分析方法的实质是着眼于数据流的、自顶向下逐层分解的、建立系统的处理流程，它以数据流图和数据字典为主要工具，建立系统的逻辑模型。 3、 软件需求规格说明书是需求分析阶段的最后成果，是软件开发的重要文档之一。软件需求规格说明书把软件计划

37、中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准、其他与要求有关的信息。,软件工程基础,结构化设计方法 1、软件设计软件设计是把软件需求转换为软件表示的过程。从技术角度：软件设计包括结构设计、数据设计、接口设计、过程设计。从工程角度：软件设计包括概要设计、详细设计。软件设计的基本原理包括：抽象、模块化、信息隐蔽、模块独立性 2、概要设计概要设计的基本任务：系统结构设计数据结构设计编写设计文档设计文档评审结构图是软件结构设计的常用工具。 3、详细设计详细设计的任务，是为软件结构图中的每一个模块确定算法和局部数据结构，用某种选定的工具表示算法和数据结构的细节。常见的设

38、计工具：图形工具：流程图、N - S、PAD、HIPO表格工具：判定表语言工具：PDL(伪码),软件工程基础,软件测试 1、测试软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。测试不是为了证明程序是正确的，目的是设法暴露程序中的错误和缺陷。测试只能说明程序有错，不能证明程序无错。程序不能100%可靠。 2、测试方法程序的静态分析程序的动态分析自动测试工具 3、测试层次模块测试(单元测试)整体测试(集成测试)又分为 功能测试 和 验收测试 两种。 4、白盒法根据对程序内部逻辑结构的分析来导出测试用例。 5、黑盒法不考虑程序的内部结构特征，根据程序功能导出测试

39、用例。,软件工程基础,程序调试 1、调试与测试 测试的目的是发现错误，评价可靠性；调试的目的是发现错误的位置，改正发现的错误。 测试揭示设计人员的过失，由非设计人员承担；调试帮助设计人员改正错误，由设计人员自己承担。 测试是机械的、强制的、严格的、可预测的；调试要求随机应变、联想、经验、智力，并要求自主地完成。 测试发现的错误可立即进行调试改正，然后还必须再进行测试。 调试用例与测试用例可以一致也可以不一致。 2、调试方法 强行排错法 回溯法 原因排除法,软件工程基础,本章重点 1、软件生命周期分为三个时期共八个阶段：软件定义期：问题定义、可行性研究、需求分析。软件开发期：系统设计、详细设计、

40、编码、测试。软件维护期：运行维护。 2、在系统分析阶段，结构化分析方法用来对系统进行逻辑设计，此时不考虑物理实现的问题，而只考虑“做什么”的问题，系统的物理设计(“如何做”)的问题留在系统设计阶段用结构化设计方法来完成。 3、数据流图有两种典型的结构形式：变换型、事务型。 4、评价模块的独立性的标准有两个：耦合性：表明两个模块间联系的强弱。内聚性：表明模块内部联系是否紧密。内聚性要强，偶合性要弱。 5、软件测试是在精心控制的环境下执行程序，发现程序中的错误，给出程序可靠性的鉴定。 6、测试是程序执行的过程，目的在于发现错误；一个好的测试在于能发现至今未能发现的错误，一个成功的测试是发现了至今未

41、发现的错误。 7、测试发现错误后，可进行调试；调试后的程序还应再测试，以检验调试效果。,数据库设计基础,关键考点 数据库系统基本概念 数据模型,数据库设计基础,本章重点 1、数据管理技术的发展分为三个阶段：人工管理、文件管理、数据库管理。 2、数据库系统是由操作系统、数据库管理系统和应用程序在一定的硬件支持下所构成的。数据库管理系统(DBMS)是整个数据库系统的核心，它对数据库中的数据进行管理，还作为用户应用与数据库之间的接口。 3、数据库技术的根本目标是要解决数据的共享问题。 4、数据库技术的特点之一是数据的独立性。数据的物理独立性表示数据的物理结构改变不会影响数据库的逻辑结构，不致引起应用

42、程序的变化。数据的逻辑独立性表示数据库总体逻辑结构改变不会影响局部逻辑结构，基于局部逻辑结构的应用程序也不必修改。 5、实体与实体之间的联系归结为三类：一对一联系、一对多联系、多对多联系。 6、在数据库系统中，由于采用的数据模型不同，响应的数据库管理系统(DBMS)也不同。目前常用的有：层次模型、网状模型、关系模型。,数据库设计基础,本章重点 7、网状模型和层次模型都属于格式化模型。所谓格式化模型，是指在建立数据模型时，根据应用的需要，事先将数据之间的逻辑关系固定下来(先对数据的逻辑结构进行设计使其结构化)。 8、在关系模型中，把数据看成二维表，每个二维表是一个关系。表中的列成为属性(记录的数

43、据项)，表中的行称为元组，相当于记录。 9、选择运算是在关系中选择满足条件的元组构成新的关系，该新关系是原关系的一个子集，它在关系的行方向上进行运算。 10、投影运算是在关系的某些域上进行操作，它是在关系的列方向上进行运算。 11、数据库设计是指在已有数据库管理系统的基础上建立数据库的过程。 12、数据库设计分为需求分析、概念结构设计、逻辑结构设计、物理结构设计等阶段。 13、E-R图(实体-联系图)是设计概念模型的有力工具。 14、数据字典是数据库的信息系统，是由关于数据库的数据描述信息组成的库，也称为描述数据库。,1. 数据库的基本概念,1. 数据库应用系统中的核心问题是 A数据库设计B数据库系统设计 C数据库维护D数据库管理员培训 2. 数据库系统的核心是 数据库管理系统 。 3. 数据库管理系统是 A.操作系统的一部分B.在操作系统支持下的系统软件 C.一种编译系统D.一种操作系统 4.在学生管理的关系数据库中，存取一个学生信息的数据单位是 A.文件B.数据库C.字段D.记录 5.层次型、网状型、关系型数据库划分的原则是 A.记录长度B.文件大小C.联系的复杂程度D.数据间的联系方式 6.下列叙述中正确的是_。 A. 数据库是一个独立的系统，不需要操作系统的支持 B. 数据库设计是指设计数据库管理系统C. 数据库技术的根本目标是要解决