2022年2022年计算机等级考试二级基础知识 .pdf

《2022年2022年计算机等级考试二级基础知识 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机等级考试二级基础知识 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、页眉内容1 第一章数据结构与算法一、算法1、算法：是指解题方案的准确而完整的描述。2、算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。3、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。4、算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。5、指令系统：一个计算机系统能执行的所

2、有指令的集合。6、基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。7、算法的控制结构：顺序结构、选择结构、循环结构。8、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。9、算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。二、数据结构的基本基本概念1、数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。2、数据结构是指相互有关联的数

3、据元素的集合。3、数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。4、数据的存储结构有顺序、链接、索引等。5、线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。6、非线性结构：不满足线性结构条件的数据结构。三、线性表及其顺序存储结构1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 19 页 -页眉内容2、在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。3、非空线性表的结构特

4、征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n 称为线性表的长度，当n=0 时，称为空表。4、线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai 的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k 代表每个元素占的字节数。5、顺序表的运算：插入、删除。（详见 14-16 页）四、栈和队列1、栈是限定在一端进行插入与删除的

5、线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。2、栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用 top 表示栈顶位置，用bottom 表示栈底。3、栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。4、队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear 指针指向队尾，front 指针指向队头。5、队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退

6、队运算：从队头删除一个元素。6、循环队列：s=0 表示队列空，s=1 且 front=rear 表示队列满五、线性链表1、数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。2、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。3、链式存储方式即可用于表示线性结构，也可用于表示非线性结构。4、线性链表，HEAD 称为头指针，HEAD=NULL（或 0）称

7、为空表，如果是两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。线性链表的基本运算：查找、插入、删除。六、树与二叉树名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 19 页 -页眉内容3 1、树的基本概念在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。树的最大层次称为树的深度。2、在一个算术表达式中，有运算符和运算对象。一个运算符可以有若干个

8、运算对象。例职，取正（+）等只有一个运算对象，称为单目运算符；二个运算对象称为双目运算符，三目运算符。用树来表示算术表达式的原则如下：表达式中的每一个运算符在树中对应一个结点，称为运算符结点。运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。运算对象中的单变量均为叶子结点。3、二叉树及其基本性质（1）什么是二叉树二叉树是一种很有用的非线性结构。二就树具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结

9、点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。可以没有其中的一个，也可以全没有。（2）二叉树的基本性质性质 1：在二叉树的第K 层上，最多有（K1）个结点。性质 2：浓度为M 的二叉树最多有2m-1 个结点。深度为 m 的二叉树是指二叉树共有m 层。性质 3：在任意一棵二叉树中度为0 的结点（即叶子结点）总是比度为2 的结点多一个。性质 4：具有 n 个结点的二叉树，其深度至少为 log2n+1,其中 log2n 表示取的整数部分。(3)满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。满二叉树所谓满二叉树是指这样的一种二叉树；除最后一层外，每一

10、层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K 层上有 2K-1 个结点，且深度为m 的满二叉树有2m-1 个结点。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 19 页 -页眉内容(4)完全二叉树所谓完全二叉树是指这样的二叉树，除最后一层外，每一层上的结点数均达的最大值；在最后一层上只缺少右边的若干结点。确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行边疆编号，则深度为m、且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为m 的满二叉树中编号从1 到 n 的结点一一对应时，称之为完全二叉树。对

11、于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为 p，或为 p+1。由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下两个性质：性质 5：具有 n 个结点的完全二叉树的深度为 log2n+1。性质 6：设完全二叉树共有n 个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n 给结点进行编号，则对于编号为k（k=1,2,n）的结点有以下结论：若 k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT

12、(k/2)。若 2kn，则编号为k 的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若 2k+1n，则编号为k 的结点的右子结点编号为2k+1；否则该结点无右子结点。(5)二叉树的存储结构(6)二叉树的遍历二叉树的遍历是指不重复地访问二叉树的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。前序遍历（DLR）所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。F，C，A，D，B，E，G，H，P 中序遍历（LDR）所谓中序

13、遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。A，C，B，D，F，E，H，G，P 后序遍历（LRD）所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。A，B，D，C，H，P，G，E，F 七、查找技术1、顺序查找名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 19 页 -页眉内容5 顺序查找又称顺序搜索。顺序查找一般是

14、指在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。顺序查找的效率是很低的。以下两种情况只能采用顺序查找：如果线性表无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2、二分法查找二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，但允许相邻元素值相等）。设有序线性表的

15、长度为n，被查元素为x，则对分查找的方法如下：将 x 与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若 x 小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若 x 大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n 的有序线性表，在最坏情况下，二分查找只需要比较log2n 次，而顺序查找需要比较n 次。八、排序技术1、交换类排队序

16、法所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。（1）冒泡排序法基本过程如下：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。放最大值然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序。放最小值。重复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序。假设线性表的长为n，则在最坏情况下，冒泡排序需要经过n/2

17、遍的葱馨往后的扫描和 n/2 遍的从后往前的扫描，需要的比较的次数为n(n-1)/2。（2）快速排序法名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 19 页 -页眉内容快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。基本思想如下：从线性表中选取一个元素，设T，将线性表后面小于T 的元素移到前，而前大于T 的元素移支后面，结果就将线性表分成了两部分（称为两个子表），T 插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T 为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均

18、不小于T。如此反复，则此时的线性表就变成了有序表。步骤：首先，在表的第一个，中间一个与最后一个元素中选取中项，设为P（K），并将 P（K）赋给 T，再将表中的第一个元素移到P（K）的位置上。然后设置两个指针i 和 j 分别指向表的起始与最后的位置。反复操作以下两步：（4）将 j 逐渐减小，并逐次比较P（j）与 T，直到发现一个P(j)T 为止，将P(i)移到 P(j)位置上。上述两个操作交替进行，直到指针i 与 j 指向同一个位置（即i=j）为止，此时将 P(i)的位置上。分割需要记忆，用栈来实现。2、插入类排序法（1）简单插入排序法所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线

19、性表中。一般来说，假设线性中前j-1 元素已经有序，现在要将线性表中第j 个元素插入到前面的有序子表中，插入过程如下：将第 j 个元素放到一个变量T 中，然后从有序子表的最后一个元素（即线性表中第 j-1 个元素）开始，往前逐个与T 进行比较，将大于T 的元素均依次向后移动一个位置，直到发现一个元素不大于T 为止，此时就将T（即原线性表中的第j 个元素）插入到刚移出的空位置上，有序子表的长度就变为j 了。效率与冒泡法相同在最坏情况下，简单插入排序需要n(n-1)/2 次比较。（2）希尔排序法基本思想如下：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量H

20、 的元素构成一个子序列。在排序过程中，逐次减小这个增量，最 后 当H 减 到1 时，进 行 一 次 插 入 排 序，排 序 就 完 成。增 量 序 列 一 般 取h=n/2k(k=1,2,log2n,其中 n 为待排序序列的长度。其效率与增量序列有关。在最坏情况下，需要的比较次数为O（N 1.5）。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 19 页 -页眉内容7 3、选择类排序法（1）简单选择排序法基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。简单选择排序法在最坏情况下需要比较n(n-1)/2/次。（2）

21、堆排序法方法：首先将一个无序序列建成堆。然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1 个元素构成的子序，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆。反复做第（2）步，真到剩下的子序列为空为止。适用规模较大的线性表，在最坏情况下，堆排序需要比较的次数为O（nlog2n）。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 19 页 -页眉内容第 2 章程序设计基础一、程序设计方法与风格就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。（一）程序设计风

22、格一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应该强调得意和清晰，程序必须是可以理解的。要形成良好的程序设计风格，主要应注重和考虑下述一些因素。1、源程序文档化2、源程序文档化应考虑如下几点：（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。（2）程序注释：下克的注释能够帮助读者理解程序。（3）礼堂组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧使程序层次清晰。（二）数据说明的方法在编写程序时，需要注意数据说明的风格，以便使程序中

23、的数据说明更易于理解和维护。一般应注意如下几点：（1）数据说明的次序规范化鉴于程序理解、新闻记者和维护的需要，使数据说明次序固定，可以使数据的发生容易查找，也有利于测试、排错和维护。（2）说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺序为好。（3）使用注释来说明复杂数据的结构。(三)语句的结构程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应注意如下：（1）在一行内只写一条语句；（2）程序编写应优先考虑清晰性；（3）除非对效率有特殊要求，程序编写要做清晰第一，效率第二；（4）首先要保证程序正确，然后才要求提高速度；（5）避免使用临时变量而使程

24、序的可读性下降；（6）避免不必要的转移；（7）尽可能使用库函数；（8）避免采用复杂的条件语句；（9）尽量减少使用“否定”条件的条件语句；（10）数据结构要有利于程序的简化；（11）要模块化，使模块功能尽可能单一化；名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 19 页 -页眉内容9（12）确保每一个模块的独立性；（13）从数据出发去构造程序；（14）不要修补不好的程序，要重新编写；（四）输入和输出无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应该考虑如下原则：（1）对所有的输入数据都要检验数据的合法性；（2）检查输入项的各种重要组合的合理性；（3）输

25、入格式要简单，以使得输入的步骤和操作尽可能简单；（4）输入数据时，应允许使用自由格式；（5）应允许缺省值；（6）输入一批数据时，最好使用输入结束标志；（7）在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输入出加注释，并设计输出报表格式。二、结构化程序设计（一）构化程序设计的原则结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用 goto 语句。1、自顶向下：程序设计时，应先考虑总体，后考虑细节；先考

26、虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。2、逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。3、模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。4、限制使用goto 语句（二）结构化程序的基本结构与特点1、顺序结构：顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序。2、选择结构：选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根

27、据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。3、重复结构：重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。分为两类：一是先判断后执行，一是先执行后判断。优点：一是程序易于理解、使用和维护。二是编程工作的效率，降低软件开发成本。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 19 页 -页眉内容（三）结构化程序设计原则和方法的应用要注意把握如下要素：1、使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。2、选用的控制结构只准许有一个入口和一个出口；3、程序语句组成容易识别的块

28、，每块只有一个入口和一个出口；4、复杂结构应该嵌套的基本控制结构进行组合嵌套来实现；5、语言中所没有的控制结构，应该采用前后一致的方法来模拟；6、严格控制GOTO 语句的使用。其意思是指：（1）用一个非结构化的程序设计语言去实现一个结构化的构造；（2）若不使用GOTO 语句会使功能模糊；（3）在某种可以改善而不损害程序可读性的情况下。三、面向对象的程序设计（一）关于面向对象方法面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域，也就是说，系统中的对象以及对象之间的关系能够如实地反映问题

29、域中固有事物及其关系。优点：1、与人类习惯的思维方法一致2、稳定性好3、可重用性好软件重用是指在不同的软件开发过程中重复作用相同或相似软件元素的过程。重用是提高软件生产率的最主要的方法。4、易于开发大型软件产品5、可维护性好（1）用面向对象的方法开发的软件稳定性比较好（2）用面向对象的方法开发的软件比较容易修改；（3）用面向对象的方法开发的软件比较容易理解。（4）易于测试和调试。（二）面向对象方法的基本概念1、对象（object）对象是面向对象方法中最基本的概念。对象是对问题域中某个实体的抽象，设立某个对象就反映软件系统保存有关它的信息并具有与它进行交互的能力。对象可以做的操作表示它的动态行为

30、，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务。属性即对象所包含的信息，它在设计对象时确定，一般只能通过挂靠对象的操作来改变。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 19 页 -页眉内容11 操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。操作的过程对外是封闭的，即用户只能看到这一操作实施后的结果。这相当于事先已经设计好的各种过程，只需要调用就可以了，用户不必去关心这一过程是如何编写的。事实上，这个过程已经封装在对象中，用户也看不到。对的这一特性即是对象的封装性。2、类（Class）和实例(Instance)类是具有共同属性、共同方法

31、的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。例如：Integer 是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，而一个具体的整数“123”是类 Integer 的实例。由类的定义可知，类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。3、消息（Message）消息是一个实例与另一个实例之间传递信息，它请示对象执行某一处理或回答某一要求的信息，它统一了数据流的控制流。消息的使用类似于函数调用，消息中指定了某一个实例，一个操作名和一个参数表（可空）。接收消息的实例执行消息中指定的操

32、作，并将形式参数数与参数表中相应的值结合起来。消息传递过程中，由发送消息的对象（发送对象）的触发操作产生输出结果，作为消息传送至接受消息的对象（接受对象），引发接受消息的对象一系列的操作。所传送的消息实质上是接受对象所具有的操作/方法名称，有时还包括相应参数。通常，一个消息由下述三部分组成：（1）接收消息的对象的名称；（2）消息标识符（也称为消息名）；（3）零个或多个参数。4、继承（Inheritance）继承是面向对象的方法的一个主要特征。广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。继承具有传递性，如果类C 继承类 B，类 B 继承类 A，则类 C 继承类 A。因此一

33、个类实际上继承了它上层的全部基类的特性，也就是说，属于某类的对象除了具有该类所定义的特性外，还具有该类上层全部基类定义的特性。继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。多重继承的类可以组合多个父类的性质构成所需要的性质。5、多态性（Polymorphism）对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 19 页 -页眉内容第 3 章软件工程基础一、软件工程基本概念（一）软件定义与软件特点计算机软件是计算

34、机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。基中，程序是软件开发人员根据用户需求开发的用程序设计语言描述的、适合计算机执行的指令（语句）序列。数据是使程序能正常操纵信息的数据结构。文档是与程序开发、维护和使用有关的图文资料。可见软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）。应用软件：为解决特定领域的应用而开发的软件。系统软件：计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件。支撑软件：介于系统软件和应用软件之间，协助用户

35、开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件。（二）软件危机与软件工程软件工程概念的出现源自软件危机。所谓有软件危机四伏是泛指在计算机软件开发和维护过程中所遇到的严重问题。具体地说，在软件开发和维护过程中，软件危机主要表现在：（1）软件需求的增长得不到满足。用户对系统不满意的情况经常发生。（2）软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生。（3）软件质量难以保证。（4）软件不可维护或护程度非常低。（5）软件的成本不断提高。（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率等问题。软

36、件工程就是试图用工程、科学和数学的大批量与方法研制、维护计算机软件的有关技术及管理方法。软件工程包括3 个要素：即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件工程的核心思想是把软件产品看作是一个工程产品来处理。（三）软件生命周期通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。软件生命周期的主要活动阶段是：名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 19 页 -页眉内容13（1）可行性研究与计划制定。确定

37、待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。（2）需求分析。对待开发软件提出的需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。（3）软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块和划分、功能的分配及处理流程。在系统比软件复杂的情况下，设计阶段可分解成概要设计阶段和详细设计阶段。编写概要设计说明书、详细设计说明书和测试计划初稿，提交评审。（4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写

38、单元测试计划。（5）软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。（6）运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新进出的需求进行必要而且可能的扩充和删改。（四）软件工程的目标与原则1、软件工程的目标软件工程的目标是，在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程需要达到的基本目标应是：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付使用。2、软件工程的原则为了

39、达到上述的软件工程目标，在软件开发过程中，必须遵循软件工程的基本原则。这些基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。（1）抽象。抽取事物最基本的特性和行为，忽略非本质细节。采用分层次抽象，自顶向下，逐层细化的办法控制软件开发过程的复杂性。（2）信息隐蔽。采用封闭技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。（3）模块化。模块是程序中相对独立的成分，一个独立的编程单位，应有良好的接口定义。模块的大小要适中，模块过大会使模块内部的复杂性增加，不得对模块的理解和个性也不得模块的调试和重用。模块太小会导致整个系统表示过于复杂，不利于控制系统的复杂性。（4）

40、局部化。要求在一个物理模块内集中逻辑上相互关联的计算资源，保证模块间具有松散的耦合关系，模块内部有较强的内骤性，这有助于控制角的复杂性。（5）确定性软件开发过程中所有概念的表达应是确定的、无歧义且规范的。这有助于人与人的交互不会产生误解和遗漏，以保证整个开发工作的协调一致。（6）一致性。指程序、数据和文档的整个软件系统的各模块应使用已知的概念、名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 19 页 -页眉内容符号和术语；程序内外部接口应保持一致，系统规格说明与系统行为应保持一致。（7）完备性。软件系统不丢失任何重要成分，完全实现系统所需的功能。（8）可验证性。开发大型软件系统

41、需要对系统自顶向下，逐层分解。系统分解应遵循容易检查、测评、评审的原则，以确保系统的正确性。二、结构化分析方法1、关于结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。对于面向数据流的结构化分析方法，按照DeMarco 的定义，“结构化分析就是使用数据流图（DFD）、数据字典（DD）、结构化英语、判定表和羊定树等工具，来建立一种新的、称为结构化规格说明的目标文档。”结构化分析方法的实质是着眼于数据流、自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具建立系统的逻辑模型。2、结构化分析的常用工具(1)数据流图（DFD Data Flow Diagram

42、）数据流图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。数据流图中的主要图形元素与说明如下：加工（转换）。输入数据经加工变换产生输出。（2）数据字典（DD Data Dictionary）数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。数据字典中有4 中类型的条目：数据流、数据项、数据存储和加工（3）判定树使用判定树进行描述时，应先从问题定义的文字描述

43、中分清哪些是判定的条件，哪些是判定的结论，根据模仿材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。（4）判定表判定表与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的联欢会，即完成该加工的一组动作是由于某一组条件联欢会的组合而引发的，使用判定表描述比较适宜。判定表由四部分组成，基本条件，条件项，基本动作，动作项（三）软件需求规格说明书软件需求规格说明书（SRS,software Requirement Specification）是需求分析阶段的最后成果，是软件开发中的文档之一。软件需求规格说明书的特点正确性。体现待开发系统的真实要求。无歧义性。对每一个需

44、求只有一种解释，其陈述具有惟一性。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 19 页 -页眉内容15 完整性。包括全部有意义的需求，功能的、性能的、设计的、约束的，属性或外部接口等方面的需求。可验证性。描述的每一个需求都是可以验证的，即存在有限代价的有效过程验证确认。一致性。各个需求的描述不能矛盾。可理解性。需求说明书必须简明易懂，尽量少包含计算机的要领和术语，以便用户和软件人员都能接受它。可修改性和课追踪性。每一个需求的来源、流向是清晰的，当产生和改变文件编制时，可以方便地引证每一个需求。三、软件设计（一）软件设计的基本概念1、软件设计的基础软件设计是软件工程的重要阶段

45、，软件设计是确定系统的物理模型。从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。结构设计是定义软件系统各主要部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信；过程设计则是把系统结构部件转换成软件的过程性描述。2、从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。概要设计（又称结构设计）将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。（二）软件设计的基本原理1、软件设计遵循软

46、件工程的基本目标和原则，建立了适用于在软件设计中应该遵循的基本原理和与软件设计有关的概念。（1）抽象软件设计中考虑模块化解决方案时，可以定出多个抽象级别。抽象的层次从概要设计到详细设计逐步降低。（2）模块化模块化是指把一个待开发的软件分解成若干个小的简单的部分。模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。（3）信息隐蔽名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 19 页 -页眉内容信息隐蔽是指，在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。（4）模块独立性模块独立性是指，每个模块只完成系统要求的独立的子功能，

47、并且与其他模块的联系最少且接口简单。是评价设计好坏的重要度量标准。2、衡量软件的模块独立性作用耦合性和内聚性两个定性的度量标准（1）内聚性：内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。内聚有如下的种类，它们之间的内聚性由弱到强排列为：偶然内聚逻辑内聚时间内聚过程通信内聚顺序内聚功能内聚（2）耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口。耦合可以分为下列几种，它们之间的耦合度由高到低排列为：内容耦合公共耦合外部耦合控制耦合标记耦合数据耦合非直接耦合在程序结构中，各模块的内聚性越强

48、，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有得提高模块的独立性。四、软件测试（一）软件测试的目的Grenford J.Myers 给出了软件测试的目的：软件测试是为了发现程序中的错误而执行程序的过程；一个好的测试用例子指很可能找到迄今为止尚未发现的错误的用例；一个成功的测试是发现了至今尚未发现的错误的测试。Myers 的观点告诉人们测试要以查找错误为中心，而不是为了演示软件的正确功能。（二）软件测试的准则1、所有测试都应追溯到需求软件测试的目的是发现错误，而最严惩的错误不外乎是导致程序无法满足用户需求的错误。2、严格执行测试计划

49、，排除测试的随意性。软件测试应当制定明确的测试计划并按照计划执行。测试计划应包括：所测软件的功能、输入和输出、测试内容、各项测试的目的和进度安排、测试资料、测试工具测试用例的选择、资源要求、测试的控制方式和过程等。3、充分注意测试中的群集现象经验表明，程序中存在错误的概率与该程序中已发现的错误数成正比。这一现象说明，为了提高测试效率，测试人员应该集中对付那些错误群集的程序。4、程序员应避免检查自己的程序为了达到好的测试效果，应该由独立的第三方来构造测试。因为从心理学角度讲，程序人员或设计方在测试自己的程序，要采取客砚的态度是程序不同地存在障碍的。名师资料总结-精品资料欢迎下载-名师精心整理-第

50、 16 页，共 19 页 -页眉内容17 5、穷举测试不可能所谓穷举测试是指把程序所有可能的执行路径都进行检查的测试。但是，即使规模较小的程序，其路径排列数也是相当大的，在实际测试过程中不可能穷尽每一种组合。这说明，测试只能证明程序中有错误，不能证明程序中没有错误。6、妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。（三）软件测试技术与方法综述若从是否需要执行被测软件的角度，可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法1、静态测试与动态测试（1）静态测试静态测试包括代码检查、表态结构分析、代码质量度量等。代码检查包括代码审查、代码走查、桌面检