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

《计算机二级考试之公共基础知识课件》由会员分享，可在线阅读，更多相关《计算机二级考试之公共基础知识课件（141页珍藏版）》请在金锄头文库上搜索。

1、计算机二算机二级考考试之公共基之公共基础知知识课件件二级公共基础知识点分值分布二级公共基础知识点分值分布 第一章 数据结构与算法(30%)n 考试大纲1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；

2、基本排序算法（交换类排序，选择类排序，插入类排序）。一.算法的基本概念 *1.所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：n有穷性有穷性（有限步骤内完成） 、 确定性确定性（结果不能模棱两可）、 可可行性行性（能够完成目标要求）、 输入输入 、 输出输出n输出和输出输出和输出可说成：拥有足够的情报拥有足够的情报 2.算法的组成要素n算法中对数据的运算和操作n算法的控制结构一.算法的基本概念3.算法设计的要求算法设计的要求 通常设计一个“好”的算法，应考虑达到以下目标。n正确性正确性：算法应当满足具体问题的需求。n可读性可读性：算法主要是为了人的阅读与交流

3、，其次才是机器执行。可读性好有助于人对算法的理解。n健壮性健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。 n效率与低存储量需求。效率与低存储量需求。效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。一.算法的基本概念4.算法设计基本方法n列举法n归纳法n递推n递归n减半递推n回溯法一.算法的基本概念*5.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度算法的时间复杂度n算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法

4、的时间复杂度为算法中的基本操作重复执行的次基本操作重复执行的次数数。是问题规模n的某个函数f(n)f(n)。一.算法的基本概念n何估算算法的时间复杂度？ 任何一个算法都是由一个“控制结构”和若干“原操作原操作”组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和 ( ( 原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间 ) )nFor i=1 to 100 for j=1 to 100 s=i*j。 算法时间复杂度为：O（n2)一.算法的基本概念（2 2）算法的空间复杂度）算法的空间复杂度n算法的空间负杂度是指执行这个算法所需要的内存空间。空

5、间复杂度作为算法所需存储空间的量度，记作：S(n)=O(g(n)S(n)=O(g(n)，其中n n为问题的规模，表示随问题规模的增大，算法运行所需存储量的增长率与g(n)g(n)的增长率相同。n一般不估计空间复杂度(3)(3)算法分析：算法分析：对算法的效率算法的效率进行分析，以求改以求改进进的过程。典型例题1.一个算法是对某类给定的问题求解过程的精确描述，算法中的操作都 可能通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有什么特性？ A 有穷性 B 可行性 C 确定性 D 健壮性2.算法的时间复杂度是指（） A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需

6、要的基本运算次数 D）算法程序中的指令条数 3.下面叙述正确的是（） A）算法的执行效率与数据的存储结构无关 B）算法得空间复杂度是指算法程序中指令（或语句）的条数 C）算法得有穷性是指算法必须能在执行有限个步骤之后终止 D）以上三种描述都不对 4.算法能正确地实现预定功能的特性称为算法的（ ）。 A正确性 B易读性 C健壮性 D高效率5. 算法的计算量的大小称为计算的（ ）。 A效率 B. 复杂性 C. 现实性 D. 难度 二.数据结构1.数据结构的定义：数据结构的定义： 是指相互有关联的数据元素的集合。 备注： 1）数据元素：是数据的基本单位基本单位，由数据项组成。通俗的说：数据元素就是现

7、实世界中的一个实体的抽象。 2）数据项：数据的最小单位最小单位。*2. 数据结构主要研究三个方面的问题：数据结构主要研究三个方面的问题： 1)数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构逻辑结构。2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构存储结构。3)对各种数据结构进行的运算运算。数据结构简单实例Student Student zhangsan Student lisi name; zhangsan; lisi; Sno; s20081001; s20081001; class; 计算机1班； 计算机1班； Rscore; 515； 501； 数据的逻辑结

8、构n数据逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述（本身固有的），它可以用一个数据元素的集合和定义在此集合上的若干关系表示。n与数据在计算机中的存储位置无关，是独立于计算机的。n常见的有线性结构线性结构和非线非线性结构性结构两种。 数据的存储结构n数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示，也称为物理结构物理结构。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素数据元素，在存储空间中建立各存储结点之间的关联关联，来表示数据元素之间的逻辑关系逻辑关系。n常见的存储结构：n顺序存储结构、链式存储结构、索引存储结构、散列存储结构典型例题（1

9、）数据结构中，与所使用的计算机无关的是数据的A）存储结构 B）物理结构C）逻辑结构 D）物理和存储结构（2）数据在计算机中的存储位置改变了，（）不变。A.数据的存储地址 B.数据间的逻辑关系C.数据的物理存储结构 D.逻辑结构和物理结构线性结构和非线性结构线性结构线性结构n在数据元素的非空有限集合中，线性结构的逻辑特征如下：n存在一个唯一的被称为“第一个”的数据元素n存在一个唯一的被称为“最后一个”的数据元素n除第一个之外，集合中的每个数据元素均有且只有一个直接前驱n除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构n非线性结构的逻辑特征是：一个结点可能有多个直接前

10、驱和直接后继，树和图都属于非线性结构。线性表n通常以下列 n 个数据元素的序列”表示线性表线性表 ：(a1,a2,.,ai,.,an)n序列中数据元素的个数 n 定义为线性表的表长表长；n=0 时的线性表被称为空表空表。称 i 为ai在线性表中的位序位序。n元素大多数时候称为”结点结点“线性表的顺序存储n线性表的顺序存储结构用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素，即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。 所有结点的存储位置均可由第一个结点的

11、存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址基地址 一个数据元素所占存储量一个数据元素所占存储量 线性表的插入和删除运算n插入结点插入结点：要在第i(1in)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。n删除结点：删除结点：要删除第i(1in)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。栈n栈栈是限定仅在表的一端进行插入和删除表的一端进行插入和删除操作的线性表线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。n栈顶元素栈顶元素总

12、是最后被插入的元素，从而也是最先被删除的元素；栈栈底元素底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种后进先出后进先出（LIFO）的线性表。n通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的顺序存储及运算n用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。top=0表示栈为空，top=m表示栈满。n栈的操作n入栈：入栈：在栈顶位置插入一个新元素，栈顶指针top加1。n退栈退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。n取栈顶元素：取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针栈顶指针toptop不变不变。栈的溢出

13、n上溢上溢 当栈满时再做进栈运算必定产生空间溢出，简称“上溢”。n下溢下溢 当栈空时再做退栈运算也将产生溢出，简称“下溢”。n备注备注 (1)上溢是一种出错状态出错状态，应该设法避免避免之；下溢则可能是正常正常现象现象。 (2) 两个栈共享两个栈共享一块空间时，分配的存储空间要大于等于栈元大于等于栈元素较多的栈素较多的栈，这样可以减少减少“上溢上溢”。栈n如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（）A、DCEFBA B、ABCDEF C、EDFCAB D、CBAEDF 备注：这样的题目，字母出来的顺序不可以：备注：这样的题目，字母出来的顺序不可以：先大，先大，后小，再中。后小，

14、再中。例：如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A）e3,e1,e4,e2 B）e2,e4,e3,e1C）e3,e4,e1,e2 D）任意顺序队列n队列队列是一种先进先出先进先出的线性表线性表，它只允许在表的一端插一端插入入元素(队尾队尾)，在另一端删除元素另一端删除元素( (队头队头)。n向队尾队尾插入一个元素的操作称为入队，头指针入队，头指针front +1front +1，从队头队头删除一个元素的操作称为退队退队，尾指针尾指针rear+1rear+1。n队列和栈队列和栈一样是一种特殊的线性表特殊的线性表、是操作受限操作受限的线性线性表表、也称其为限定性数据结构为限定性数

15、据结构。循环队列n将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的逻辑上的环状空间环状空间。循环队列初始状态为空，即front=rear=0.nFront总是指示队头元素，rear指示队尾元素加1的位置。n入队操作时，rear加1，若rear+1=容量，则置rear=0；n退队操作时，front加1，若front+1=容量，则置front=0。n*当rearfront时，元素个数rearfront ；当rearnextP-next删除节点：删除节点：p-next= p-next-nextp-next= p-next-next插入节点：插入节点：p-next= pxp-next= px

16、px-next=p-after that px-next=p-after that双向链表和循环链表n在双向链表中的结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。n循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。HEADHEADHEADHEADHEADHEAD回顾：例：已知一组数据原先采用顺序存储，现改为散列存储，则（）不变。 A.存储结构 B.逻辑结构 C.数据间的顺序 D.不确定例：常见的线性结构有_,_,

17、_例：在线性表中删除第5个节点，则原第6个节点的位置（），如果单链表则（） A.6 B.5 C.不变 D.不确定例：已知栈的头指针front当前位置为5，从栈中读取一个数据，则front指向（） A.5 B.6 C.不变 D.不确定例：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（） A、435621 B.123456 C、546312 D、654321树及其基本概念n树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。n树是(n0)个结点的有限集合，在任意一棵非空树中： (1)有且仅有一个特定的结点称为根结点。 (2)当n1时，其余的结点可分为m个互不相交的

18、子集T1,T2,Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。n集合为空的树简称为空树；树中的元素称为结点。树的主要术语n结点的度：结点拥有的子树数。n叶节点(终端结点)：度为0的结点。n双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。同一个双亲结点的孩子互称为兄弟。n层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。n深度：树中结点的最大层次称为树的深度或高度。二叉树n二叉树是n(n0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。n

19、二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。二叉树的基本性质n性质性质1 1 在二叉树的第i层上至多有2i-1个结点（i1）n性质性质2 2 深度为k的二叉树至多有2k -1个结点（k1）n性性质质3 3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2 ，则：n0 =n2+1n性性质质4 4 具有n个结点的二叉树，其深度至少为log2n +1例： 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A）221 B）219 C）231 D）229 例：一棵含18个结点的二叉树的高度至少为(),

20、至多为（） A）3 B）4 C）5 D）6 E)18 F)17满二叉树和完全二叉树n满二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。n完全二叉树完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为log2n +1。n从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树满二叉树 最大层的结点最大层的结点均向左靠齐均向左靠齐 完全二叉树完全二叉树 ADCBEF二叉树的基本性质性质性质5 5

21、如果对一棵有 n 个结点的完全二叉树（其深度为log2n +1）的结点按层序（从第1层到第log2n +1 层，每层从左到右）从1起开始编号，则对任一编号为 i 的结点(1in)，则:(1) 如果 i=1，则编号为 i 的结点是二叉树的根，无双亲；如果 i1，则其双亲结点 parent(i)的编号是i/2。(2) 如果 2in，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 lChild(i) 的编号是 2i 。(3) 如果 2i+1n，则编号为 i 的结点无右孩子；否则其右孩子结点 rChild(i) 的编号是结点 2i+1。 例： 在一棵二叉树上第5层的结点

22、数最多是 A）8 B）16 C）32 D）15例：在深度为5的满二叉树中，叶子结点的个数为 A）32 B）31 C）16 D）15例：深度为4的二叉树中，编号为7的节点，它的右孩子节点为（）该树为满二叉树；如果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为（） A）14 B）8 C）9 D）15例：设树T的度为4，其中度为1，2，3，4的结点个数分别人4，2，1，1.则T中的叶子结点数为 A)8 B)7 C)6）二叉树的链式存储结构n在二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。L(i)V(i)R(i)L

23、childvalueRchild二叉树的链式存储结构二叉树的遍历n二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由根结点、左子树和右子树三部分构成，则遍历二叉树的操作可分解为访问根结点、遍历左子树和遍历右子树三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样递归进行。 先序遍历二叉树先序遍历二叉树中序遍历二叉树中序遍历二叉树后序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；否则(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。 若二叉树为空，则空操作；否则(1) 中序遍历左子树；(2) 访问根结点；(3) 中序遍

24、历右子树。 若二叉树为空，则空操作；否则(1) 后序遍历左子树；(2) 后序遍历右子树；(3) 访问根结点。二叉树的遍历先序遍历：ABDEGHCFIJ中序遍历：DBGEHACIJF后序遍历：DGHEBJIFCA二叉树的遍历n已知前序和中序遍历时，根据前序判断出根，根据已知前序和中序遍历时，根据前序判断出根，根据中序分出左右子树；再根据前序分别判断出左右子中序分出左右子树；再根据前序分别判断出左右子树的根，然后再分出左右子树，以此类推下去树的根，然后再分出左右子树，以此类推下去例：某二叉树的前序遍历结点访问顺序是A B D E C ，中序遍历的结点访问顺序是D B E A C，则后序遍历的结点访

25、问顺序是：n已知后序和中序遍历时，根据后序判断出根，根据已知后序和中序遍历时，根据后序判断出根，根据中序分出左右子树；再根据后序分别判断出左右子中序分出左右子树；再根据后序分别判断出左右子树的根，然后再分出左右子树，以此类推下去树的根，然后再分出左右子树，以此类推下去例：已知一棵二叉树的中根序列和后根序列分别为31564和36541，试画出这棵二叉树。 前序和中序推理过程nA B D E C 前序nD B E A C 中序中序和后序推理过程n3 6 5 4 1 后序n3 1 5 6 4 中序例题例例1 1：某二叉树的前序遍历结点访问顺序是A AB BD DG GC CE EF FH H，中序遍

26、历的结点访问顺序是D DG GB BA AE EC CH HF F，则后序遍历的结点访问顺序是：例例2 2：已知一棵二叉树的中根序列和后根序列分别为B BD DC CE EA AF FH HG G和D DE EC CB BH HG GF FA A，试画出这棵二叉树。 GDBEHFCA例：例：某二叉树的前序遍历结点访问顺序是ABEFGHMN，中序遍历的结点访问顺序是EFBGAMHN，则后序遍历的结点访问顺序是：例：已知一棵二叉树的中根序列和后根序列分别为和，试画出这棵二叉树。(节点为0到9的数字）FEGBMNHA查找n顺序查找:是指在一个给定的数据结构中查找某个指定的元素。n顺序查找一般是指在线

27、性表中查找指定元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中的所有元素与被查找元素都不相等，则查找失败。n如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。n如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。n平均查找长度为（n+1)/2，最坏为n.二分查找(折半查找)二分查找法只适用于顺序存储的有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到0也没有找到目标元素为止。n查找过程中，给定值首先和处于待查区

28、间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。n在等概率状态下查找成功时的平均查找长度为：ASLlog2（ n1）-1（当n 50时） 折半查找二分查找例题：1.以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为(n+1)/2,时间复杂度为O(n)。2.以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于log2(n+1)，时间复杂度为O(log2n)。排序n排序是指将一个无序序列整理成按值递增或递减(本章均采用递增规则)的有序序列。n排序可以在各种不同的存储结构上实现，本章所介绍的

29、算法以顺序存储的线性表为排序对象，在程序设计语言中就是一维数组。n常见的排序方法有插入排序插入排序(包括简单插入排序法和希尔排序法等)、交换排序(包括冒泡排序和快速排序法等)和选择排序(包括简单选择排序和堆排序等)。 交换类排序n冒泡排序n基本思想：从表头开始扫描线性表，在扫描的过程中依次比较相邻两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置。显然，在扫描过程中，不断地将将相邻元素间较大的向后移动，最后将线性表中最大的元素移到表尾。n然后，从后向前扫描剩下的线性表，同样在扫描的过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则交换位置。在扫描过程中，不断地将将相邻元

30、素间较小的向前移动，最后将线性表中最小的元素移到表头。n对剩下的线性表重复上述过程，直到剩余线性表为空为止，此时线性表变为有序。n最坏情况下运算的次数为：最坏情况下运算的次数为：n*(n-1)/2n*(n-1)/2（即时间复杂度）。最好情况下为：最好情况下为：n-1.n-1.冒泡排序示例第一遍第一遍( (从前向后从前向后) )第一遍第一遍( (从后向前从后向前) )第二遍第二遍( (从前向后从前向后) )第二遍第二遍( (从后向前从后向前) )快速排序n基本思想：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，将前面大于T的元素移动到后面，将线性表分为两个部分(子表)，T放

31、到分界线的位置，这个过程称为线性表的分割，通过一次分割，就以T为分界将线性表分为两个子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原则对子表继续进行分割，直到子表为空，则整个线性表有序。快速排序n操作步骤：n首先，在表的第一个元素、最后一个元素和中间元素中选取一个中值，设为P(k)，并将P(k)赋值给T，再将表中的第一个元素移到P(k) 的位置。设两个指针i，j分别指向表的起始和最后位置，反复操作以下两步：将j逐渐减小，并逐次比较P(j)和T，直到发现一个P(j)T为止，并将P(i)移到 P(j)的位置上。n上述两步操作交替进行，直到i和j指向同一个位置，再将T

32、移动到P(i)的位置上，完成一次分割。31 68 45 90 233954 12 87 7631暂存枢轴记录暂存枢轴记录T T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割过程快速排序的一次分割过程31插入类排序n简单插入排序n基本思想：将待排序列表分成两部分：已排序部分和未排序部分。每次扫描将未排序列表中的第一个元素取出并插入到已排序列表中的合适位置。包含n个元素的列表最多需要n-1次扫描。简单插入排序示例原始序列第1趟第2趟第3趟第4趟第5趟希尔排序n基本思想：将整个无序序列分割成若干个小的子序

33、列分别进行插入排序。n子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。n增量序列一般取ht=n/2k(k=1,2log2n)希尔排序h=6h=6h=1h=1h=3h=3完成完成选择类排序n简单选择排序n基本思想：将待排序列表分成两部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一个元素进行交换。经过一次选择和交换，列表中已排序部分增加一个元素，未排序部分减少一个元素。每次把一个元素从未排序部分移动到已排序部分称为完成一次分类扫描分类扫描或称为一趟排序一趟排序。n一个包含n个元素

34、的列表需要进行n-1次扫描完成排序。简单选择排序示例原始序列第1趟第2趟第3趟第4趟第5趟排序时间复杂度汇总（基数空间为O（rd)*从上表应当看出：1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(n)。（也就是最好情况下） 。如果选择快速排序则相反，达到最坏时间复杂度。2.空间复杂度最坏的是归并排序O（n) ，其次是基数排序O（rd) 。3.平均时间最好的是快速、堆、归并排序O（nlgn)。4.稳定排序和不稳定排序（希尔、堆、直接选择，快速）。5.最坏情况下，时间复杂度最小的是：堆和归并排序。第二章 程序设计基础(15%)n考试大纲n1. 程序设计方法与风格。2.

35、结构化程序设计。3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。 知识点归纳n程序设计是一门技术，需要相应的理论、方法和工具来支持。就程序设计方法和技术的发展而言，主要经历了结构化的程序设计和面向对象的程序设计阶段。n在程序设计中，通常采用“自顶向下，逐步求精”的方法，即把一个模块的功能逐步分解，细化为一系列具体的步骤，进而转换成一系列用某种程序设计语言编写的程序。程序设计风格n除了程序设计设计方法和技术之外，程序风格也是非常重要的。良好的程序设计风格概括起来包括以下及格方面：n源程序文档化n数据说明的方法n语句的结构n输入和输出程序设计风格（4个方面）n源程序文档化n标识符的命

36、名标识符的命名:要有一定的实际含义要有一定的实际含义。n程序的注释：程序的注释：较完善程序一般要有注视。n序言性注释：通常置于每个程序模块的开头部分,一般给出程序的程序的整体说明。整体说明。n功能性注释：一般是对某条语句的功能性说明。n程序的视觉组织：程序的视觉组织：一定要层次清晰层次清晰n数据的说明n数据说明的次序应该规范化：数据说明的次序应该规范化：比如先说明变量，其次是简单类型（如数组），接着是构造类型（如自己定义的数据结构）。n说明语句中变量的安排有序化：说明语句中变量的安排有序化：例如多个变量出现在同一个说明语句中，要按顺序排列。n使用注释说明复杂的数据结构使用注释说明复杂的数据结构

37、程序设计风格n语句结构语句结构n在一行内只写一条语句n程序编写应优先考虑清晰性程序编写应优先考虑清晰性n除非对效率有特殊要求，程序编写要做到清晰第一，效率第二清晰第一，效率第二n首先要保证程序正确，然后才要求提高速度n避免使用临时变量而使程序的可读性下降n避免不必要的转移n尽可能使用库函数n避免使用复杂的条件语句n尽量减少使用“否定”条件的条件语句n数据结构要有利于程序的简化n要模块化，使模块功能尽可能单一化要模块化，使模块功能尽可能单一化n利用信息隐蔽，确保每一个模块的独立性利用信息隐蔽，确保每一个模块的独立性n从数据出发构造程序n不要修补不好的程序，要重写编写不要修补不好的程序，要重写编写

38、程序设计风格n输入和输出n对所有输入数据检验合法性对所有输入数据检验合法性n检查输入项的各种重要组合的合法性n输入格式要简单，以使输入的步骤和操作尽可能简单n输入数据时，应允许使用自由格式n应允许缺省值n输入一批数据时，最好使用输入结束标志n在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息n当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。结构化程序设计n结构化程序设计的原则n自顶向下自顶向下。程序设计时，应先考虑总体先考虑总体，后考虑细节细节；先考虑全局目标全

39、局目标，后考虑局部目标局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。n逐步求精逐步求精。对复杂的问题，应设计一些子目标过渡，逐步细化。n模块化模块化。一个复杂问题肯定是有若干简单问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标成为一个模块。n严格限制严格限制GOTOGOTO语句的使用语句的使用。（不是不能使用）结构化程序设计的基本结构和特点n程序由一些基本结构组成，任何一个程序都可以用三种基本控制结构组成： 顺序结构、选择结构和循环结构顺序结构、选择结构和循环结构n程序结构的特点：单入口、单出口、结构中无单入口、单出口

40、、结构中无死循环死循环（也称有限的控制结构），程序中三种基本控制结构之间形成顺序执行关系。n一个大型程序应按功能分割成一些模块，并把这些模块按层次关系进行组织层次关系进行组织。n在程序设计时应采用自顶向下、逐步细化的实施方法。例：结构化程序设计的基本思想是采用自自顶向下，逐步求精顶向下，逐步求精的程序设计方法和单入口单出口单入口单出口的控制结构。 面向对象程序设计 面向对象方法的基本概念1.1.对象、类和属性对象、类和属性 (1)对象的定义：在面向对象程序设计中，对象对象是程序的基本单位。对象可以表示客观世界中的任何实体实体，是对问题域中某个实体的抽象。 (2)对象通常由对象名、属性和操作三部

41、分组成。 (3)类是对一组具有共同属性和相似行为的对象的一种抽象， 类是对象的抽象类是对象的抽象，而对象是类的具体实例对象是类的具体实例。类是抽抽象的，象的，不占用内存不占用内存，而对象是具体的对象是具体的，占用存储空间占用存储空间。 对象的特点n标识唯一性：对象名是唯一的n分类性：每个对象都有属于自己的类。n封装性：将对象的属性和操作封装成一个整体，也实现了数据的隐藏。n模块独立性：例题：信息隐蔽的概念与下述哪一种概念直接相关_。A. 软件结构定义 B. 模块独立性 C. 模块类型划分 D. 模拟耦合度 对象的特点继承继承：指一个类(子类)直接使用另一个类(父类)的所有属性和方法。 单重继承

42、：单重继承：一个类从另一个类继承属性和操作 多重继承：多重继承：一个类有几个父类多态性：多态性：多态性可以用“一个对外界面，多个内部实现一个对外界面，多个内部实现”来表示。可以通过方法重载和方法重写重载和方法重写来实现多态。 举一个例子，计算机中的堆栈可以存储各种格式的数据，包括整型，浮点或字符。不管存储的是何种数据，堆栈的算法实现是一样的。 n例：有三个栈（对象），分别放数值型、字符型、日期型数据，队列（对象）向三个栈发送同样的“读取”消息，则产生的结果不一样。2.2.方法方法 方法也可称为操作或服务操作或服务，它描述了对象执行的功能，若通过消息传递，还可为其他对象使用。3.消息：消息：面向

43、对象系统中的对象之间是通过消息消息机制彼此相互合作的。消息由三部分组成： 消息标识符、零个或多个参数、接受消息消息标识符、零个或多个参数、接受消息对象的对象名对象的对象名面向对象程序设计的特点n按照人的思维方式对客观世界进行抽象n稳定性好n可重用性好可重用性好n易于开发大型软件n可维护性好n1、程序设计语言的基本成分是数据成分、运算成分、控制成分和（D） A）对象成分 B）变量成分 C）语句成分 D）传输成分n2、结构化程序设计主要强调的是 （D） A）程序的规模 B）程序的效率 C）程序设计语言的先进性 D）程序易读性n3、对建立良好的程序设计风格，下面描述正确的是（A） A）程序应简单、清

44、晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无n4、NULL是指（C） A）0 B）空格 C）未知的值或无任何值 D）空字符串n5、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C）nA）安全性 B）一致性 C）可理解性 D）合理性n6、子程序通常分为两类： 【过程】 和函数，前者是命令的抽象，后者是为了求值。n7、.在面向对象方法中，类之间共享属性和操作的机制称为 【继承】 。n8、一个类可以从直接或间接的祖先中继承所有属性和方法，提高了软件的 【可重用性】第三章 软件工程基础n考试大纲n

45、1. 软件工程基本概念，软件危机，软件工程的软件工程基本概念，软件危机，软件工程的三要素、目标与原则三要素、目标与原则。2. 结构化分析方法，数据流图，数据字典，软结构化分析方法，数据流图，数据字典，软件需求规格说明书。件需求规格说明书。3. 结构化设计方法，总体设计与详细设计结构化设计方法，总体设计与详细设计。4. 软件测试的方法，白盒测试与黑盒测试，测软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集试用例设计，软件测试的实施，单元测试、集成测试和系统测试。成测试和系统测试。5. 5. 程序的调试，静态调试与动态调试。程序的调试，静态调试与动态调试。 软件定义和

46、特点计算机软件计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整程序、数据及相关文档的完整集合集合。计算机软件具有如下特点：n软件是一种逻辑实体，具有抽象性n软件生产没有明显的制造过程n软件在运行、使用期间不存在磨损、老化问题n软件的开发、运行对计算机系统具有依赖性n软件复杂性高，成本昂贵n软件开发涉及诸多社会因素软件危机n所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题，包括：n软件需求的增长得不到满足n软件开发成本和进度无法控制n软件质量难以保证n软件不可维护或可维护性低n软件成本不断提高n软件开发生产率的提高赶不上硬件的发展和应用需求的增

47、长。软件工程n为了消除软件危机，提出了软件工程学。软件工程是为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。工具、文档、实践标准和工序。n软件工程的三要素n方法：方法：软件开发提供了“如何做”的技术。它包括了多方面的任务，如项目计划、软件系统需求分析、系统总体结构的设计、编码、测试及维护等。 n工具：工具：提供了自动的或半自动的软件支撑环境，即通常所说的软件工具 。n过程：过程：软件工程过程n软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。它包括两方面含义：n1. 软

48、件工程过程是指为获得软件产品获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动一系列工程活动。通常包括四种基本活动：nP(Plan)：软件规格说明nD(Do)：软件开发nC(Check)：软件确认nA(Action)：软件演进n2.从软件开发的观点看，软件工程过程是使用适当的资源，为开发软件进行的一组开发活动一组开发活动，在活动结束时将输入输入( (用户需求用户需求)转化为输出(软件产品软件产品) )。软件工程目标与原则目标：目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基本原则

49、：基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。*软件工程的理论和技术性研究的内容包括：软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。软件工程管理包括：软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。*衡量软件的指标：衡量软件的指标：高内聚（模块内）、低耦合（模块间）。软件开发工具与软件开发环境计算机辅助软件工程计算机辅助软件工程(CASE):(CASE):是一组工具和方法集合，可以辅助软件开发生命周期个阶段进行软件开发帮助进行应用程序开发的软

50、件，包括分析、设计和代码生成.(CASE)(CASE)的集成的集成: :(1)平台集成：工具运行在相同的硬件/操作系统平台。 (2)数据集成：工具使用共享数据模型来操作。 (3)表示集成：工具提供相同的用户界面。 (4)控制集成：工具激活后能控制其他工具的操作。(5)过程集成：工具在一个过程模型和“过程机”的指导下使用。 软件生命周期n软件从提出、实现、使用、维护到停止使用的过程称为软件的生命周期。一般包括以下几个阶段：n可行性研究：可行性研究：目的就是用最小的代价在尽可能短的时间内确定该软件项目是否值得去开发。其实质是要进行一次简化、压缩了的需其实质是要进行一次简化、压缩了的需求分析求分析n

51、需求分析：需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。 需求分析的方法是：结构化分析方法和面向对象分析方法。n软件设计：软件设计：任务从软件需求规格说明书出发，形成软件的具体设计方案，即划分模块结构的过程. n软件实现：软件实现：把软件设计转换成计算机可以接受的程序代码。 n软件测试软件测试:n运行和维护：运行和维护：软件生命周期中所花费最多的阶段是软件运行维护阶段。 需求分析阶段的主要工作n需求获取：需求获取：包括需求来源和获取需求的技术。它是软件设计的第一阶段，其本质主要是人的活动，涉及软件设计人员如何与客户建立有效的沟通(弄明白要做什么？）。也称为“需求

52、发现”、“需求获得”。 n需求分析：需求分析：对沟通获得的需求或信息进行分析、汇总，并判断能否完成。n编写需求规格说明书编写需求规格说明书(SRS) ：是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。n 需求评审：需求评审：在软件生命周期中，越晚发现的错误越难修改，修改成本越昂贵的论断也已经成为了大家的共识。 因此我们需要评审需求规格说明是否合理地确定了所有的性能目标，是否合理地确定了安全性方面要考虑到的问题。 软件需求n软件需求包括：功能需求、性能需求、环境需求、可靠性需求、安全保密需求、用户界面需求

53、、资源使用需求、成本消耗需求、开发进度需求等。n需求分析应交付的主要文档是软件需求规格软件需求规格说明书说明书。n软件需求规格说明书的特点： （1）正确性； （2）无岐义性； （3）完整性； （4）可验证性； （5）一致性； （6）可理解性； （7）可追踪性。需求分析阶段典型例题需求分析阶段典型例题8、需求分析的任务不包括（） A问题分析 B系统设计 C 需求描述 D 需求评审。9.软件的可行性研究中不包括（D）、法律可行性 、技术可行性 、经济可行性 、政治可行性10.软件生产过程中，需求信息由（D ）给出。 A、程序员 B、项目管理者 C、软件分析设计人员 D、软件用户11可行性研究要进行

54、一次（）需求分析。参考答案为:CA详细的B全面的C简化的、压缩的D彻底的*结构化分析方法（SA）n结构化方法的核心和基础是结构化程序设计理论。n结构化分析方法是一种建模技术建模技术（是需求分析的一种有是需求分析的一种有效方法，另一种是面向对象的方法效方法，另一种是面向对象的方法） 。其实质着眼于数据流，自顶向下，逐层分解自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。n结构化分析常用的工具：数据流图数据流图 数据字典数据字典 判定树判定树 判定表判定表 （有时也用结构化语言）*数据流图1.数据流图（DFD）：就是采用图形方式来表达系统的逻辑功能、数据

55、在系统内部的逻辑流数据在系统内部的逻辑流向向和逻辑变换过程，是结构化系统分析方法的主要表达工具。2.数据流图从数据传递和加工的角度，是描述描述数据处理过程的工数据处理过程的工。3.数据流图的基本元素 数据源（终点数据源（终点) 数据流数据流 处理处理(加工加工) 数据存储数据存储数据流图的基本符号的意思矩形表示数据的外部实体（数据源或终点）外部实体（数据源或终点）；圆角的矩形表示变换数据的处理（加工）处理（加工），加工过程至少要有一个输入流和输出流。少右面的边矩形表示数据存储数据存储； 箭头表示数据流，是数据的流向数据流，是数据的流向。例：数据流图（DFD）*处理过程至少有一个输入数据流和一个

56、输出数据流数据流程图上的每个元素都必须有名字。数据字典n数据字典（DD）:是关于数据的信息的集合，对数据流图中的各个元素进行完整的定义和说明。数据字典是一个预留空间，一个数据库，这是用来储存信息数据库本身。 n数据字典的作用数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。 n数据字典通常包含5个部分：数据项、数据结数据项、数据结构、数据流、构、数据流、数据存储数据存储和处理过程和处理过程 。n数据字典是结构化分析的核心。 结构化设计（SD）n从技术角度出发软件设计软件设计包括软件结构设计、数据设计、接口设计、过程设计。（每个设计的含义一定要记住，见P6！)n从结构化设计角度看，软

57、件设计软件设计分概要设计概要设计和详详细设计细设计两步完成。n1.概要设计，即总体设计。将需求分析得到的DFD转化为转化为软件系统结构和全局数据结构、确定数据库模式（即概要设计的功能）。n2.概要设计的工具是结构图结构图(SC）.结构图基本组成成分：模块、数据和调用.n3.结构图基本图符由上面的数据流图转化的SC图储户模块存钱模块其他模块取钱模块验证密码确认签字n详细设计即过程设计。功能是为软件结构图（SC）中的每一个模块确定采用的算法，模块内数据结构，用某种选定的表达工具（如N-S图等）给出清晰的描述。 n常用工具有：常用工具有：程序流程图、N-S图、PAD图、过程设计语言PDL(伪码)。详

58、细设计：详细设计：由SC图中的密码验证得到的N-S图 （右边是N-S图，左边是根据图写的代码）验证密码输入密码返回继续输入错误 正确可以取钱输入密码输入密码m mIf m=If m=123123 可以取钱可以取钱ElseElse 密码错误，密码错误，请重新输入请重新输入 需求分析的工具：需求分析的工具： （不要与方法弄混了，也不要与结构化分析工具弄混！） 问题分析图 （ PAD ）、程序流程图 （PFD ）、 N-S （也是一种流程图）也称为盒图，是程序流程图的一种改进是程序流程图的一种改进 。n程序流程图（程序流程图（PFDPFD）中的箭头代表的是）中的箭头代表的是：控制控制流流n数据流图中

59、的箭头代表：数据流图中的箭头代表：数据的流向数据的流向n结构图（结构图（sc):sc):箭头代表模块的调用箭头代表模块的调用备注：几个易混的知识点软件设计阶段典型例题软件设计阶段典型例题软件设计阶段典型例题软件设计阶段典型例题1.对在数据流图中每一个命令的图形元素均给以定义是（B）、条目定义、数据字典 、数据定义、数据说明2. 结构化程序设计理论认为，实现良好的程序结构要应用（ A ）的分析方法。 A、自顶向下 B、自底向上 C、面向对象 D、基于组件3.从事物的组成部件及每个部件的属性、功能来认识事物。这种方法被称为（A）的方法。A、面向对象 B、面向数据 C、面向过程 D、面向属性4.（D

60、）工具在软件详细设计过程中不采用。A判定表 BIPO图CPDLDDFD图5程序的三种基本控制结构的共同特点是参考答案为:DA不能嵌套使用B只能用来写简单程序 C已经用硬件实现D只有一个入口和一个出口6.从工程管理的角度软件设计可分为概要设计和（详细）设计两大步骤。7.流程图也称为程序框图是最常用的一种表示法，它有顺序、分支和（循环）三个基本控制构件。8.软件可靠性是指在给定的时间间隔内，程序成功运行的_概率_ 9. 软件工程时代的生产方式是（）化。10. 结构化设计以（）为基础映射成软件结构。软件结构是以（ ）为基础而组成的一种控制层次结构。软件测试n定义：定义：使用人工或自动手段来运行或测定

61、某个系统的过程，其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差别。n软件测试是为了发现错误而执行程序的过程是为了发现错误而执行程序的过程。（有时也（有时也解决存在的问题）解决存在的问题）n一个好的测试用例好的测试用例是指可能找到迄今为止尚未发现的错误的用例。n一个成功的测试成功的测试是发现了至今尚未发现的错误的测试，一般由输入数据和预期的输出数据两部分组成。 n测试用例应该包括合理的和不合理测试用例应该包括合理的和不合理的输入条件。测试技术与方法综述n从是否需要执行被测试软件的角度是否需要执行被测试软件的角度，可将测试分为静态测试和动态测试。 1.静态测试主要包括代码检查代

62、码检查、静态结构分析静态结构分析、代码质量度量代码质量度量等，它可以由人工进行 。 2.动态测试：动态测试是通常意义上的测试，也就是运行和使用软件。是根据软件开发的各是根据软件开发的各个阶段的规格说明和程序的内部结构而精心设个阶段的规格说明和程序的内部结构而精心设计的一批测试用例，计的一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。n按照功能划分，可将软件测试分为黑盒测试和按照功能划分，可将软件测试分为黑盒测试和白盒测试。（有时也称白箱和黑箱测试）白盒测试。（有时也称白箱和黑箱测试）测试技术与方法综述1.黑盒测试黑盒测试将测试对象看作一个黑盒，不考虑程序内部的逻辑结构和内部特

63、性，只依据程序的需求规格说明书需求规格说明书，检查程序的功能是否符合它的功能说明。这种测试又称为功能测试或这种测试又称为功能测试或数据驱动测试数据驱动测试。 黑盒测试的方法黑盒测试的方法：等价类划分法、边界值分析法、错误推测法、因果图法等。2.白盒测试白盒测试把测试对象看作一个透明的盒子，利用程序内部的逻辑机构及有关信息，设计或选择测试用例，对程序的所有对程序的所有逻辑路径进行测试逻辑路径进行测试。通过在不同点检查程序的状态，确定实际的状态是否与预期的一致。这种测试又称为结构测试或逻结构测试或逻辑驱动测试辑驱动测试。 白盒测试的方法白盒测试的方法：逻辑覆盖、基本路径测试 等。3.白盒和黑盒测试

64、有可能是动态测试，又有可能是静态测试。白盒和黑盒测试有可能是动态测试，又有可能是静态测试。软件测试的实施n软件测试按四个步骤（不同阶段不同阶段）进行：n单元测试：单元测试：对软件设计的最小单位模块进行正确性的测试，其目的是发现各模块内部可能存在的各种错误。其目的是发现各模块内部可能存在的各种错误。是在代码编写阶段可进行的测试，它是整个测试工作的基础测试工作的基础。n集成测试：集成测试：是测试和组装软件的过程，它是在把模块按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的主要目的是发现与接口有关的错误。错误。n确认测试：确认测试：任务是验证软件的功能和性能以及其他特性是否满是否满足了

65、需求规格说明中确定的各种需求，足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确。n系统测试：系统测试：系统测试是将已经确认的软件、计算机硬件、外设、网络等其他元素结合在一起，进行信息系统的各种组装测试和确认测试，其目的是通过与系统的需求相比较，发现所开发的系统与用户需求不目的是通过与系统的需求相比较，发现所开发的系统与用户需求不符或矛盾的地方，从而提出更加完善的方案。符或矛盾的地方，从而提出更加完善的方案。程序调试n程序调试的任务是诊断和修正程序中的错误。n调试的方法：n强行排错法n回溯法n原因排除法软件维护n定义：软件维护主要是指根据需求变化或硬件环境的变化对应用程序进行部分或全

66、部的修改，修改时应充分利用源程序修改后要填写程序改登记表，并在程序变更通知书上写明新旧程序的不同之处。 n分类： 1.适应性维护适应性维护 ：为适应软件运行环境的变化而修改软件的活动。 2.改善性维护：改善性维护：根据用户在软件使用过程中提出的建设性意见而进行的维护活动 。 3.纠错性维护：纠错性维护：为改正软件系统中潜藏的错误而进行的维护活动。 4.预防性维护预防性维护 ：为了改进应用软件的可靠性和可维护性，为了适应未来的软硬件环境的变化 而进行的维护活动。维护的副作用n维护的副作用有编码副作用、数据副作用、文编码副作用、数据副作用、文档副作用档副作用三种。1.编码副作用：编码副作用：在使用

67、程序设计语言修改源代码时，都可能引入错误。例如，删除或修改一个子程序、删除或修改一个标号、 删除或修改一个标识符等。2.数据副作用：数据副作用：在修改数据结构时，可能导致软件出错 。例如，在修改定义局部或全局常量、 重新定义记录或文件格式、增大或减小一个数组或数据结构的大小。3.文档副作用：文档副作用：对相关技术文档进行相应修改 而引起的错误。例如：用户对交互输入的顺序或格式进行修改 。软件测试维护阶段典型例题1.下列关于软件测试的叙述中错误的是（D）。（选择一项） A、软件测试可以作为度量软件与用户需求间差距的手段 B、软件测试的主要工作内容包括发现软件中存在的错误并解决存在的问题 C、软件

68、测试的根本目的是尽可能多地发现软件中存在地问题，最终把以个高质量地软件系统交给用户使用 D、没有发现错误地测试也是有价值的2.在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是_。(C)A. 循环的集合 B. 地址的集合 C. 路径的集合 D. 目标的集合3.在设计测试用例时，应当包括（C）、合理的输入条件 、不合理的输入条件、合理的和不合理的输入条件、部分条件4、与设计测试数据无关的文档是（D ）。 A、需求说明书 B、设计说明书 C、源程序 D、项目开发设计5.软件测试的目的是（）A 实验性运行软件 B找出软件中的错误 C证明软件正确 D 找出软件中的全部错误6.对于软件

69、测试分类，下列各项都是按照不同阶段来进行的划分，除了（C）。 A、单元测试 B、集成测试 C、黑盒测试 D、系统测试7.在设计测试用例时，应当包括（C） 、合理的输入条件 、不合理的输入条件 、合理的和不合理的输入条件、部分条件测试与维护阶段典型例题8.与设计测试数据无关的文档是（D ）。 A、需求说明书 B、设计说明书 C、源程序 D、项目开发设计9、为了进一步改善软件系统的可维护性和可靠性，并为以后的改进奠定基础的软件维护称为（D）。 A。纠错性维护 B适应性维护 C 改善性维护 D预防性维护10. 为适应软件运行环境的变化而修改软件的活动称为（B）。 A.纠错性维护 B适应性维护 C 改

70、善性维护 D预防性维护11、根据用户在软件使用过程中提出的建设性意见而进行的维护活动称为（C）。 A纠错性维护 B适应性维护 C改善性维护 D预防性维护12、为改正软件系统中潜藏的错误而进行的维护活动称为（A）。 A错性维护 B适应性维护 C 改善性维护D 预防性维护 13、以下不属于白盒测试技术的是（D） A 逻辑覆盖 B基本路径测试 C循环覆盖测试 D等价类划分14产生软件维护的副作用，是指（C）A开发时的错误B隐含的错误C因修改软件而造成的错误D运行时误操作15. 软件测试方法中（ ）属于静态测试。 A 黑盒法 B 路径覆盖 C 错误推测 D 人工检测测试与维护阶段典型例题16.黑盒测试

71、主要是测试软件是否满足（功能）需求 。17.程序设计语言的（可维护）性通常指这种语言编写的程序被理解，被修改及调整和改进的难易程度。18.软件测试是为了（ ）而执行程序的过程。19.软件测试的目的是尽可能的发现软件中错误，通常（ ）是在代码编写阶段可进行的测试，它是整个测试工作的基础。 20.若按功能划分，软件测试的方法通常分为白盒测试方法和（ ） 测试方法。 按软件是否被执行，软件测试分为（ ）和（ ）。21.测试用例应有（ ）和预期的输出数据两部分组成。这样便于对照检查。22.黑盒测试是（）测试，因此设计测试用例时，需要研究需求规格说明书和概要设计说明书中有关程序功能或输入、输出之间的关系

72、等信息。23.维护的副作用有编码副作用、（）、文档副作用三种。 24.程序（）的任务是诊断和修正程序中的错误。其方法有强行排错法、（）和回溯法。第四章 数据库设计基础n考试大纲n1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。知识点归纳n数据库的定义n1.长期存放在计算机内，有组织的有组织的、可共享可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储，具

73、有较小的较小的冗余度冗余度、较高的数据独立性和易扩展性数据独立性和易扩展性。 数据独立性包括：数据独立性包括：物理和逻辑独立性。物理和逻辑独立性。 物理独立性物理独立性是指用户的应用程序与存储在磁盘上的数据库中数据是相互独立的。即，数据在磁盘上怎样存储由DBMS管理，用户程序不需要了解。 逻辑独立性逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的，即，当数据的逻辑结构改变时，用户程序也可以不变。 n2.数据库还可以说成：是由一个互相关联的数据的集合互相关联的数据的集合和一组用以访问这些数据的程序访问这些数据的程序组成的。n3.数据库技术的根本目标是解决数据的共享问根本目标是解决数据的

74、共享问题。题。计算机数据管理技术发展的三个阶段n人工管理阶段人工管理阶段:数据不具有独立性,由应用程序管理数据本身。n文件系统阶段文件系统阶段:数据独立性和共享性差,由文件管理数据本身。n数据库系统阶段：数据库系统阶段：有较高的数据独立性和共享性，由数据库管理系统(DBMS)管理数据。数据库管理系统(DBMS)n数据库管理系统数据库管理系统是一个帮助用户创建和管理数据库用户创建和管理数据库的应用程序的集合应用程序的集合也就是一个可以帮助完成定义、构造和操纵数据库等处理目的的通用软件系统软件系统。其主要功能如下：n数据模式定义：数据模式定义：数据库存放数据的模式，即数据库中全体数据的逻辑结构和特

75、征的描述 。 n数据存取的物理构建：数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段 。n数据操纵：数据操纵：数据的查询、修改、删除、添加查询、修改、删除、添加四种操作。n数据的完整性、安全性定义和检查：数据的完整性、安全性定义和检查：n数据库的并发控制和故障恢复数据库的并发控制和故障恢复n数据的服务数据的服务n为完成上述功能，为完成上述功能，DBMS提供了相应的语言：提供了相应的语言：n数据定义语言数据定义语言(DDL) 数据操纵语言数据操纵语言(DML) 数据控制语言数据控制语言(DCL，用来设置或者更改数据库用户或角色权限的语句 )数据库系统n数据库系统是由数据库、

76、数据库管理系统、数数据库、数据库管理系统、数据库管理员、硬件平台和软件平台据库管理员、硬件平台和软件平台等几个部分组成的完整的运行实体。 DBS=DB+DBMS+DBAn数据库系统的特点n数据的集成性n数据的高共享性和低冗余性n数据的独立性n数据统一管理和控制数据库系统的内部体系结构n三级模式n外模式：外模式：又称为用户模式，是每个用户的局部数据描述，用户的数据视图.n概念模式：概念模式：数据库系统中全局数据逻辑结构的描述，全体用户的数据视图.n内模式：内模式：又称为物理模式，是数据库物理存储结构和物理存取方法的描述.n二级映射二级映射:保证了数据的物理独立性和逻辑独立性n概念模式到内模式的映

77、射 (物理独立性)n外模式到概念模式的映射(逻辑独立性)数据模型n数据模型数据模型是数据模型（Data Model）是数据特征的抽象，它是数据及其操作的一种抽象表示。数据模型描述的内容包括三部分：数据模型描述的内容包括三部分：n数据结构数据结构：主要描述数据的类型、内容、性质以及数据间的联系等。 n数据操作：数据操作：主要描述在相应的数据结构上的操作类型和操作方式 。如选择、投影、连接等。n数据约束：数据约束：主要描述数据结构内数据间的语法、词义联系 等。一个学生实体转换为关系模型n一学生： 姓名：张三；年龄：20；性别：男；班级：中文1；入学成绩：550。学生表：学生表：姓名 年龄性别班级入

78、学成绩张三 20男中文1550数据模型n数据模型数据模型按不同的应用层次分成三种类型三种类型： 概念数据模型、概念数据模型、 逻辑数据模型和物理数据模型逻辑数据模型和物理数据模型n概念数据模型：简称概念数据模型：简称概念模型，是面向现实世界的，其出发点是有效地模拟现实世界，给出数据的概念化结构。与具体的数据管理系统无关。概念数据模概念数据模型必须换成逻辑数据模型，才能在型必须换成逻辑数据模型，才能在DBMS中实现。中实现。 n实体联系模型实体联系模型是一种广泛使用的概念模型，该模型将现实世界的要求转化为实体实体、联系联系和属性属性等几个基本概念，并用ERER图图直观地表示出来。ER模型的基本概

79、念n实体：概念世界中的基本单位，它们是客观存在且能相互区别的事物。凡具有共性的实体可以组成一个集合称为实体集实体集。n属性：属性用来描述实体的特征。一个实体可以有多个属性，每个属性可以有值，一个属性的取值范围称为该属性的值域值域。n联系：联系反映概念世界中的实体集之间存在的一定关系。n一对一联系(1:1)n一对多联系(1:M)n多对多联系(M:N)ER图n实体用矩形实体用矩形表示，并在矩形中标明实体的名称。n属性用标有属性名属性用标有属性名称的椭圆称的椭圆表示，而且必须用线将属性与其所属的实体相连。n关系用标明关系名关系用标明关系名称的菱形表示称的菱形表示，关系的名称一般是动动词词。关系将相关

80、的实体连接在一起并在实体旁标注关系的基数。 课程选课成绩教师专业职称系开设拥有划分学生学号姓名物理数据模型 与逻辑数据模型n物理数据模型：简称物理模型，是面向计算机物理表示的模型，描述了数据在储存介质上的组织结构，数据在储存介质上的组织结构，它不但与具体的DBMS有关，而且还与操作系统和硬有关，而且还与操作系统和硬件有关。件有关。n逻辑数据模型：就是我们通常所说的数据模型，这是用户从数据库所看到的模型用户从数据库所看到的模型，是具体的DBMS所所支持的数据模型。支持的数据模型。n常用的数据模型（常用的数据模型（即逻辑数据模型即逻辑数据模型）有）有三种：三种：层次型、关系型和网状型。层次型、关系

81、型和网状型。层次模型 用树形结构表示数用树形结构表示数据及其之间联系的模据及其之间联系的模型，称为层次模型。型，称为层次模型。 层次模型中数据的层次模型中数据的联系象一棵倒置的树，联系象一棵倒置的树，树根、树叶都称为节树根、树叶都称为节点。节点是分层的，点。节点是分层的，树根是最高点。例如树根是最高点。例如家谱、单位编制等都家谱、单位编制等都是层次型结构是层次型结构。网状模型 用网状结构来表示数用网状结构来表示数据与数据之间联系的模型据与数据之间联系的模型称为网状模型。称为网状模型。 网状模型中，数据之间网状模型中，数据之间的联系象一张网，网上的的联系象一张网，网上的连接点称为节点，节点之连接

82、点称为节点，节点之间是平等的，不分层次。间是平等的，不分层次。例如一所学校中的教师、例如一所学校中的教师、学生、课程、成绩、教室学生、课程、成绩、教室的联系，就是网状型结构。的联系，就是网状型结构。关系模型的概念n关系模型以关关系系代代数数理理论论为基础，是当今广泛使用的数据库关系模型。n关系模型中数据的逻辑结构是具具有有唯唯一一的的名名称称一张二维表一张二维表，它由行和列组成。n属性属性（字段）：一列 Fieldn元组元组（记录）：一行 Recordn主关键字主关键字(码码):唯一标志元组的属性组(可以不是一个）为关键字。n域：域：属性的取值范围。关系模型的基本概念n 外关键字外关键字 ：

83、其他表的主关键字n 关系模式：关系模式：对关系的描述。 关系名（属性1，属性2，属性n） 例如：学生（学号，姓名，年龄，性别，系，年级）n关系模型：关系模型：通过关键字表示实体间联系的数据模型。关系的基本性质n元组的个数是有限的。n列是同质的，即每一列中的分量是同一类型同一类型的数据，来自同一个域同一个域。并且不可分解不可分解。n不同的属性要给予不同的属性名。n任意两个元组不能完全相同。n行和列的顺序无所谓，即行和列的次序可以任意交换。关系模型的数据操作n关系模型的数据操纵即建立在关系上的数据操纵（即关系操作），一般有查询、增加、删除及修改四种操作查询、增加、删除及修改四种操作。n关系模型的约

84、束n实体完整性约束：实体完整性约束：在关系中用主关键字来唯一标识一个实体，实体具有独立性，关系中的这种约束条件称为实体完整性。n参照完整性约束：参照完整性约束：关系之间相互关联的基本约束，不允许关系引用不存在的元组，即在关系中的外键要么是所关联关系中实际存在的元组，要么为空值。见下例n用户自定义完整性约束：用户自定义完整性约束：用户定义完整性约束是用户定义某个具体数据库所涉及的数据必须满足的约束条件，是由具体应用环境来决定的。例如，约定学生成绩的数据必须小于或等于100。参照完整性例子n例如，学生关系S和学校专业关系Z之间满足参照完整性约束。学校专业关系Z中的专业号属性是主关键字，同时它也存在

85、学生关系S中，那么只有当专业号存在，这个专业的学生才有可能存在，因此在添加学生关系中的元组时，定义的专业号必须在学校专业关系Z中已存在对应的元组。 系部专业专业号 学年证书工学院工学院自动化0014工学工学院工学院机械0024工学姓名年龄性别专业入学成绩张三20男001550关系运算n传统的集合运算，要求两个相同的关系模式n并、交、差并、交、差n专门的关系运算n选择：选择： 原关系的子集，水平分解n投影：投影： 抽取原关系的部分属性形成的新的关系，垂直分解n联接：联接： 根据给定的条件（共有属性）将两个关系拼成一个新的关系笛卡尔乘积 关系R（M个元组）和关系S（N个元组）进行笛卡尔乘积 运算后

86、，元组个数为M*NR S R*Sa b c a b c m 3 4 m 3 4 7 n 5 m 3 5 7 n 4 7 n 5数据库设计n数据库设计的基本任务是根据用户对象的用户对象的信息需求、处理需求信息需求、处理需求和数据的支持环境和数据的支持环境设计出数据模式。数据库的设计通常分为几个阶段：需求分析、概念设计、逻辑设计和物理设计。数据库设计n需求分析：这是数据库设计的第一个阶段，任务主要是收集和分析数据，这一阶段收集到的基础数据和数据流图是下一步设计概念结构的基础。 n概念设计：根据用户的需求，分析数据间内在语义关联，在此基础上建立一个数据的抽象模型，即形成E-R图。 方法有以下两种：n

87、集中式模式设计法：把集中式模式设计法：把需求说明综合成一个统一的需求说明，然后，在此基础上设计一个单位的全局数据模式。n视图集成设计法：是以各部分的需求说明为基础，分别设计各自的局部。然后把局部概念模式合并成一个完整的全局概念模式。 试图设计的策略有：自顶向下、自低向上、由内向外。试图设计的策略有：自顶向下、自低向上、由内向外。数据库设计n逻辑设计：主要工作是将ER图转换成指定的关系型数据库管理系统 (RDBMS)中的关系模式，并利用规范化理论对逻辑数据模型进行优化。 ER图中的实体和联系都可以表示成关系，ER图中的属性也可以转换成关系的属性。n物理设计：对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。 数据库管理n数据库的建立n数据库的调整n数据库的重组n数据库的保护：安全性控制与完整性控数据库的保护：安全性控制与完整性控制、数据的恢复、并发性控制。制、数据的恢复、并发性控制。n数据库监控人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。