国二《公共基础知识》--修改后讲稿

第一章 数据结构与算法 1.1算法 1.1.1算法

算法：是指解题方案的准确而完整的描述。通常不用计算机程序来直接描述算法，而是用别的描述工具，如程序流程图，专门的算法描述语言，甚至用自然语言。 1. 算法的基本特征

（1）可行性：算法总是在一个特定的计算工具上执行的，因此算法往往受到计算工具的限制，使执行结果产生偏差。所以在设计一个算法时，必须要考虑它的可行性，否则不会得到满意的结果。

（2）确定性：指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

（3）有穷性：是指算法必须在有限的时间内做完。即算法必须能在执行有限个步骤之后终止。例如计算无穷级数的算法，只能是有穷的。满足精度要求即可结束。

（4）拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。即不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行错误。

综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 2. 算法的基本要素

主要有两种：一是对数据对象的运算和操作，二是算法的控制结构 （1）算法中对数据的运算和操作

有四类：

1）算术运算：主要是加、减、乘、除等 2）逻辑运算：主要是与、或、非等

3）关系运算：主要是大于、小于、等于、不等于等 4）数据传输：主要是赋值、输入、输出等

（2）算法的控制结构：顺序结构、选择结构、循环结构

一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架。

包括三种：顺序结构、选择结构、循环结构。一个算法可以用这三种结构组合而成。 例如：计算1+2+3+ +100 1.1.2算法的复杂度

包括时间复杂度和空间复杂度。 1. 算法的时间复杂度

是指执行算法所需要的计算工作量。用基本运算次数来度量。 在分析算法工作量时，必须对问题的规模进行度量。

在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：

1）平均态性：是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 2）最坏情况复杂性：是指在规模为n时，算法所执行的基本运算的最大次数。显然它更容易计算。其实就是给出了算法工作量的一个上界。因此更有实用价值。 2. 算法的空间复杂度

是指执行算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储空间，及算法执行过程中所需要的额外空间。 1.2数据结构的基本概念 1.2.1什么是数据结构

是指相互有关联的数据元素的集合。 主要研究和讨论以下三个方面的问题：

1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。

2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 3）对各种数据结构进行的运算。

讨论以上问题的主要目的是为了提高数据处理的效率。主要包括两方面：一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。 1. 数据元素

数据元素：数据元素具有广泛的含义，一般来说，现实世界中存在的一切个体都是数据元素。例如：

描述一年四季的季节名：春、夏、秋、冬 家庭成员的成员名：父亲、儿子、女儿 表示数值的各个数：18、11、35、23、16...

总之，在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素，简称为元素。 一般情况下，在具有相同特征的数据元素中，各个数据元素之间是存在某种关系的（关联），它也就反映了数据元素所固有的一种结构，在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系来描述（直接前驱与直接后继关系）。

例如：在考虑一年四季的顺序关系时，春是夏的前件，夏是春的后件，夏是秋的前件，秋是夏的后件。

考虑家庭成员辈分关系时：父亲是儿子和女儿的前件，儿子和女儿是父亲的后件。 2. 数据的逻辑结构

数据结构是指反映数据元素之间关系的数据元素的集合，所以，数据结构包括两方面的信息：

（1）数据元素。

（2）各个数据元素之间的前后件关系（逻辑关系）。 用二元组方式描述数据结构：

数据元素的集合用D表示。

数据元素之间的前后件关系用R表示。 B表示数据结构

B=（D，R）

例如：一年四季数据结构

B=（D，R）

D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）} 又如：家庭成员数据结构

B=（D，R）

D={父亲，儿子，女儿} R={（父亲，儿子），（父亲，女儿）} 3. 数据的存储结构

在实际进行数据处理时，被处理的数据元素总是被放在计算机的存储空间中，并且，各

数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（物理结构）。 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。 1.2.2数据结构的图形表示

一个数据结构除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据元素用中间标有元素值的方框表示，称之为数据结点，简称为结点。对于数据元素的前后件关系，用一条有向线段从前件结点指向后件结点。

一年四季数据结构

家庭成员关系数据结构 在数据结构中，没有前件的结点称为根结点。没有后件的结点称为终端结点（叶子结点）。

除了根结点和终端结点，其它结点称为内部结点。

通常，一个数据结构中的结点可能是在动态变化的，根据需要可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。

不仅结点的个数在动态变化，各数据元素之间的关系也可能在动态地变化。 1.2.3线性结构与非线性结构

如果一个数据结构中一个数据元素都没有，则称为空的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，将数据结构分为两大类：线性结构和非线性结构。

1. 线性结构—顺序表、栈、队列、线性链表

若非空的数据结构满足两点，则称为线性结构（又称为线性表）： （1）有且只有一个根结点。

（2）每个结点最多有一个前件，也最多有一个后件。

所以，一年四季数据结构是线性结构，家庭成员数据结构是非线性的。 2. 非线性结构－树、二叉树

如果一个数据结构不是线性结构，它一定是非线性结构。

1.3线性表及其顺序存储结构 1.3.1线性表的基本概念

线性表是最简单、最常用的一种数据结构，是由n个数据元素组成的一个有限序列，表中的每个数据元素，除了第一个外，有且只有一个前件，除最后一个外，有且只有一个后件。线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。（矩阵也是一个线性表，可以将矩阵的每一行看成一个元素） 1.3.2线性表的顺序存储结构

在计算机中存放线性表，最简单的方法是顺序存储（顺序表），有两个特点： 1）线性表中所有元素所占的存储空间是连续的；

2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 1.3.3顺序表的插入运算

如果已满，再插入元素则称为上溢。 1.3.4顺序表的删除运算

1.4栈和队列 是线性结构，是线性表

栈：先进后出（FILO），计算栈中元素个数：bottom - top + 1

栈：是一种线性结构，在这种特殊的线性结构中，其插入和删除运算都是在一端进行。即一端是封闭的，不允许插入和删除元素；另一端是开口的，允许插入与删除元素。

开口的一端称为栈顶，封闭的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。其运算规则是：先进后出（FILO）或后进先出（LIFO），通常用指针top来指示栈顶的位置，用指针bottom指向栈底。

往栈中插入一元素称为入栈运算，从栈中删除一个元素称为退栈运算。 例如：入栈顺序是A、B、C、D，以下不可能的出栈顺序有？

① D、C、B、A ② A、B、C、D

入栈 出栈 ③ A、C、B、D

↓ ↑ ④ C、A、B、D

栈顶 top →a n

1. 栈的顺序存储及其运算 ┇ a 2 top=0表示栈空，top=m表示栈满（注：m为栈的最大

栈低bottom→a 1 容量）。

栈的三种基本运算：入栈、退栈、读栈顶元素

1）入栈运算：首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置。 2）退栈运算：首先将栈顶元素赋给一个变量，然后将栈顶指针退一。 3）读栈顶元素：将栈顶元素赋给一个变量。 计算栈中元素个数：bottom - top + 1 1.4.2队列

1. 队列：先进先出（FIFO）

是一种线性结构，它在一端插入，而在另一端删除。允许插入元素的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头，通常用一个排头指针（front）指向排头元素的前一个位置。在队列中，队尾指针rear和排头指针front共同反映了队列中元素动态变化的情况。

它是按照先进先出（FIFO）或后进后出（LILO）的原则组织数据，在队尾插入元素，在队头删除元素。

在队尾插入一个元素称为入队运算；在队列的排头删除一个元素称为退队运算。 计算队列中元素个数： rear - front

入对入队

图1.11 具有6个元素的队列示意图

2. 循环队列及其运算

队列的顺序存储结构一般采用循环队列的形式。

循环队列：就是将队列存储空间的最后一个位置绕到第一个位置，即存储空间的第一个位置作为队尾，形成逻辑上的环状空间，供队列循环使用。

循环队列的初始状态为空，即rear=front=m

循环队列主要有两种基本运算：入队运算与退队运算。

入队运算：队尾指针进一，当队尾指针rear=m+1时，则置rear=1。 退队运算：排头指针进一，当排头指针front=m+1时，则置front=1。

所以当rear=front时，循环队列可能满，也可能空。所以还需要增加一个标志s，s=0时表示队列空，s=1时表示队列非空。

1）入队运算：指在循环队列的队尾加入一个新元素，首先将队尾指针进一，当rear=m+1时，置rear=1；然后将新元素插入到队尾指针指向的位置。

当队列满时不能入队运算。

2）退队运算：首先排头指针进一，当front=m+1时，置front=1；然后将排头指针所指向的元素赋给指定变量。

当队列空（s等于0）时不能退队运算。

问：栈和队列的共同点是：都在端点处插入和删除元素。 计算非空循环队列中元素个数：

①front＜rear时， rear - front

②front≥rear时， m- (rear - front) 1.5线性链表 1. 线性链表

线性表的链式存储结构称为线性链表。

在链式存储结构中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个结点或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点，线性链表中最后一个结点的指针域为空。当HEAD为0时为空表。

i

12345678910

(a) 线性链表的物理状态

(b) 线性链表的逻辑状态

HEAD

2. 带链的栈 3. 带链的队列

图1.18 线性链表例

1.5.2线性链表的基本运算（插入与删除）

不发生数据元素移动的现象，只需改变有关结点的指针即可。 1.5.3循环链表及其基本运算

特点：

1）增加了一个表头结点，其指针域指向第一个结点。头指针指向表头结点。 2）最后一个结点的指针域不是空，而是指向表头结点。 1.6

非线性表：树与二叉树 1.6.1树的基本概念

图1.28 书的层次结构树树一种非线性结构。在树结构中，所有数据元素之间有明显的层次特性。

在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。

每个结点可以有多个后件，它们称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件个数称为该结点的度。所以叶子结点的度为0。 所有结点中的最大的度称为树的度。 树的分层原则是： （1）根结点在第1层

（2）同一层上所有结点的所有子结点都在下一层

树的最大层次数称为树的深度。

在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。 叶子结点没有子树。 1.6.2二叉树及其基本性质

1. 二叉树――（支持子程序调用的数据结构）

非空二叉树具有以下两个特点： （1）只有一个根结点

（2）每一个结点最多有两棵子树，且分别称为该结点的左子树、右子树。

所以，在二叉树中，每一个结点的度最大为2。 2. 二叉树的基本性质

性质1：在二叉树的第k层上，最多有2k-1个结点 性质2：深度为m的二叉树，最多有2m-1个结点

性质3：二叉树中，度为0的结点（叶子结点）总比度为2的结点多一个 性质4：具有n个结点的二叉树，其深度至少为[log2n]+1 例如：利用性质3

1、一棵二叉树共有25个结点，其中5个是叶子结点，则度为一的结点数为多少啊 二叉树中，度为0的结点（即叶子节点）比度为二的结点多1个，而度为0、1、2的结点相加等于总结点数25，所以度为1的节点数为25-5-（5-1）=16

2、一个二叉树的叶子节点是70，树上有80个度是1的结点，请问总共多少个结点。请说明具体算法

叶子结点数（度为0的节点数）=度为2的节点数 + 1 所以，度为2的节点数 = 69

总结点数=度为0的节点数 + 度为1的节点数 + 度为2的节点数 =70 + 80 + 69 =219 3. 满二叉树

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点的二叉树。就是说，在

k-1

满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2个结点，且

m

深度为m的满二叉树有2-1个结点。

(a) 深度为2的满二叉树

(b) 深度为3的满二叉树(c) 深度为4的满二叉树

4. 完全二叉树

图1.32 满二叉树

完全二叉树：除最后一层外，每一层上的结点数都达到了最大值的二叉树，并且在最后

一层上只缺少右边的若干结点。

满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

(a) 深度为3的完全二叉树

(b) 深度为4的完全二叉树

图1.33 完全二叉树

性质5：具有n个结点的完全二叉树，其深度为[log2n]+1

性质6：设完全二叉树共有n个结点，如果从根结点开始，按层序（第一层从左到右）用自然数1、2 n对结点编号，则对于编号为k的结点有以下结论：

1）若k=1，则该结点为根，它没有父结点；若k＞1，则该结点的父结点的编号为int（k/2） 2）若2k≤n，则编号为k的结点的左子结点编号为2k。

3）若2k+1≤n，则编号为k的结点的右子结点编号为2k+1。

A

C

BEA

C

HD

BE

A

CF

G

FD

深度为3的完全二叉树

1.6.3二叉树的存储结构

通常采用链式存储结构。

对于满二叉树与完全二叉树，可以按层序进行顺序存储。 1.6.4二叉树的遍历

遍历是指不重复地访问二叉树中的所有结点。

有三种遍历的方式，分别是前序遍历，中序遍历，后序遍历。 1. 前序遍历（DLR）－根左右

是指在访问根结点，遍历左子树与遍历右子树三者中，首先访问根结点，然后遍历左子树，最后遍历右子树，并且在遍历左右子树时，遵循前序遍历的顺序。 2. 中序遍历（LDR）－左根右

是指在访问根结点，遍历左子树与遍历右子树三者中，首先遍历左子树，然后访问根结点，最后遍历右子树，并且在遍历左右子树时，遵循中序遍历的顺序。 3. 后序遍历（LRD）－左右根

是指在访问根结点，遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且在遍历左右子树时，遵循后序遍历的顺序。

图1.33 完全二叉树

1.7查找技术

查找：指在一个给定的数据结构中查找某个指定的元素。 1.7.1顺序查找

顺序查找：在线性表（a1，a2， ，an）中查找指定的元素。

查找方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

查找效率：最好查找1次，最坏查找n次，平均查找n/2次。

适用场合：对于大的线性表，顺序查找的效率是很低的。但在下列两种情况下也只能采用顺序查找：

（1）对于无序线性表，无论链式存储结构或顺序存储结构，只能用顺序查找。 （2）对于有序线性表，若用链式存储结构，也只能用顺序查找。（顺序存储结构的可用二分法查找） 1.7.2二分法查找

适用场合：只适用于顺序存储的有序表（有序：从小到大，允许相邻元素值相等）。14 1，5，9，14，16，78，90，105，200

查找方法：设有序线性表的长度为n，被查元素为x，则对分查找的方法如下：

①将x与线性表的中间项进行比较；

②若中间项的值等于x，则说明查到，查找结束；

③若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找； ④若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找； ⑤这个过程一直进行到查找成功或子表长度为0（说明查找失败）为止。 查找效率：每次去掉一半，效率高。最好1次，最坏log2n次。 小结：

1.8排序技术

排序：指将一个无序序列整理成按值非递减顺序排列的有序序列。

如： 3 1 2 6 5 —→ 1 2 3 5 6 1.8.1交换类排序法：

1. 冒泡排序法

冒泡排序法是通过相邻两元素的交换逐步将线性表变成有序。基本过程如下：

①从表头开始往后扫描线性表，逐次比较相邻两个元素，将小的元素留在前面，大的换到后面。最后就将线性表中的最大元素换到了表的最后。

②从后到前扫描剩下的线性表，同样，逐次比较相邻两个元素。将大的元素留在后面，小的换到前面。最后就将剩下线性表中的最小元素换到了表的最前面（象气泡一样冒到表的前头）。

③对剩下的线性表重复①②过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。

例：对无序序列（5 1 7 3 1 6 9 4 2 8 6）排序 最坏比较次数为：n(n-1)/2 2. 快速排序法

快速排序法比冒泡排序法的速度快，其基本思想如下： ①从线性表中选取一个元素（一般选第1个元素），设为T，将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，结果就将线性表分割成了两个子表，T位于分界线处，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。

②对分割后的各子表按上述原则再进行分割，直到所有子表为空为止，则此时的线性表就变成了有序表。

例：对无序序列（5 1 7 3 9 4 2 8 6）排序 最坏比较次数为：n(n-1)/2 1.8.2插入类排序

1. 简单插入排序法

插入排序是将无序序列中的各元素依次插入到已经有序的线性表中。其基本思想如下： 在线性表中，只包含第1个元素的子表显然可以看成是有序表，从线性表的第2个元素到最后一个元素看成是无序表，逐次将其中的每一个元素插入到前面已经有序的子表中。

例：对无序序列（3 1 5 8 6 2）排序 最坏比较次数为：n(n-1)/2 2. 希尔排序法

希尔排序法是对简单插入排序做了较大的改进，其基本思想如下：

将相隔某个增量h的元素构成一个子序列，整个无序序列被分割成若干个这样的小的子序列，分别进行插入排序。在排序过程中，逐次减小这个增量。最后当h减到1时，进行一次插入排序，排序就完成。

例：对无序序列（7 19 24 13 31 8 82 18 44 63 5 29）排序 最坏比较次数为：O(n1.5) 1.8.3选择类排序法

1. 简单选择排序法

选择排序法的基本思想如下：

扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。

例：对无序序列（89 21 56 48 85 16 19 47）排序 最坏比较次数为：n(n-1)/2 2. 堆排序法

1）堆：具有n个元素的序列（h1，h2， ，hn）当满足

hi h2i

hi h2i 1

或

hi h2i

hi h2i 1

（i=1，2， ，n/2）称之为堆。本节只讨论满足前者条件的堆。 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。

2）堆的存储与表示：在实际处理中，可以用一维数组H（1

：

n）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。例如，序列（91，85，53，36，47，30，24，12）是一个堆，它所对应的完全二叉树如右图所示。由图看出，在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左、右子树的根结点值，因此，堆顶（完全二叉树的根结点）元素必为序列的n个元素中的最大项。

3）调整建堆：在一棵具有n个结点的完全二叉树（用一维数组H（1：n）表示）中，假设结点H(m)的左右子树均为堆，现要将以H(m)为根结点的子树也调整为堆，称为调整建堆。

4）调整建堆的方法：总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。

（a）

（b）

（c）

图1.42 调整建堆示意图5）堆排序的方法如下：

①首先将一个无序序列建成堆；

②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。

③反复做第②步，直到剩下的子序列为空为止。 最坏比较次数为：O(nlog2n)

第二章 程序设计基础

2.1程序设计方法与风格

程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。 程序设计方法有结构化程序设计和面向对象的程序设计。（填空题）

除了好的程序设计方法和技术之外，程序设计风格也是很重要的。因为程序设计风格会深刻地影响软件的质量和可维护性。好的设计风格的核心就是“清晰第一，效率第二”。（选择题）

要养成良好的程序设计风格，主要应注重和考虑下述一些因素。 1．源程序文档化（填空/选择题）

（1）符号名的命名：符号要有一定的实际含义

（2）程序要有注释。注释一般分为序言性注释（一般于程序段前）和功能性注释（一般于语句行尾）。序言性注释一般位于程序的开头部分，它给出程序的整体说明。功能性注释一般嵌在源程序体中，主要描述其后的程序或语句做什么

（3）视觉组织：可以在程序中利用空格、空行、缩进使程序层次清晰 *功能是：。。。。。。。。。 Public s

S=0 && s 存放累加和 For i=1 to 100 &&for ..

S=s+i Endfor

?s &&输入结果

2．数据说明的方法

（1）数据说明的次序规范化 （2）说明语句中变量安排有序化 （3）使用注释来说明复杂的数据结构 3．语句的结构

（1）一行内只写一条语句 （2）编程时优先考虑清晰性

（3）程序编写要做到清晰第一，效率第二 （4）首先保证程序正确，然后才要求提高速度 （5）避免使用临时变量而使程序的可读性下降 （6）避免不必要的转移（goto语句） （7）尽可能使用库函数

（8）避免采用复杂的条件语句

（9）尽量减少使用“否定”条件的条件语句 （10）数据结构要有利于程序的简化

（11）要模块化，使模块功能尽可能单一化

（12）利用信息隐蔽，确保每一个模块的独立性

（13）从数据出发去构造程序（程序是为数据服务的） （14）不要修补不好的程序，要重新编写

4．输入和输出

（1）对所有的输入数据都要检验数据的合法性 （2）检查输入项的各种重要组合的合理性 （3）输入格式要简单

（4）输入数据时，应允许使用自由格式 （5）应允许缺省值

（6）输入一批数据时，最好使用输入结束标志 （7）应该给出状态信息 （8）给所有的输出加注释 2.2结构化程序设计

由于软件危机的出现，人们开始研究程序设计方法，20世纪70年代提出了结构化程序设计思想和方法。结构化程序设计方法的核心是工程思想和结构化思想。 2.2.1结构化程序设计的原则（选择题）

1．自顶向下。先总体后细节，先全局后局部，逐步具体化

2．逐步求精。总目标→分目标→小目标，对复杂问题逐步细化 3．模块化。每个小目标称为模块

4．限制使用goto语句。少用，不是不可用 2.2.2结构化程序的基本结构与特点

三种基本控制结构：（选择/填空题） 1．顺序结构

2．选择（分支）结构 3．重复（循环）结构

2.2.3结构化程序设计原则和方法的使用（选择题）

1．使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑 2．选用的控制结构只准许有一个入口和一个出口

3．程序语句组成容易识别的块，每块只有一个入口和一个出口 4．复杂结构应该用嵌套来实现

5．语言中所没有的控制结构，应该采用前后一致的方法来模拟 6．严格控制goto语句的使用 2.3面向对象的程序设计 2.3.1关于面向对象方法

当今，面向对象方法已经成为主流的软件开发方法。 面向对象方法的优点：（选择题） 1．与人类习惯的思维方法一致

以对象为核心，对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系；对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。面向对象的程序设计强调模拟现实世界中的概念而不强调算法。

2．稳定性好

以对象为中心构造软件系统，根据问题领域的模型建立起来（而不是基于对系统应完成

的功能的分解），所以当对系统的功能需求变化时，不会引起软件结构的整体变化，往往仅需做一些局部性的修改。

3．可重用性好

软件重用：在不同的软件开发过程中重复使用相同或相似软件元素的过程。

由于对象具有很强的自含性（数据和操作平等）和独立性/封装性（对象的内部实现与外界隔离），所以说对象提供了比较理想的模块化机制和比较理想的可重用的软件成分；对象的继承性（类→实例，父类→子类）使得子类不仅可以重用其父类的数据结构和程序代码，而且可以在父类代码的基础上方便地修改和扩充，这种修改并不影响对原有类的使用，所以说这种可重用性是自然的和准确的。

4．易于开发大型的软件产品

可以把一个大型产品看作是一系列本质上相互独立的小产品来处理，这样既降低了开发的技术难度，又使开发工作容易管理。许多经验明显表明，用面向对象技术开发大型软件时，软件成本降低，软件的整体质量提高。

5．可维护性好

用面向对象的方法开发的软件稳定性比较好、比较容易修改、比较容易理解、 易于测试和调试。

2.3.2面向对象方法的基本概念

1．对象

对象：用来描述客观事物的一个实体，是构成系统的一个基本单位。对象由一组表示其静态特征的属性（用数据来表示）和它可以执行的一组操作（针对数据，为数据服务）组成的统一体。

对象的基本特点：（选择题）

1）标识唯一性：对象是可区分的

2）分类性：可以将具有相同属性和操作的对象抽象成类 3）多态性：同一操作可以是不同对象的行为

4）封装性：从外面看，只能看到对象的外部特性（无需知道数据的具体结构以及实现操作的算法）对外不可见也不能直接修改,有利于实现信息隐蔽。

5）模块独立性好。对象是数据和操作的统一体（是一个基本模块），内部的内聚性强，所以模块独立性好 2．类

类：类是具有共同属性、共同方法的对象的集合。它描述了该对象类型的所有对象的性质。（填空题）

类是对象的抽象，对象是类的实例。 3．消息

消息：是一个对象与另一个对象之间传递的信息。（填空题）

消息中只包含传递者的要求，告诉接受者做什么，并不指示接受者怎样做。 4．继承 针对类而言 父类---子类

继承：是使用已有的类定义作为基础建立新类的定义技术。（填空题） 继承分为单继承和多重继承。

相似的对象可以共享程序代码和数据结构，从而减少程序中的冗余信息，提高软件的可重用性，便于软件修改维护。

5．多态性

多态性：同样的消息被不同的对象接受时可导致不完全不同的行动。

多态性减少了软件中信息冗余，提高了软件的灵活性、可重用性、可扩充性。

第三章 软件工程基础

3.1软件工程基本概念 3.1.1软件定义与软件特点

计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。

程序：用程序设计语言描述的、适合计算机执行的指令序列 数据：使程序能正常操纵信息的数据结构

文档：与程序开发、维护和使用有关的图文资料 软件的特点：

1、软件是一种逻辑实体，而不是物理实体，具有抽象性 2、它没有明显的制作过程

3、软件在运行使用期间不存在磨损和老化的问题 4、软件的开发和运行对计算机系统具有依赖性 5、软件的复杂性高，成本昂贵 6、软件开发会涉及诸多的社会因素

软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）（填空/选择题） 应用软件：为解决特定领域的应用而开发的软件

系统软件：管理计算机软硬件资源，并为用户高效提供各种服务的软件 支撑软件：介于系统软件和应用软件之间，协助用户开发软件的工具性软件 3.1.2软件危机与软件工程

1、软件危机

软件工程源自软件危机。在软件开发和维护过程中，软件危机主要表现在： ① 软件需求的增长得不到满足。 ② 软件开发成本和进度无法控制。 ③ 软件质量难以保证。

④ 软件不可维护或维护程度非常低。 ⑤ 软件的成本不断提高。

⑥ 软件开发生产率的提高赶不上硬件的发展和应用需求的增长。 2、软件工程

软件工程：试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。

软件工程包括三个要素：方法、工具、过程。（填空题） 方法：完成软件工程项目的技术手段 工具：支持软件的开发、管理、文档生成 过程：支持软件开发的各个环节的控制、管理

软件工程的核心思想：把软件产品当成工程产品来处理，把需求计划，可行性研究，工程审核，质量监督等工程化的概念引入到软件生产当中，以期达到工程项目的三个基本要素（进度、经费、质量）的目标。 3.1.3软件工程过程和软件生命周期

1、软件工程过程：把输入转化为输出的一组彼此相关的资源和活动。

P（Plan）： 软件规格说明

D（Do）： 软件开发

C（Check）： 软件确认 A（Action）： 软件演进 ２、软件生命周期：将软件产品从提出、实现、使用维护到停止使用退役的过程。 具体阶段：如右图（选择/填空题）

3.1.4软件工程的目标与原则

1、软件工程目标： 在给定成本，进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性、可互操作性且满足用户需求的产品。

基于软件工程的目标，软件工程研究的内容主要有：

① 软件开发技术

② 软件工程管理 2、软件工程原则：

为了达到软件工程的目标，开发软件产品时要遵循软件工程的原则：

抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性 3.1.5软件开发工具和软件开发环境

1．软件开发工具

2．软件开发环境：全面支持软件开发全过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个阶段和各项任务的完成。

CASE（计算机辅助软件工程）：将各种软件工具、开发机器和一个存放开发过程信息的中心数据库组合起来，形成软件工程环境。（填空题） 3.2结构化分析方法

软件开发方法是软件开发过程所遵循的方法和步骤，其目的在于有效地得到一些工作产品，即程序和文档，并且满足质量要求。软件开发方法包括分析方法、设计方法和程序设计方法。

结构化方法已经成为系统的、成熟的软件开发方法之一，包括结构化分析方法，结构化设计方法和结构化编程方法。 3.2.1需求分析与需求分析方法

1．需求分析的任务：是发现需求、求精、建模和定义需求的过程。 需求分析阶段的工作：

①需求获取 ②需求分析

③编写需求规格说明书 ④需求评审 2．需求分析方法：

①结构化分析方法

面向数据流的结构化分析方法（SA） 面向数据结构的jackson方法（JSD）（填空题） 面向数据结构的结构化数据系统开发方法（DSSD） ②面向对象的分析方法(OOA)

3.2.2结构化分析方法

结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

1．结构化分析方法常用的工具（填空题） (1) 数据流图（DFD）：

是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示。 （选择题）

加工,转换

数据流

存储文件（数据源）

源,谭

(2) 数据字典（DD）

是对所有与系统相关的数据元素的一个有组织的列表。概括地说，数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。 (3) 判定树 (4) 判定表 3.2.3软件需求规格说明书（选择题）

软件需求规格说明书是需求分析阶段最后成果，是软件开发中的重要文档之一。 软件需求规格说明书的特点是：

① 正确性 ② 无歧义性 ③ 完整性 ④ 可验证性 ⑤ 一致性 ⑥ 可理解性 ⑦ 可修改性 ⑧ 可追踪性 3.3结构化设计方法

1．软件设计的基本原理（选择题）

(1) 抽象 (2) 模块化 (3) 信息隐蔽 (4) 模块独立性：

指每个模块只完成系统要求的独立的子功能，和其它模块接口简单，联系少。好的模块一定是独立性高的模块（高内聚、低耦合）。（常考）

内聚性：指一个模块内部各个元素之间彼此结合的紧密程度的度量。

耦合性：指模块间相互连接的紧密程度的度量。

软件设计包括概要设计和详细设计 3.3.2概要设计

1、概要设计的任务

①设计软件系统结构 ②数据结构及数据库设计 ③编写概要设计文档 ④概要设计文档评审。

2、常用的软件结构设计工具----结构图

结构图（SC，程序结构图）使用结构图描述软件系统的层次和分块结构关系，反映了整个系统的功能实现以及模块与模块之间的联系与通讯，是未来程序中的控制层次体系。

根据已绘出的结构图，分析出深度、宽度

图3.11 简单财务账务管理系统结构图

3、面向数据流的设计方法 数据流类型：变换型、事务型 4、设计的准则

① 提高模块独立性 ② 模块规模适中

③ 深度、宽度、扇出和扇入适当

④ 使模块的作用域在该模块的控制域内 ⑤ 应减少模块的接口和界面的复杂性 ⑥ 设计成单入口、单出口的模块 ⑦ 设计功能可预测的模块 3.3.3详细设计

1、详细设计的任务：

为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。

在过程设计阶段，要对每个模块规定的功能以及算法的设计，给出适当的算法描述，即确定模块内部的详细执行过程。

2、常用的过程设计工具

图形工具：程序流程图、N-S、PAD、HIPO（选择题）

表格工具：判定表 语言工具：伪码

3.4软件测试

3.4.1软件测试的目的（选择题）

软件测试：是为了发现错误而执行程序的过程。 3.4.21）．所有测试都应追溯到需求 2）．严格执行测试计划，排除测试的随意性 3）．充分注意测试中的群集现象 4）．程序员应避免检查自己的程序 5）．穷举测试不可能 6）．妥善保存测试计划，测试用例 3.4.3软件测试技术与方法综述

若从是否需要执行被测软件的角度，可分为静态测试、动态测试。 若按功能划分，可分为白盒测试、黑盒测试。（填空题）

注：白盒测试和黑盒测试都属于动态测试。

1、静态测试

不运行程序，由人工/软件工具进行

2、动态测试

运行程序，基于计算机测试 测试用例：[（输入值集），（输出值集）]

3、白盒测试（透明的）

在程序内部进行，主要用于完成软件内部操作的验证

白盒测试的基本原则是：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。

① 逻辑覆盖测试 ② 基本路径测试

4、黑盒测试（不透明的）

黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。

① 等价类划分法 ② 边界值分析法 ③ 错误推测法 ④ 因果图 3.4.4软件测试的实施

软件测试过程一般按4个步骤顺序进行：

单元测试→集成测试→验收测试（确认测试）→系统测试。 1、单元测试

目的：发现各模块内容可能存在的各种错误。

本文来源：https://www.bwwdw.com/article/703m.html