全国计算机等级考试二级VF.doc

二级VF知识点 第1章 基本数据结构与算法1. 算法的基本概念 算法的指解题方案的准确而完整的描述。作为一个算法，一般应具有的特征为：1） 可行性，针对实际问题设计的算法， 考虑其可行性，应该能够得到满意的结果；2） 确定性，算法中的每一个步骤都必须是明确定义的，不允许有模掕两可的解释，也不允许有多义性；3） 有穷性，算法必须能在执行有限个步骤之后终止；4） 有零个或多个输入；5） 有一个或多个输入；综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的.明确的；这个运算顺序将在有限的次数下终止。2. 算法复杂度 算法的复杂度主要包括时间复杂度和空间复杂度。（1）算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法在所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f（n)其中N是问题的规模。 例如，两个N阶矩阵相乘需要的基本算法次数为n3 ，即计算工作量为n3, 也就是时间复杂度为n3, 即 F（n）=O( n3 )(2) 算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。【例1.1】 算法的时间复杂度是指（ ） A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数 答案：C 提示：2005年9月真题填空题第2题。2006年9月真题选择题第7题。2007年4月真题选择题第1题属该题的类似题目2007年4月真题选择题第11题考察算法的特征。1.2 数据结构的基本概念1. 数据结构的定义 数据结构是指反映数据元素之间关系的数据元素集合的表示。 通俗地说，数据结构是指带有结构的数据元素的集合。（1）数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 一个数据结构应包含以下两方面的信息： 1） 表示数据元素的信息； 2） 表示各数据元素之间的前后件关系。（2） 数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 （也称数据的物理结构）。 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序。链接。索引等。而采用不同的存储结构，其数据处理的效率是不同的，因此，在进行数据处理时， 选择合适的存储结构是很重要的。【例1.2 】 与所使用的计算机系统无关的数据结构是（ ） A)存储 B)物理 C)逻辑 D)线性表 答案： C 解析： 线性表是一种具体逻辑结构，存储结构也称物理结构，只是逻辑结构是不依赖于计算机系统的。所以选项C为正确答案。【例1.3 】 数据的存储结构是指（ ） A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示 答案： D 解析：数据的存储结构，也称为数据的物理结构，它指的是数据的逻辑结构在计算机存储空间的中的存放形式。只有选项D符合其定义，为本题的答案。 提示：2007年4月真题选择题第1题与该题相关。 2007年9月真题选择题第5题考察程序的执行效率也数据结构的关系。2. 数据结构的图形表示【例1.4】 下列叙述中，正确的是（ ） A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构，存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效答案：D解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，而采用不同的存储结构，其数据处理的效率是不同的。提示： 2007年9月真题选择题第6题属该题的类似题目。数据结构除了可用二元关系表示外，还可以用直观的图形表示。在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素指的方框表示，一般称之为数据结点（简称为结点）。为了进一步表示各数据元素之间的前后件关系，对于关系中的每一个元组，用一条有向线段从前件结点指向后件结点。3. 线性结构与非线性结构 根据数据结构中个数据元素之间前后件关系的复杂程度，一般将数据结构分成两大类：线性结构和非线性结构。 如果一个非空的数据结构满足下列两个条件： 1）有且只有一个根结点 2）每一个结点最多有一个前件，也最多有有一个后件。 则称该数据结构为线性结构。线性结构又称为线性表。如果一个数据结构不是线性结构。就称为非线性结构。1.3 线性表及其顺序存储结构 1. 线性表的基本概念 线性表是有n（n0）个数据元素 a1,a2,.,an 组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件，即线性表或是一个空表。或者可以表示为： （ a1 ,a2 ,.ai ,.an ）其中 ai(i=1,2,.n)是数据元素，通常也称其为线性表中的一个结点。 2. 线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： 1）线性表中所有元素所占的存储空间是连续的； 2）线性表中个数据元素在存储空间中是逻辑顺序依次存放的。 由此可以看出，在线性表的存储结构中，其前后件两个元素在存储空间中的紧邻的， 且前后元素一定存储在后件元素的前面。 3. 线性表的插入、删除运算下面讨论线性表在顺序存储结构下的插入与删除的问题。（1）线性表的插入运算 设长度为n的线性表为 （ a1 ，a2 ， ，ai ，an ）现要在线性表的第j个元素 之前插入一个新元素b，插入后得到长度为n+1的线性表为 （a1,a2, ，aj，aj+1，an，an+1）则插入前后两个线性表中的元素满足如下关系: aj 1ji-1aj= b j = i aj-1 i+1jn+1一般情况下，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n）元素开始，知道第i 个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个就被空出，然后将新元素插入到第i 个位置，插入结束后，线性表的长度增加了1.（2）线性表的删除运算 设长度为n的线性表为 （ a1 ，a2 ， ，ai ，an ）现要删除第j个元素，删除后得到长度为n-1的线性表 （ a1,a2, ，aj，an-1 ）则删除前后两个线性表中的元素满足如下关系： aj 1ji-1aj= aj+1 i+1jn+1一般情况下，要删除第i （1in ）个元素时，从第i+1个元素开始，直到第n个元素之间共n-1个元素依次向前移动一个位置，删除结束后，线性表的长度减少了1。1.4 栈和队列 栈及其基本运算 队列及其基本运算1. 及其基本运算 栈（stack）是限定在一端进行插入和删除运算的线性表。 在栈中，允许插入与删除的一端称为栈顶（top），另一端称为栈低（bottom）。栈顶元素总是最后被插入的元素；栈底元素总是最先被插入的元素，栈顶元素总是最先被删除的元素；栈底元素总是最后被删除的元素。即栈是按照“先进后出”（First In Last “Out, FILO”）的原则组织数据的，因此，栈也被称为“先进后出”表。 栈的基本运算有三种： 入栈、出栈、和读栈顶元素。【例1.5】 下列关于栈的描述中错误的是（ ） A)栈的先进后出的线性表 B)栈只能顺序存储 C)栈具有记忆作用 D)对栈的插入于删除中，不需要改变栈底指针。 答案： B . 解析：栈是限定在一端进行插入和删除的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底；栈是按照“先进后出”或“后进先出”的原则就、组织数据的；栈既可以顺序存储又可以链式存储；栈具有记忆功能。 提示：2008年4月真题选择题第7题属该题的类似题目。 （1） 队列的基本概念队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一段称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素;允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。因此，队列又称为“先进先出”（First In First Out FIFO）的线性表。退队a1 a2 a3 an入队队列的基本结构如图1-1所示。 图1-1 队列的基本结构向队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。（2）循环队列及其运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向最后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。循环队列的初始状态唯恐，即rear=front【例1-6】 下列关于队列的叙述正确的是（ ）。A）队列是非线性结构 B）队列是一种树状结构C）队列具有“先进先出”的特征 D）队列具有“后进后出”的特征 答案：C。提示：2007年4月真题选择题第5题属该题的类似题目。【例1-7】 下列说法中，正确的是（ ）。A）栈是在两端操作、“先进先出”的线性表 B）栈是在一端操作、“先进先出”的线性表 C）队列是在一端操作、“先进先出”的线D）队列是在两端操作、“先进先出”的线性表 答案：D。 解析：栈是只允许在一端进行插入和删除操作的线性表，又称“先进后出”或“后进先出”表；队列是在一段进行插入，而在另一端进行删除的线性表，又称“先进先出”或“后进后出”表。所以只有选项D正确。 提示：2007年9月真题填空题第3题考察循环队列的存储结构。1.5 线性链表1.线性链表的基本概念线性表的链式存储结构称为线性链表，线性链表分为单链表，双向链表和循环链表三种类型。为了适应线性表的链式存储结构，计算机存储空间被划为一个一个小块，每一小块占若干字节，通常称这些小块为存储节点。为了存储线性表中的每一个元素，一方面要存出数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储节点分为两部分：一部分用于存储数据元素的值，称之为数据域；另一部分用于存放下一个数据元素的存储序号（即存储节点的地址），即指向后件节点，称为指针域。2. 线性链表的基本运算线性链表的运算主要有以下几个：1） 在线性链表中包含指定元素的结点之前插入一个新元素。2） 在线性链表中删除包含指定元素的结点。3） 将两个线性链表按要求合并成一个线性链表。4） 将一个线性链表按要求进行分解。5） 逆转线性链表。6） 复制线性链表。7） 线性链表的排序。8） 线性链表的查找。3.循环链表及其基本运算 循环链表与线性链表相比，具有以下两个特点：1） 在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。2） 循环链表中最后一个结点的指针域不为空，而是指向表头结点。即循环链表中，所有结点的指针构成了一个环状链。a1a2图1-2是一个非空循环链表，图1-3是一个空循环链表。an HEAD 图1-2 非空循环链表 HEAD 表头结点 图1-3 空循环链表循环链表的插入和删除运算的方法与线性单链表基本相同。但由循环链表的特点可以看出，在对循环链表进行插入和删除过程中，实现了空表和非空表的运算统一。【例1-8】 下列对于线性链表的描述中正确的是（ ）。 A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须有连续，且前件元素一定存储在后件元素前面 D）存储空间必须有连续，且各元素的存储顺序是任意的 答案：A。 解析：采用链式存储结构的线性表称为线性链表。其存储的结构的存储空间可以不连续，换句话说，逻辑上相邻的数据元素，其储存位置（又称物理位置）不一定相邻，数据元素之间的逻辑关系是由指针域确定的。1.6 树和二叉树 树的基本概念 树是一种简单的非线性结构。在树这种数据结构中，所有元素之间的关系具有明显的层次特性，图1-4表示一棵一般的树。KJIHGFEDCBA 图1-4 一般的树2.二叉树及其基本性质 （1）什么是二叉树 二叉树是一种很有用的非线性结构，它具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该节点的左子树和右子树。（2）二叉树的基本性质 二叉树具有以下几个性质： 性质1 在二叉树的第k层上，最多有2k-1（k1）个结点。 性质2 深度为m的二叉树最多有2m-1个结点。 性质3 在任意一棵二叉树中，度为0的结点（即叶结点）总是比度为2的结点多一个。 性质4 具有n个节点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。（3）满二叉树与完全二叉树 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点，换句话说，每一层上的节点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树中有2m-1个结点。完全二叉树：除最后一层外，每一层上的节点数都达到最大值；在最后一层上只缺少右边的若干结点。满二叉树与完全二叉树的关系：满二叉树也是完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树还具有如下两个特性：性质5 具有n个结点的完全二叉树的深度为log2n+1。性质6 设完全二叉树共有n个结点。如果从根节点开始，按层序（每一层从左到右）用自然数1，2，n给结点编号，则对于编号为k（k=1，2，n）的结点有以下结论：1、若k=1，则该结点为根节点，他没有父节点，若k1，则该结点的父节点编号为k/2。2、若2kn，则编号为k的左节点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。3、若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。【例1-9】 设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶结点。 答案：350个。 解析：根据完全二叉树的定义可以得出：度为1的结点的个数为0或1；又由性质3可知，度为0的结点的个数比度为2的结点的个数多1个；设度为0的结点个数为k，则度为2的结点个数为k-1，设度为1的结点个数为n，则有k+k-1+n=700,由于k和n都是自然数，n的值为0或1，所以只有当n=1是，k有整数解，此时k=350. 提示：2007年9月真题选择题第8题属该题的类似题目。【例1-10】 深度为5的满二叉树中，结点的个数为 。 答案：31。 解析：满二叉树是相同深度的二叉树中结点最多的一棵，所以由性质2可知，深度为5的二叉树最多有25-1=31个结点。即深度为5的满二叉树的结点为31个。 提示：2007年4月真题选择题第7题、填空题第1题、2008年4月真题填空题第2题属该题的类似题目。3.二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。 与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成；数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），一次，用于存储二叉树的存储节点的指针域有两个，一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。4.二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。各个遍历过程描述如下：（1） 前序遍历（DLR）若二叉树为空，则结束返回，否则：访问根节点；前序遍历左子树；前序遍历右子树。（2） 中序遍历（LDR）若二叉树为空，则结束返回，否则：中序遍历左子树；访问根节点；中序遍历右子树。（3） 后序遍历（LRD）若二叉树为空，则结束返回，否则：后序遍历左子树；访问根节点后（4） 序遍历右子树。【例1-11】 已知二叉树（见图1-5），其后序遍历序列是（ ）。FECBA A）ABCDEF B) DBAECFC) BCDEFA D) DBEFCA D答案：D。 解析：采用后序遍历方式遍历二叉树的具体过程为：1）先后序遍历左子树（以B为根节点的左子树，包括两个结点B和D），在左子树中仍按后序遍历，所以先访问左节点D，其右子树为空，所以第二个访问的结点是该子树的根节点B。 图1-5 二叉树 2)接着按后序遍历右子树（以C为根节点，包括C、E、F三个结点），右子树中也按后序遍历访问左子树E，再访问右子树F，最后访问根节点C，右子树访问完毕。3)最后访问的是二叉树的根节点A。故访问顺序为：DBEFCA。查找技术所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常，对不同的数据结构应采用不同的查找方法。1.顺序查找 顺序查找是指在现行表中查找指定的元素，基本方法为：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若现行表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。【例1-12】 对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数是（ ）。 A）n+1 B）n C)(n+1)/2 D)n/2 答案：B。 解析：在进行顺序查找过程中，如果现行表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查找元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺行查找的最坏情况。在平均情况下，利用顺序查找法在线性表中一半的元素进行比较。 题目中的线性表的长度为n，则在最坏情况下，需要比较n次。2.二分查找 二分查找只适用于顺序存储的有序表。设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：将x与线性表的中间项进行比较。 若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0（说明现行表中没有这个元素）为止。 显然，当有序线性表为顺序存储时才能采用二分查找，并且二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。排序技术 所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）的次序排列起来。重要知识点 交换类排序法1. 交换类排序法（1） 冒泡排序法冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。冒泡排序法的基本过程如下：首先，从表头开始往后扫描线性表，在扫描过程中主次比较两个相邻元素的大小。若两个相邻元素中，前面的元素大于后面的元素，则将它们交换，称之为消去了一个逆序。然后从后往前扫描剩下的线性表，同样，在扫描过程中主次比较两个相邻元素的大小。若两个相邻元素中，后面的元素小于前面的元素，则将他们交换，这样就又消去了一个逆序。一次排序结束后，表中最大元素为与线性表末尾。对剩下的线性表重复上述过程，直到剩下的线性表变空位置，此时的线性表已经变为有序。（2） 快速排序法快速排序法也会死一种交换类排序方法，但由于它的排序速度比较快，因此称为快速排序法。快速排序法的基本思想如下：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后连个子表，且前面子表中的所有元素均不大于T，二后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且这种分割过程一直做下去，知道所有子表为空为止，则此时的线性表就变成了有序表。【1-13】 在最坏情况下，冒泡排序法需要的比较次数为 。 答案：n（n-1）/2. 解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍从前往后的扫描和n/2遍的从后往前的扫描，同时需要进行n-1躺排序所以比较次数为n（n-1）/2。但这个工作量不是必需的，一般情况下要小于这个工作量。2. 插入类排序法（1） 简单插入排序法 所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性列表中。（2） 希尔排序法 希尔排序法属于插入类排序，其基本思想为：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列分割方法 如下：将相隔某个增量h的元素构成一个子序列，在排序过程中，逐次减少这个铮亮，最后当h减到1时，进行一次插入排序，排序即完成3. 选择类排序法（1） 简单选择排序法 选择排序法的基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。（2） 建堆排序法堆排序的方法如下：1、首先将一个无序序列建成堆；2、然后将堆顶元素与堆中最后一个元素交换。不考虑已经交换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子树调整为堆。反复做第二部，知道剩下的子序列为空为止。1.10 仿真练习与参考答案一选择题 1.下面的叙述正确的是（ ）。A）算法的执行效率与数据的存储结构无关B)算法的空间复杂度是指算法程序中指令（或语句）的条数C）算法的有穷性是指算法必须能在执行有限个步骤之后终止。D）以上三种描述都不对。2.以下数据结构中不属于现行数据结构的是（ ）。A）队列 B）线性表 C）二叉树 D）栈 3.一个栈的入栈序列是A,B,C,D,E,则不可能的输出序列是（ ）。A) E D C B A B) D E C B A C) D C E A B D) A B C D E 4.快速排序法属于（ ）排序法。A) 交换类 B）插入类 C）选择类 D) 建堆 5.下列关于队列的叙述正确的是（ ）。A）在队列中只能插入数据 B）在队列中只能删除数据C）队列是“先进先出”的线性表 D）队列是“先进后出”的线性表 6.在深度为5的满二叉树中，叶结点的个数为（ ）。A）32 B）31 C）16 D）15 7.算法的空间复杂度是指（ ）。 A)算法程序的长度 B）算法程序中的指令条数C）执行算法过程中所需要的存储空间 D）算法程序所占的存储空间 8.对一个长度为10的排好序的表用二分法查找，若查找不成功，至少需要比较的次数为（ ） A）3 B）4 C）5 D）6 9.假定根节点的层次是0，含有15个结点的二叉树的最小树深是（ ）。 A）3 B）4 C）5 D）6 10.深度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为（ ）。 A）2h-1 B）2h C）2h+1 D）h+1 11.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（ ）。 A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n（n-1）/2二填空题1.数据结构包括数据的 结构和数据的存储结构及各种数据结构间的运算。2.只允许在一端进行插入和删除的线性表称为 。3.在长度为n的有序线性表中进行二分查找，其时间复杂度为 。4.设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为 5.线性表中 称为线性表的长度。参考答案一、选择题1.C 2.C 3.C 4.A 5.C 6.C 7.C 8.A 9.A 10.A 11.D二、填空题1.逻辑 2.栈 3.O（log2n） 4.DEBFCA 5.数据元素的个数第2章 程序设计基础2.1 程序设计方法与风格 除了好的程序设计方法外，程序设计风格也很中亚，因为程序设计风格回影响软件的质量和可维护性，良好的程序设计风格可以是程序结构清晰合理，是程序代码便于维护。程序设计风格是指编写程序是所表现出的特点、习惯和逻辑思路。总体而言，程序设计风格应该强调简单和清晰，程序必须是可以理解的。 要形成良好的程序设计风格，主要应注重和考虑下属一些因素:源程序文档化、数据说明方法、语句的结构以及输入和输出。【例2-1】 形成良好的程序设计风格，需要考虑的一些因素中不包括 （ ）。 A）源程序文档化 B)数据说明方法 C）可行性研究 D）输入和输出 答案：C。2.2 结构化程序设计重要知识点 面向对象方法的基本概念1.结构化程序设计的原则结构化程序设计方法的主要原则为：1）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。2）逐步求精：对复杂问题，应设计一些子目标作为过渡，逐步细化。3）模块化：一个复杂问题肯定是由若干简单的问题构成。模块化就是把程序要解决的总目标分解为分目标，在进一步分解为具体的小目标，把每个小目标称为一个模块。4）限制使用GOTO语句。2.结构化程序设计的结构与说明 结构化程序由顺序、分支、循环三种基本结构组成，可以用下图进行说明。A条件B条件BCACBA 一端结构化程序，都可以归结为以上三种结构，无论是简单问题还是复杂问题，都可以设计成以上三种结构的一种或多种来解决。这种是程序结构化有利于提高模块的独立性，提高程序的信息隐蔽能力。【例2-2】 下面对于结构化程序设计方法的主要原则描述错误的是（ ）。A）自顶向下 B）逐步求精 C）模块化 D）多使用GOTO语句答案：D。3.关于面向对象方法 面向对象方法之所以日益受考查结构化程序设计的结构。到人们的重视和应用，称为流行的软件开发方法，是因为面向对象方法具有以下主要优点：与人类习惯的思维方法一致。 稳定性好。可重用性好。易于开发大型软件产品。可维护性好。面向对象方法的基本概念面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。面向对象方法中的几个重要的概念是理解和使用面向对象的基础和关键。这些概念包括：（1） 对象（Object）对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体。客观世界中的实体通常既具有静态的属性又具有动态的行为，因此，面向对象方法学中的对象是由描述该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。对象可以做的操作表示它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作称为方法或服务。属性即对象所包含的信息，他在设计对象是确定，一般只能通过执行对象的操作来改变属性。操作描述了对象执行的功能，若通过消息传递，还可以被其他对象使用。操作的过程对外是封闭的，即用户只能看到这一操作实施后的结果。对象的这一特征称为对象的封装性。（2） 类（Class）和实例（Instance）类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。类同对象一样，包括一组数据属性和在数据上的一组合法操作。（3） 消息（Message） 面向对象世界是通过对象与对象间彼此相互合作来推动的对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。 消息是一个实例与另一个实例之间传递的信息，他请求对象执行某一处理或回答某一要求的信息，他统一了数据流和控制流。消息类似于函数调用。一个消息有以下三部分组成：1、接收消息的对象的名称。2、消息标识符（也称为消息名）。3、零个或多个参数。（4） 继承（Inheritance） 继承是面向对象方法的一个重要特征。继承是使用已有的类定义作为基础，建立新类的定义技术。已有的类可当作基类来引用，新类相应地可当作派生类来引用。 广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 面向对象软件技术的许多强有力的功能和突出优点，都来源于把类组成一个层次结构的系统；一个类的上层可以有父类，下层可以有子类。这种层次结构系统的一个重要性质就是继承，一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。（5） 多态性（Polymorphism） 对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时，可导致完全不同的行动，该现象称为多态性。在面向对象的软件技术中，多态性是指子类对象可以像父亲对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。【例2-3】在面向对象的程序设计中，类描述的是具有相似性质的一组 。 答案：对象。 解析：由于类是具有共同属性、共同方法的对象的集合。所以类描述的是具有相似性质的一组对象。【例2-4】在面向对象方法中，类之间共享属性和操作的机制称为 。 答案：继承。 解析：继承是使用已有的类定义作为基础，建立新类的定义技术。因此他是类之间共享属性和操作的机制。2.4仿真练习与参考答案一、选择题1.结构化程序设计的三种基本控制结构是（ ）。A）输入、处理、输出 B)树形、网形、环形C）顺序、选择、循环 D）主程序、子程序、函数2.关于对象概念描述错误的是（ ）。A）任何对象都必须有继承性 B）对象是属性和方法的封装体C）对象间的通信靠消息传递 D）操作是对象的动态属性3.为了使程序在不同的计算机环境中都能运行，程序应该具有良好的（ ）。A）可适用性 B）可重用性 C）可移植性 D）可创新性4.面向对象的主要特征除了对象的惟一、封装、继承外，还有（ ）。A）多态性 B）完整性 C）可移植性 D）兼容性5.面向对象的程序设计主要考虑的是提高软件的（ ）。 A）可靠性 B）可重用性 C）可移植性 D）可修改性6.信息隐蔽是通过（ ）实现的。A）抽象性 B）封装性 C）继承性 D）传递性二、填空题1. 的基本原理是使用现实世界的概念抽象地思考问题，从而自然地解决问题。2.源程序文档化要求程序应加以注释。注释一般分为序言性注释和 注释。3.类是一个支持集成的抽象数据类型，而对象是类的 。4.面向对象的模型中，最基本的概念是对象和 。参考答案一、选择题1.C 2.A 3.C 4.A 5.B 6.B二、填空题1.面向对象方法 2.功能性 3.实例 4.类第3章 软件工程基础3.1软件工程基本概念1. 软件工程基本概念（1）软件定义与软件特点计算机软件（Software）是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。软件有以下特点：1） 软件是一种逻辑实体，而不是物理实体，具有抽象性；2） 软件的生产与硬件不同，它没有明显的制作过程；3） 软件在运行、使用期间不存在磨损、老化问题；4） 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；5） 软件复杂性高、成本昂贵；6） 软件开发设计诸多的社会因素。 （2）软件危机与软件工程软件工程概念的出现源自软件危机。20世纪60年代末以后，“软件危机”这个词频繁出现，所谓软件危机，是指在计算机软件的开发和维护过程中所遇到的一系列严重问题。具体地说，在软件开发和维护过程中，软件危机主要表现在：1） 软件需求的增长得不到满足。用户对系统不满意的情况经常发生。2） 软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生；3） 软件质量难以保证；4） 软件不可维护或维护程度非常低；5） 软件的成本不断提高；6） 软件开发生产率的提高跟不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率等问题。为了消除软件危机，通过认真研究解决软件危机的方法，认识到软件工程是使计算机软件走向工程科学的途径，逐步形成了软件工程的概念，开辟了工程学的新兴领域软件工程学。软件工程就是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。国标（GB）中指出，软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。1993年，IEEE(Institute of Electrical & Electronic Engineers,电气和电子工程师学会)对软件工程给出了一个更加综合的定义：“将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中。”这些主要思想都是强调在软件开发过程中需要应用工程化的原则。软件工程的三要素为方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制和管理。软件工程的核心思想是把软件产品（就像其他工业产品一样）堪称是一个工程产品。把需求分析、可行性研究、工程审核、质量监督等工程化的概念引入到软件生产中，以期达到工程项目的三个基本要素（进度、经费和质量）的目标。2. 软件生命周期概念（1） 软件工程过程ISO 9000中关于软件工程过程的定义是：软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。该定义支持了软件工程过程的以下两方面内涵：其一，软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。其二,从软件开发的观点看，它就是使用适当的资源（包括人员、硬软件工具、时间等），为开发软件进行的一组开发活动，在过程结束是将输入（用户要求）转化为输出（软件产品）。所以，软件工程的过程是将软件工程的方法和工具综合起来，已达到合理、及时地进行计算机软件开发的目的。（2） 软件生命周期通常，将软件产品从提出、实现、使用维护到停止使用（退役）的过程称为软件生命周期。一般将软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。其主要活动阶段是：1）可行性研究与计划制定。确定待开发软件形同的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。2）需求分析。队准备开发的软件提出的需求进行分析并给出详细定义，编写软件规格说明书及初步的用户手册，提交评审。3）软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。在系统比较复杂的情况下，设计阶段可分解成概要设计阶段和详细设计阶段。编写概要设计说明书、详细设计说明书和测试计划初稿，提交评审。4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。5）软件测试.在设计测试用例的基础上，检验软件的各个组成部分，编写测试分析报告。6）运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改。（3）软件工程的目标与原则1）软件工程的目标。在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程需要达到的基本目标应是：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付使用。1） 软件工程的原则。为了达到上述的软件工程目标，在软件开发过程中，必须遵循软件工程的基本原则。这些原则适用于所有软件项目。这些基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、和可验证性。3.软件开发工具与软件开发环境软件开发工具的完善和发展奖促进软件开发方法的进步和完善，促进软件开发的高速度和高质量。软件开发工具的发展是从单项工具的开发逐步向集成工具发展的，软件开发工具为软件工程方法提供了自动的或半自动的软件支撑环境。软件开发环境或称软件工程环境好似全面支持软件开发全过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个阶段和各项任务的完成。计算机辅助软件工程（Computer Aided Software Engineering,CASE）是当前软件开发环境中富有特色的研究工作和发展方向。【例3-1】以下说法错误