计算机综合能力强化训练(公共基础)讲稿.ppt

1、2020年9月8日,1,时间与教室安排（1）,2020年9月8日,2,时间与教室安排（2）,2020年9月8日,3,注意事项,1.等级考试 时间：9月20日 笔试：90分钟，选择题+填空题（基础占30分） 上机：90分钟 win2000+vc+6.0 1、程序填空题（30分） 2、程序修改题（30分） 3、程序设计题（40分） 2.课程考试 时间：9月18日晚（第3周周四）18：45,2020年9月8日,4,相关资料,1 .教材 全国计算机等级考试二级教程公共基础知识 （2008年版）高等教育出版社 全国计算机等级考试二级教程C语言程序设计 （2008年版）高等教育出版社 2 .公共基础知识题

2、集 3 .笔试题集 4 .上机练习系统（南开100题） 5 .课程复习题（网络课堂）,计算机综合能力强化训练（C程序设计）,公共基础知识,2020年9月8日,6,公共基础知识基本要求,掌握算法的基本概念 掌握基本数据结构及其操作 掌握基本排序和查找算法 掌握逐步求精的结构化程序设计方法 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力 掌握数据库的基本知识，了解关系数据库的设计,2020年9月8日,7,一、基本数据结构与算法,算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念

3、。 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 线性单链表、双向链表与循环链表的结构及其基本运算。 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,2020年9月8日,8,1.1 算 法,算法：解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。 算法的的可解性：通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果。 算法不等于程序，也不

4、等于计算机方法，程序的编制不可能优于算法的设计；程序是算法的一种描述。 算法的基本特征： （1）可行性；与采用的特定计算工具和步骤有关。 （2）确定性，算法中每一步骤都必须有明确定义，不允许有 模棱两可的解释，不允许有多义性。 （3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义。 （4）拥有足够的情报，与输入的初始数据有关。,2020年9月8日,9,算法的基本要素：由两种基本要素组成 一是对数据对象的运算和操作；二是算法的控制结构。 计算机算法：计算机能处理的操作所组成的指令序列。 计算机算法的主要特征注重于算法的动态执行。 指令系统：一个计算机系

5、统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数 据传输。 算法的控制结构： 算法中各操作之间的执行顺序，算法的 基本框架。 描述算法工具：传统流程图、N-S结构化流程图、算法描述语言等； 算法的基本构成：顺序、选择、循环三种基本控制结构。 算法设计的基本方法： 列举法、归纳法、递推、递归、减半递推技术、回溯法。,2020年9月8日,10,算法复杂度：算法的时间复杂度和算法空间复杂度。 算法的时间复杂度：是指执行算法所需要的计算工作量。 用算法在执行过程中所需的基本运算次数来度量， 与问题的规模有关，是规模的函数； 与特定的输入有关，用平均性态分析和最坏情况复杂

6、性来分析， 但与使用环境无关。 算法的空间复杂度：是指执行这个算法所需要的内存空间。 包括：程序所占空间、输入初始数据所占空间、算法执行过程所需额外空间。 为了减少算法所占空间，通常采用压缩存储技术。,2020年9月8日,11,1.2 数据结构的基本概念,利用计算机进行数据处理需要考虑三个因素： 数据元素在计算机中的组织、数据处理的效率、存储空间。 数据处理的效率：一是提高数据处理速度，二是尽量节省在数据处理过程中所占用的存储空间。 数据结构研究的三个方面： （1）数据集合中各数元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储

7、结构； （3）对各种数据结构进行的运算。 数据处理：对数据集合中的各元素以各种方式运算和分析。 数据结构：指相互有关联的数据元素的集合。,2020年9月8日,12,一般情况下，在具有相同特征的数据元素（简称为元素）集合中，各元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱于直接后继关系）来描述 。 前后件关系是数据元素之间的一种基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般说，数据元素之间的任何关系都可以用前后件关系来描述。 1.数据的逻辑结构： 反映数据元素

8、之间逻辑关系的结构，包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 与数据元素在计算机中的实际存储位置无关。 其一般表示形式：,B=（D，R） B：数据结构；D：数据元素的集合；R前后件关系,2020年9月8日,13,2.数据的存储结构 数据的逻辑结构在计算机中的存储形式，也称物理结构； 在存储结构中，既要存放元素信息，又要存放元素之间的前后件关系信息，与逻辑结构不可能相同。 一种数据的逻辑结构根据需要可以表示成多种存储结构，且效率各不相同 常用的数据存储结构有：顺序、链接、索引等。 数据结构的表示：二元关系表示法、图形表示法。 线性结构特征： （1）有且只有一个根

9、结点； （2）每一个结点最多有一个前件，也最多有一个后件。 （3）特例：插入或删除一个结点后，仍然满足上述条件 非线性结构：不满足线性结构条件的数据结构。,2020年9月8日,14,1.3线性表及其顺序存储结构,线性表：线性结构称之为线性表，由n个数据元素构成的有序列，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，形成每个数据元素的若干相关数据项称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且

10、只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。,2020年9月8日,15,线性表的顺序储储结构具有以下两个基本特点： （1）线性表中所有元素所占的存储空间是连续的； （2）线性表中各数元素在存储空间中是按逻辑顺序依次存放的。 顺序存储结构的线性表中的元素地址由序号惟一确定 ai的存储地址为： ADR（ai）=ADR(a)+（i-1）*k， ADR（a）为第一个元素的地址，k代表每个元素占的字节数。 在程序设计语言中通常用一维数组来表示线性表。 线性表在顺序存储结构下的运算：插入、删除、查找、排序、分解、合并、复制、逆转。,2020年9月8日,16,顺序存储结构的优缺点 优点

11、逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素，平均移动一半的元素，在最坏的情况下，需要移动所有的元素。 预先分配空间需按最大空间分配，利用不充分。 表容量难以扩充。 对大的线性表及插入与删除操作频繁的情况，效率低，不方便。,2020年9月8日,17,1.4 栈和队列,栈：是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底位置。 在栈的存储空间S（1：m）中，S(bott

12、om)为栈底元素（非空情况）， S(top)为栈顶元素，top=0表示栈空；top=m表示栈满。 栈的基本运算： （1）插入：称为入栈运算，元素入在栈顶； （2）删除：称为退栈运算，元素从栈顶退出； （3）读栈顶元素是将栈顶元素给一个指定的变量，此时指针无变化。当top=0时，读不到栈顶元素。,2020年9月8日,18,队列及其基本运算 队列：是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向排头元素的前一个位置。程序设计语言中用一维数组表示。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算：包括 （1）入

13、队运算：从队尾插入一个元素；只涉及队尾指针rear的变化。 （2）退队运算：从队头删除一个元素。只涉及排头指针front的变化。 循环队列：队列的最后一个位置与第一个位置逻辑上环状连接，供队列循环使用。循环队列指针同队列指针。 循环队列的初始状态：rear=front=m 。 s=0表示队列空，s=1，非空，且front=rear表示队列满,2020年9月8日,19,循环队列的运算：入队运算和退队运算。 每进行一次入队运算，队尾指针进一；当rear=m+1时，则置rear=1，然后插入新元素至队尾（rear所指处）。 当s=1,且rear=front时，队列满，不能进行入队运算，此刻为“上溢”

14、。 每进行一次退队运算，排头指针进一；当front=m+1时，则置front=1。然后排头元素退队至变量， 当s=0, 队列空，不能进行退队运算，此刻为“下溢”。,2020年9月8日,20,1.5 线性链表,数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成： （1）一部分用于存储数据元素值，称为数据域； （2）一部分用于存放指针，称为指针域，用于指向前一个或后一个结点。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。,2020年9月8日,

15、21,链式存储方式即可用于表示线性结构，也可用于表示非线性结构（指针域可能不只一个）。 线性链表：线性表的链式存储结构。 在线性链表中，HEAD称为头指针，指向线性表的首存储结点。HEAD=NULL（或0）称为空表，线性链表的最后一个节点的指针域=NULL（或0）。 双向链表：节点指针为两个：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。 线性单链表：线性链表的指针域只有一个，且指向后节点，只能顺指针向链尾查找。 线性链表的基本运算：查找、插入、删除、合并、分解、逆转、复制、排序等。 线性链表在实际应用中经常以带链的栈或带链的队列出现。,2020年9月8日,22,循环链表

16、，其特点为： （1）在在循环链表中增加了一个表头接结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。 （2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针域构成一个环状链。 循环链表的基本运算：与线性单链表基本相同。 （1）在循环链表中，只要指出表中任何一个结点的位置，就可从它出发访问到表中其它所有结点，而线性单链表做不到这一点。 （2）在任何情况下，循环链表中至少有一个结点存在，非空表与空表运算统一。,2020年9月8日,23,1.6 树与二叉树,树的定义：一种简单的非线性结构，是n个结点的有限集

17、合；树结构中，所有元素之间具有明显的层次（前、后件）特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。,2020年9月8日,24,树结构中的分层原则 （1）根结点在第一层。 （2）同一层上所有结点的所有子结点都在下一层。 （3）在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。 （4）在树中，叶子结点没有子树。 用树结构来表示算术表达式的原则

18、 （1）表达式中的每个运算符对应树的一个结点（运算符结点）。 （2）每个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。 （3）运算对象中的单变量均为叶子结点。 表示一个表达式的表达式树是不惟一的。 树在计算机中通常用多重链表表示，链表中每个结点中的链域个数随树中该结点的度而定。,2020年9月8日,25,二叉树及其基本性质 二叉树：一种非线性数据结构，其特点为： (1）非空二叉树只有一个根结点；（2)每个结点最多只有两棵子树,且分别称为该结点的左子树、右子树(度最大为2，没有子树的结点为叶子结点，可以只有根结点）。 二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k

19、1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；,2020年9月8日,26,二叉树的基本形态,(1)空树,(1)仅有根,(3) 右子树空,(4) 左子树空,(5) 左、右子树均在,2020年9月8日,27,满二叉树与完全二叉树 1)满二叉树：指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点，深度为m的满二叉树有2m-1个结点。,2020年9月8日,28,2)完全二叉树：指除最后一层外，每一层上的结点数均达到最

20、大值，在最后一层上只缺少右边的若干结点。,对于完全二叉树中的任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的最大层次为p或p+1。 满二叉树也为完全二叉树，而完全二叉树不一定是满二叉树。,2020年9月8日,29,完全二叉树性质 （5）具有n个结点的完全二叉树的深度为log2n+1； （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号，则对于编号为k（k=1,2.n）的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为int(k/2)；若2kn，则编号为k的结点的左子结点编号为2k

21、；否则该结点无左子结点（也无右子结点）；若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 二叉树的存储结构 二叉树存储结构采用链式存储结构（二叉链表），每个存储节点的指针域有两个（一个指向左子结点，一个指向右子结点），对于满二叉树与完全二叉树可以按层序进行顺序存储（不适用一般二叉树）。,2020年9月8日,30,二叉树的遍历： 所谓二叉树的遍历，就是按某种顺序，不重复不遗漏地访问二叉树中的所有结点，使得每个结点仅被访问一次。 在先左后右的访问原则下，二叉树的遍历分： （1）前序遍历（DLR），若为空，则返回，否则首先访问根结点，然后遍历左子树，最后遍历右子树； （

22、2）中序遍历（LDR），若为空，则返回，否首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序遍历（LRD），若为空，则返回，否首先遍历左子树，然后遍历右子树，最后访问根结点。 三种遍历都是一个递归过程。,2020年9月8日,31,1.7 查找技术,查找：指在一个给定的数据结构中查找某个指定的元素。数据结构不同，采用的查找方法不同，主要为提高数据处理效率。 顺序查找（顺序搜索）的使用情况： （1）如果线性表为无序表，则不管是采用顺序存储结构还是链式存储结构，都只能顺序查找。 （2）即使是有序线性表，如果采用链式存储结构，也只能采用顺序查找。 （3）顺序查找平均要与一半的元素进行比较 ，

23、最坏则全部（n次）。 二分法查找：只适用于顺序存储的有序表，对于长度为n的序线性表，最坏情况只需比较二log2n次。,2020年9月8日,32,1.8 排序技术,排序：将一个无序序列整理成按值非递减顺序排列的有序序列；常用的排序方法如下： 交换类排序法：借助数据元素之间的相互交换进行排序。包括：（1）冒泡排序法，需要比较的次数为n(n-1)/2；（2）快速排序法（一次交换消除多个逆序）。 插入类排序法：指将无序序列中的各元素依次插入到已经有序的线性表中；包括（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O（n）次比较。 选择类排序法：扫描整个线性表，从

24、中选择出最小的放在表的最前面，对剩下的部分继续；包括（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O（nlog2n）次比较。,2020年9月8日,33,选 择 题,1.算法的时间复杂度是指(C ) A.执行算法程序所需要的时间 B.算法程序的长度 C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数 2.算法的空间复杂度是指(D )A.算法程序的长度 B.算法程序中的指令条数C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间 3.下列叙述中正确的是(A )A.线性表是线性结构 B.栈与队列是非线性结构C.线性链表是非线性结构

25、D.二叉树是线性结构,2020年9月8日,34,4.数据的存储结构是指( B )A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据 5.下列关于队列的叙述中正确的是(C )A. 在队列中只能插入数据 B.在队列中只能删除数据C.队列是先进先出的线性表 D.队列是先进后出的线性表 6.下列关于栈的叙述中正确的是(D )A.在栈中只能插入数据 B.在栈中只能删除数据C.栈是先进先出的线性表 D.栈是先进后出的线性表,2020年9月8日,35,7.设有下列二叉树: 对此二叉树中序遍历的结果为(B )A.ABCDEF B.DBE

26、AFC C.ABDECF D.DEBFCA 8.在深度为5的满二叉树中,叶子结点的个数为(C )A. 32B. 31 C. 16D. 15 9.对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为(B ) A. N+1 B. N C .(N+1)/2 D. N/2 10.设树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1 .则T的叶子结点数为(A ) A. 8 B. 7 C . 6 D. 5,2020年9月8日,36,填空题,1.对长度为n的有序线性表中进行二分查找,需要的比较次数为( log2n ) 2.设一棵完全二叉树共有700个结点,则在该二叉树中有(350)

27、个叶子结点 3.设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为(DEBFCA ) 4.在最坏情况下,冒泡排序的时间复杂度为 ( N(N-1)/2 ) 5. 在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有 ( 3 )个元素.,2020年9月8日,37,二、程序设计基础,程序设计方法与风格 结构化程序设计。 面向对象的程序设计方法，对象，方法，属性及继承与多态性。,2020年9月8日,38,2.1 程序设计方法和风格,程序：是具有特定功能的可执行的指令的集合。 程序设计方法： 定义：是指在设计程序过程中所采取的系

28、统的研究观点和方法。 两个阶段：结构化程序设计阶段和面向对象的程序设计阶段。 程序设计风格： 定义： 指编写程序时所表现出的特点、习惯和逻辑思路。 主导的程序设计风格是：“清晰第一、效率第二”。,2020年9月8日,39,形成良好的程序设计风格应考虑的因素： （1）源程序文档化： 符号名的命名：顾名思义。 程序注释：帮助读者理解程序，包括序言性注释、功能性注释 视觉组织：利用空行、缩进等使程序层次分明、便于阅读。 （2）数据说明的方法： 数据说明的秩序规范化：注意不同类型数据说明的次序。 说明语句中变量安排有序化：多个变量，应按字母顺序排列。 使用注释来说明复杂数据的结构。 （3）语句的结构：

29、 程序应简单、易懂、可读性强，语句构造应简 单直接，尽量采用功能单一的模块化结构，不应为提高效率 而把语句复杂化，优先保证程序正确性，尽可能使用库函数;避免不必要的转移;不修补不好程序,最好重新编写。 （4）输入和输出：输入和输出方式和格式应尽可能方便用户的使 用。,2020年9月8日,40,2.2 结构化程序设计,结构化程序设计的原则：1、自顶向下；2、逐步求精；3、模块化；4、限制使用goto语句。 结构化程序的基本结构与特点： （1）顺序结构：按照语句的自然顺序，逐条语句执行程序。 （2）选择结构：又称分支结构，可根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列，包括简单选择和

30、多分支选择结构， （3）重复结构：又称循环结构，根据给定的条件，判断是否需要重复执行某一相同或类似的程序段，依此简化程序行。分当型循环与只到型循环。,2020年9月8日,41,结构化程序设计原则和方法的应用 （1）使用三种基本控制结构表示程序的控制逻辑。 （2）选用的控制结构只准有一个入口和一个出口。 （3）程序语句组成容易识别的块，每块只有一个入口和一个出口，无死块(永远执行不到的操作块)。结构内的每一部分都有机会被执行到。 （4）复杂结构应用嵌套的基本控制结构进行组合签套来实现，无死循环(无终止的循环)。 （5）语言中所没有的控制结构，应采用前后一致的方法来模拟。 （6）严格控制GOTO语

31、句的使用。 结构化程序设计优点：程序易于理解、使用和维护；提高编程效率，降低开发成本。,2020年9月8日,42,2.3 面向对象的程序设计,面向对象方法的优点： （1）与人类习惯的思维方法一致； 传统程序设计方法：核心是算法，开发过程基于功能分析和功能分解。不重视数据与操作的内在联系，求解空间与问题空间不一致。 面向对象程序设计方法：核心是对象，并依此为中心构造系统，对象是由数据和数据的操作组成的封装体，与客观实体直接对应。 基本原理：按现实世界的方式思考问题从而解决问题。 （2）稳定性好； 现实世界中的实体是相对稳定的，因此以对象为中心构造的软件系统也是比较稳定的。 面向对象软件系统的结构

32、是根据问题领域的模型建立起来的，而不是根据系统应完成的功能的分解建立的。因此当系统功能需求变化时，不会引起软件结构的整体变化。,2020年9月8日,43,（3）可重用性好； 软件重用定义：指在不同的软件开发过程中重复使用相同或相似软件元素的过程，以提高软件生产率。 传统软件重用技术：利用标准函数库。但难以适应不同场合的不同需要，通常绝大多数函数都是新编的。 对象具有很强的自含性(数据和操作作为同等重要成分出现)和独立性(对象内部与外部实现了隔离)，对象提供了理想的模块化机制和可重用的软件成分。 利用可重用软件成分构造新软件系统时，具有很大灵活性。继承机制使子类可以重用其父类的数据结构和程序代码

33、，还可以修改和扩充。 （4）易于开发大型软件产品；软件成本降低,整体质量提高。 （5）可维护性好。开发的软件容易理解，稳定性好，容易修改，自然可维护性好，易于测试和调试。,2020年9月8日,44,面向对象方法的基本概念 对象：是对问题域中某个实体的抽象；面向对象的程序设计方法中，是构成系统的一个基本单位(一个窗口，一个菜单)。 对象的组成：由一组表示其静态特征的属性和它可执行的一组操作组成。 静态属性：对象包含的信息，在设计对象时确定，一般只能通过执行对象的操作来改变，不同对象的同一属性可以具有相同或不同的属性值。 操作（动态行为）：描述了对象执行的功能，通过消息传递，其过程对外封闭；操作也

34、称为方法或服务。 对象的基本的特点： （1）标识惟一性：由对象的内在本质来区分； （2）分类性；可以将具有相同属性和操作的对象抽象成类。 （3）多态性；同一个操作可以是不同对象的行为。 （4）封装性；从外面只能看到对象的外部特性，对象内部处理能力的实行和内部状态，对外是不可见的。 （5）模块独立性好：对象内部各元素彼此结合紧密，内聚性强。,2020年9月8日,45,对象是由描述对象属性的数据和施加于这些数据之上的所有操作封装在一起的统一体。 类：指具有共同属性、共同方法的对象的集合(将属性、操作相似的对象归为类 )。 所以类是对象的抽象，一个对象是对应类的一个实例（一个具体的对象）。 组成：类

35、是关于对象性质的描述。包括一组数据属性和在数据上的一组合法操作。 消息：是一个实例与另一个实例之间传递的信息。 作用：面向对象的软件系统中，是通过对象之间彼此协作来完成任务的，对象间的相互合作需要一个机制消息。作用类似于函数调用。 消息的组成：（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。 消息传递：发送(消息)对象的触发操作产生输出结果，传送至接收对象，引发接收对象一系列的操作。,2020年9月8日,46,继承：指能够直接获得已有类的性质和特征，而不必重复定义他们。 类组成层次结构的系统：一个类上层可以有父类(基类)，下层有子类(派生类)。一个类直接继承其父

36、类的描述或特性，子类自动地继承父类的数据和方法。 继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类，功能更强，使用更方便。 优点：相似对象可共享程序代码和数据结构，提高软件可重用性。 开发新系统时不必从头开始，可以继承已有系统的功能或从类库中选取需要的类。 多态性：指同样的消息被不同的对象接受时可导致完全不同的行动。 优点：增加了灵活性、软件的可重用性和可扩充性。利用多态性，用户能够发送一般形式的消息，而将所有细节都由接收(消息)的对象实现。,2020年9月8日,47,选择题,1.结构化程序设计主要强调的是(B )A.程序的规模B.程序的易读性 C.程序的

37、执行效率D.程序的可移植性 2.对建立良好的程序设计风格，下面描述正确的是(A)A.程序应简单、清晰、可读性好 B.符号名的命名只要符合语法C.充分考虑程序的执行效率 D.程序的注释可有可无 3.在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送(D)A.调用语句B.命令C.口令D.消息 4.信息隐蔽的概念与下述哪一种概念直接相关？(B )A.软件结构定义B.模块独立性 C.模块类型划分D.模块耦合度 5.下面对对象概念描述错误的是(A)A.任何对象都必须有继承性B.对象是属性和方法的封装体C.对象间的通讯靠消息传递D.操作是对象的动态属性,2020年9月8日,48,填空题,1.结

38、构化程序设计的三种基本逻辑结构为顺序、选择和（重复 ） 2.源程序文档化要求程序应加注释。注释一般分为序言性注释和（功能性注释） 3.在面向对象方法中，信息隐蔽是通过对象的（ 封装）性来实现的 4.类是一个支持集成的抽象数据类型，而对象是类的（实例） 5.在面向对象方法中，类之间共享属性和操作的机制称为（继承）,2020年9月8日,49,三、软件工程基础,软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。 结构化分析方法，数据流图，数据字典，软件需求规格说明书。 结构化设计方法，总体设计与详细设计。 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试

39、和系统测试。 程序的调试，静态调试与动态调试。,2020年9月8日,50,3.1软件工程基本概念,区分两组容易混淆名词： 程序：根据用户需求开发、用程序设计语言描述、适合计算机执行的指令序列，软件的组成部分。 软件（定义）：包括程序、数据和相关文档的完整组合。 国标定义：与计算机系统的操作有关的计算机程序、规 程、规则以及可能有的文件、文档及数据。 软件组成 (1)机器可执行的程序和数据 (2)机器不可执行的，与软件开发、运行、维护和使用等 有关的文档。 分类：系统软件、应用软件和支撑软件(或工具软件)。 程序设计：只是软件开发过程中的必要环节。 软件开发：还包括需求分析、概要和详细设计、软件

40、测试、 运行和维护等多个环节。,2020年9月8日,51,软件的特点包括： （1）软件是一种逻辑实体，不是物理实体，具有抽象性，通过思维理解其功能、性能。 （2）软件生产不同于硬件，没有明显的制作过程，开发成功后可以大量复制，其质量控制体现在软件开发上。 （3）运行、使用期间不存在磨损、老化问题。 （4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。 （5）软件复杂性高，成本昂贵； （6）软件开发涉及诸多的社会因素。 软件按功能分为应用、系统、支撑软件（或工具软件）。 软件危机 定义：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题,涉及成本、质量

41、、生产率等问题。 作用:为了消除软件危机，逐步形成了软件工程概念，开辟了工程学新兴领域_软件工程学。,2020年9月8日,52,软件工程 国标定义：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序，即软件开发工作步骤。 软件工程包括3要素： (1) 方法：完成软件工程项目的技术手段。 (2) 工具：支持软件的开发、管理和文档生成。 (3) 过程：支持软件开发的各个环节的控制、管理。 软件工程过程 定义：是把输入转化为输出的一组彼此相关的资源和活动。 软件工程过程包含4种基本活动： （1）P软件规格说明；规定软件的功能及其运行时的限制。 （2）D软件开发；产生满足规格

42、说明书的软件。 （3）C软件确认；确认软件满足用户的需求。 （4）A软件演进。满足用户在使用中的变更要求。,2020年9月8日,53,软件生命周期 定义：软件产品从提出、实现、使用维护到停止使用退役的过程。一般包括可行性研究与需求分析、设计实现、测试、交付使用以及维护等活动。 软件生命周期的三个阶段: 软件定义：(1)可行性研究与计划制定：确定开发目标和总的要求，给出功能、可靠性等可能方案，制定实施计划。 (2)需求分析：对软件需求进行分析并给出详细定义，编写软件规格说明书及初步的用户手册，提交评审。 软件开发：(3)软件设计：概要设计和详细设计，给出软件的结构、模块和功能的划分等。编写概要设

43、计、详细设计说明书和测试计划初稿。 (4) 软件实现：源程序编码，把软件设计转换成计算机可以接受的程序代码。编写用户手册、操作手册和单元测试计划。 (5)软件测试：设计测试用例，检验软件各个组成部分。编写测试分析报告。 运行维护： (6) 软件投入运行，维护(进行扩充和删改)。,2020年9月8日,54,软件工程的目标和与原则： 目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。 基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开

44、发，及时交付使用。 软件工程基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,2020年9月8日,55,软件工程的理论和技术性研究 内容主要包括：软件开发技术和软件工程管理。 软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境；主体内容为方法学。 软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。 软件管理学包括：人员组织、进度安排、质量保证、配置管理、项目计划等。 软件工程经济学：用经济学的基本原理来研究软件开发中的经济效益问题，包括成本估算、成本效益分析等。 软件心理学：从个体心理、人类行为、组织行为和企业文化等角度来研究软件管理和

45、软件工程。,2020年9月8日,56,软件开发工具与软件开发环境 软件开发工具：是用于帮助软件开发人员开发和维护软件的一类特殊软件，它可以大大提高软件开发的效率，促进软件开发方法的进步和完善，由单项开发工具的开发逐渐过渡到继承开发工具的发展。 软件开发环境：是全面支持软件开发全过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个阶段和各项任务的完成。 CASE：计算机辅助软件工程集成软件工程环境。,2020年9月8日,57,3.2结构化分析方法,软件开发方法：软件开发过程所应遵循的方法和步骤。包括：分析方法、设计方法、程序设计方法。 结构化方法的核心和基础是：

46、结构化程序设计理论。 需求分析 软件需求：指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。 需求分析定义：开发人员准确理解用户的要求，调查分析，将用户非正形的需求陈述转化为完整的需求定义，再转换到相应的需求格式说明的过程。 任务：发现需求(用户需要软件做什么)、求精、建模和定义需求的过程。 需求分析将创建所需的数据模型、功能模型和控制模型。,2020年9月8日,58,需求分析阶段的工作(四方面)： (1)需求获取：目的是确定系统各方面需求。与用户交流、沟通全面地提炼出系统的功能性与非功能性需求。 (2)需求分析：对获取的需求分析和综合，给出系统解决方案和逻辑模型。 (3)编写需求

47、规格说明书：为用户、设计人员的交流提供方便，还可作为控制软件开发进程的依据。 (4)需求评审：复审需求分析阶段的工作，验证需求文档的一致性、可行性等。 需求分析方法：结构化分析方法和面向对象的分析方法,2020年9月8日,59,结构化分析方法 定义：结构化分析是使用数据流图(DFD)、数据字典(DD)、结构化英语、判定表和判定树等工具，建立一种新的、称为结构化规格说明的目标文档。” 实质：面向数据流，自顶向下、逐层分解，以数据流图和数据字典为主要工具，建立系统的逻辑模型。 主要步骤(五步)： (1) 获取当前系统的具体模型 (2) 抽象出当前系统的逻辑模型 (3) 建立目标系统的逻辑模型 (4

48、) 编写目标系统的软件需求规格说明 (5) 评审直到确认完全符合用户对软件的需求 结构化分析的常用工具 （1）数据流图； （2）数据字典； （3）判定树； （4）判定表。 数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。,2020年9月8日,60,基本符号(四种)： 步骤(三步)： (1)由外向里：先画系统输入/输出，再画系统的内部。 (2)自顶向下：顺序完成顶层、中间层、底层数据流图。 (3)逐层分解。 先建立顶层 数据流图,包含：相关外部实体及它们与软件中间的数据流 作用：描述软件作用范围、总体功能、输入/输出等,2020年9月8日,61,数据字典

49、：结构化分析方法的核心，对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。 作用：对DFD中出现的被命名的图形元素的确切解释。数据字典与DFD共同构成了系统的逻辑模型。 定义数据的基本符号：,2020年9月8日,62,判定树：从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。 优点：更加直观，易于理解和使用。 判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由

50、于某一组条件取值的组合而引发的，使用判定表描述比较适宜。 判定表组成(四部分)： (1) 基本条件，各种可能的条件 (2) 条件项，各种可能的条件组 (3) 基本动作，所有的操作 (4) 动作项，对应的条件组合下所选的操作,2020年9月8日,63,软件需求规格说明书 定义：是需求分析阶段的最后成果,软件开发的重要文档之一。它对所开发的软件的功能、性能、用户界面及运行环境等进行详细说明。 作用：便于用户与开发人员交流；作为软件开发的依据；作为测试和验收的依据。 内容：制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他有关数据。 特点： （1）正确性； （2）无岐义性；（3）完整性；

51、（4）可验证性； （5）一致性； （6）可理解性； （7）可理解性； （8）可追踪性。,2020年9月8日,64,3.3结构化设计方法,软件设计的基础 定义：是把软件需求转换为软件表示的具体过程，即模块结构的过程。 软件设计的基本目标：是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型。 软件设计的重要性： （1）软件开发阶段（设计、编码、测试）占成本的主要部分，是形成软件质量的关键环节。 （2）是将需求准确地转化为完整的软件产品或系统的唯一途径。 （3）所作出的决策，最终影响软件实现的成败。 （4）设计是软件工程的基础 从技术观点来看，软件设计包括：软件结构设

52、计、数据设计、接口设计、过程设计。,2020年9月8日,65,结构设计：定义软件系统各主要部件之间的关系。 数据设计：将分析时创建的模型转化为数据结构的定义。 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。 过程设计：把系统结构部件转换成软件的过程描述。 从工程管理角度来看，软件设计分成两部完成： 概要设计：也称结构设计，将软件需求转化为软件体系结构、确立系统级接口、全局数据结构或数据模式。 详细设计：确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。 软件设计的一般过程：是一个迭代过程，先进行高层次结构设计；再进行低层次过程设计；穿插数据设计和接

53、口设计。,2020年9月8日,66,软件设计的基本原立 (1)抽象：抽出事物的本质特性而不考虑其他细节。考虑模块划分解决方案时，可定多个抽象级别，从概要到详细逐步降低。 (2)模块化：指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。 (3)信息隐蔽：模块内包含的信息，不允许其他不需要这些信息的模块访问。即每个模块的实现细节对其他模块来说是隐蔽的。 (4)模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。,度量标准,耦合性：模块间互相连接的紧密程度。 内聚性：一个模块内部各个元素间彼此结合的紧密程度。 内聚性越强，独立性越好。,高内聚 低耦合,

54、结构化设计方法的基本思想：将软件设计成由相对独立且具有单一功能的模块组成的结构 。,2020年9月8日,67,概要设计及结构图,基本任务(四点)：,(1)设计软件系统结构,需求分析阶段：已将系统分解成层次结构。 概要设计阶段：进一步划分为模块以及模块的层次结构。,(2)数据结构及数据库设计：实现需求定义和规格说明过程中提出的数据对象的逻辑表示 。,(3)编写概要设计文档：包括概要设计说明书、数据库设计说明书，集成测试计划等。,(4)概要设计文档评审,2020年9月8日,68,结构图,作用：软件结构设计工具。反映系统的功能实现以及模块与模块之间的联系与通信，即反映了系统的总体结构。,基本成分：模

55、块、数据和调用,基本图符：,基本形式：,结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。,2020年9月8日,69,基本术语：,深度：在多层次的结构图中，其模块结构的层次数 (控制的层数) 宽度：同一层模块的最大模块数(控制跨度) 扇出：一个模块直接调用的其他模块数目 扇入：调用一个给定模块的模块个数。 上级模块，从属模块：上下两层模块a和b， a调用b。 a是上级模块， b是从属模块。,2020年9月8日,70,数据流图到结构图的变换,结构化设计方法的任务就是把需求分析得到的数据流图变换为结构图。,(1)数据流图到结构图的变换, 交换型：信息沿输入通路进入系统,同时由外部形式变

56、换成内部形式,进入系统的信息通过变换中心,经加工处理以后再沿输出通路变换成外部形式离开软件系统。,变换型数据处理的工作过程分三步:取得数据、变换数据、输出数据。,变换型系统结构图分三部分:输入、中心变换、输出。, 事务型：数据流的特点是接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元 (事务处理中心)，然后给出结果。,2020年9月8日,71,例图：,2020年9月8日,72,例图：,2020年9月8日,73,(2)面向数据流设计方法的实施要点与设计过程,分析确认数据流图的类型，区分是事务型还是变换型。,说明数据流的边界,将数据流图映射为程序结构图,事务流：区分事务中心和数据

57、接收通路，映射成事务结构 变换流：区分输出和输入分支，映射成变换结构,对产生的结构细化和求精,2020年9月8日,74,详细设计及工具,详细设计任务：为软件结构图中的每一个模块确定其实现算法和局部数据结构，并用某种选定的表达工具表示算法和数据结构的细节。,设计工具：,图形工具：程序流程图、N-S图、问题分析图(PAD图) 表格工具：判定表 语言工具： PDL(伪码语言),(1) 程序流程图：由一些描述不同种类操作的带有文字说明的图框和流程线构成。,优点：直观清晰，易于掌握 缺点：随意转移控制，且不易表示结构,2020年9月8日,75,(2) N-S图：去掉流程线，全部算法写在一个矩形框内。,(

58、3) PAD图：用结构化程序设计思想表现程序逻辑结构，描述软件详细设计。,特征,结构清晰、结构化程度高；易于阅读。 最左端纵线是程序主干线，每增加一层向右扩展一条纵线（纵线数等于程序层次数）。 程序执行：从最左端主干线上端点起，自上而下，从左向右执行。终止于最左端主干线。,(4) PDL图：过程设计语言，也称结构化英语或伪码。采用英语词汇和结构化程序设计语言的语法。,2020年9月8日,76,3.4软件测试,3.4.1 软件测试的目的与准则,1.目的：是为了发现错误而执行程序的过程。,2.准则(六点)：,(1)所有测试都应追溯到需求:最严重的错误为程序无法满足用户需求。 (2)严格执行测试计划

59、，排除测试的随意性。 (3)注意测试中的群集现象，程序中存在错误的概率与该程序中已发现的错误数成正比，应集中对付那些错误群集的程序。 (4)程序员应避免检查自己的程序。 (5)穷举测试不现实(穷举测试是指把程序所有可能的执行路径都进行检查的测试)。 (6)妥善保存测试计划、测试用例、和最终分析报告等。,2020年9月8日,77,3.4.2 软件测试方法,研究内容：如何用最少的测试用例集合来测试出程序中更多的潜在错误。,关键技术：如何进行彻底的测试，如何设计测试用例等。,分类：,1.静态测试与动态测试(是否需要执行被测软件),(1)静态测试：包括代码检查、静态结构分析、代码质量度量等。可以由人工进行或软件工具自动进行。,(2)动态测试：设计一批测试用例，利用它们去运行程序，以发现程序错误的过程。,测试用例：为测试设计的数据。由测试输入数据和与之对应的预期输出结果组成。 格式 (输入值集) , (输出值集) ,2020年9月8日,78,2.白盒测试与黑盒测试(按照功能划分)