计算机公共基础

计算机公共基础

第一章数据结构与算法　　一、学习目标与要求　　1．了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；　　2．掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利用图形的方式表示数据结构；　　3．了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的线性表的基本运算；　　4．了解栈和队列的基本概念，并掌握它们的基本运算；　　5．了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循环链表的基本概念和基本操作；　　6．理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存储结构和遍历技术；　　7．掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；　　8．学会利用相关的排序技术实现无序数列的排序操作。　　二、内容要点　　（一）算法　　1．算法的基本概念　　算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。　　1）算法的基本特征　　（1）可行性　　由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。　　如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。　　（2）确定性　　算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。\n　　例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一个方程来求解，要求x和y的值，公式是正确的，但如何让计算能够进行计算，我们的算法不能把公式直接输进去，而应该设计出解题的步骤和过程。　　即设计的算法是计算工具所能够正常解决问题的过程。　　（3）有穷性　　算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。　　例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。　　（4）拥有足够的情报　　算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。　　2）算法的基本要素　　一是数据对象的运算和操作，二是算法的控制结构。　　（1）算法中对数据的运算和操作　　算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。　　（2）算法的控制结构　　算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。　　在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。　　在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：流程图、N-S结构图和算法描述语言等。　　3）算法设计的基本方法　　为用计算机解决实际问题而设计的算法，即是计算机算法。　　通常的算法设计有如下几种：\n　　（1）列举法　　列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。　　例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法进行解决。　　使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。　　（2）归纳法　　归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。　　（3）递推　　递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。　　递推的本质也是一种归纳，递推关系式通常是归纳的结果。　　例如，裴波那契数列，是采用递推的方法解决问题的。　　（4）递归　　在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。　　递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。　　（5）减半递推技术　　减半递推即将问题的规模减半，然后，重复相同的递推操作。　　例如，一元二次方程的求解。　　（6）回溯法\n　　有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换别的路线进行试探。这种方法，即称为回溯法。　　如人工智能中的机器人下棋。　　2．算法复杂度　　算法的复杂度包括时间复杂度和空间复杂度。　　1）时间复杂度　　即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。　　同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：　　算法工作量=f(n)　　（1）平均性态　　用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。　　设x是某个可能输入中的某个特定输入，p(x)是x出现的概率，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：　　Dn表示当规模为n时，算法执行时所有可能输入的集合。　　（2）最坏情况复杂度　　指在规模为n时，算法所执行的基本运算的最大次数。它定义为：　例如，在具有n个元素的数列中搜索一个数x。　　平均性态：\n　　即该数在数列中任何位置出现的数列是相同的，也有可能不存在，存在的概率为q。如果有一半的机会存在，则概率q为1/2，平均性态：　　如果查找的元素一定在数列中，则每个数存在的概率即为1，则平均性态为：　　最坏情况分析：即要查找的元素X在数列的最后或不在数列中，显然，它的最坏情况复杂度为：　　2）算法的空间复杂度　　指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，如执行过程中工作单元以及某种数据结构所需要的附加存储空间等。　　（二）数据结构的基本概念　　1．概念　　数据结构是指相互有关联的数据元素的集合。它包括以下两个方面：　　表示数据元素的信息　　表示各数据之间的前后件关系　　1）数据的逻辑结构　　是指反映数据元素之间的逻辑关系的数据结构。　　数据的逻辑结构有两个要素：　　数据元素的集合，记作D　　数据之间的前后件关系，记作R\n　　则数据结构B=（D，R）　　2）数据的存储结构　　数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。　　即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。　　通常的数据存储结构有顺序、链接、索引等存储结构。　　2．数据结构的图形表示　　数据结构的图形表示有两个元素：　　中间标有元素值的方框表示数据元素，称为数据结点　　用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结点　　注意：在结构图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也称叶子结点。　　3．线性结构与非线性结构　　如果一个数据元素都没有，该数据结构称为空数据结构；在空数据结构中插入一个新的元素后数据结构变为非空数据结构；将数据结构中的所有元素均删除，则该数据结构变成空数据结构。　　如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：　　有且只有一个根结点　　每一个结点最多只有一个前件，也最多只有一个后件　　线性结构又称线性表。　　注意：在线性结构表中插入或删除元素，该线性表仍然应满足线性结构。　　如果一个数据结构不满足线性结构，则称为非线性结构。　　（三）线性表及其顺序存储结构　　1．基本概念　　线性表是最常用的数据结构，它由一组数据元素组成。\n　　注意：这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。如，矩阵、学生记录表等。　　非空线性表的结构特征：　　有且只有一个根结点，它无前件　　有且只有一个终端结点，它无后件　　除根结点和终端结点之外，所有的结点有且只有一个前件和一个后件。线性表中结点的个数称为结点的长度n。当n=0时，称为空表。　　2．顺序存储结构　　顺序存储结构的特点：　　线性表中所有的元素所占的存储空间是连续的　　线性表中各数据元素在存储空间中是按逻辑顺序依次存放的　　通常，顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。　　线性表的顺序存储结构下的基本运算：　　在指定位置插入一个元素　　删除线性表中的指定元素　　查找某个或某些特定的元素　　线性表的排序　　按要求将一个线性表拆分为多个线性表　　将多个线性表合并为一个线性表　　复制线性表　　逆转一个线性表　　3．线性表的基本操作　　1）顺序表的插入运算　　在顺序存储结构的线性表中插入一个元素。\n　　注意：找到插入位置后，将插入位置开始的所有元素从最后一个元素开始顺序后移。另外，在定义线性表时，一定要定义足够的空间，否则，将不允许插入元素。　　2）顺序表的删除运算　　在顺序在存储结构的线性表中删除一个元素。　　注意：找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在移动完成后，线性表的长度减1（四）栈和队列　　1．栈及其基本运算　　1）栈　　栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。它的插入和删除只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。　　在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端则称为栈底。栈顶的元素总是最后被插入的元素，也是最先被删除的元素。它遵循的原则是：先进后出或后进先出。　　堆栈指针总是指向栈顶元素的。　　2）栈的顺序存储及其运算　　在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素，S（top）为栈顶元素。Top=0表示栈空；top=m表示栈满。　　1）入栈运算　　即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加1，再将元素插入至指针所指的位置。　　2）退栈运算　　退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给指定的变量，再将栈顶指针减1。　　3）读栈顶元素　　将栈顶元素赋给某一指定变量，但栈顶指针不变。　　2．队列及其基本运算\n　　1）队列　　队列即是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针指向队尾；允许删除的一端称为队首，通常用一个队首指针指向排队元素的前一个位置。　　队列遵循的规则是：先进先出或后进后出　　2）循环队列及其运算　　队列的顺序存储结构一般采用循环队列的形式。　　循环队列，即是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。　　在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置到队尾指针rear指向的位置之间所有的元素均为队列中的元素。　　循环队列的初始状态为空，即rear=front=m。这里m即为队列的存储空间。　　循环队列的基本运算：入队运算和退队运算。　　入队运算：每进行一次入队运算，队尾指针加1。当队尾指针rear=m+1时，即表示队列空间的尾部已经放置了元素，则下一个元素应该旋转到队列空间的首部，即rear=1　　退队运算：每退队一个元素，排头指针加1。当排头指针front=m+1时，即排头指针指向队列空间的尾部，退队后，排头指针指向队列空间的开始，即front=1。　　在队列操作时，循环队列满时，front=rear，队列空时，也有rear=front，即在队列空或满时，排头指针和队尾指针均指向同一个位置。要判断队列空或满时，还应增加一个标志，s值的定义：　　判断队列空与队列满的条件下：　　队列空的条件：s=0　　队列满的条件：s=1、front=rear　　（1）入队运算\n　　即在队尾加入一个新元素。这个运算有两个基本操作：首先，将队尾指针加1，即rear=rear+1，当rear=m+1时，置rear=1，然后，将新元素插入到队尾指针指向的位置。　　当循环队列非空（s=1），且front=rear时，队列满，不能进行入队操作。此情况称“上溢”。　　（2）退队操作　　即将队首的元素赋给一个指定的变量。该运算也有两个基本操作：首先，将排头指针加1，即front=front+1，当front=m+1时，置front=1，然后，将排头指针指向的元素赋给指定的变量。　　当循环队列为空（s=0）时，不能进行退队运算。此种情况称为“下溢”。　　（五）线性链表　　1．基本概念　　前面的线性表均是采用顺序存储结构及在顺序存储结构下的运算。　　1）顺序存储的优点：　　结构简单　　运算方便　　2）顺序存储结构的缺点：　　要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储。在插入或删除元素时，需要移动大量的数据元素，因此运算效率较低。　　如果一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入元素时，会发生“上溢”错误。　　在实际应用时，可能有多个线性表同时使用存储空间，这样给存储空间的分配带来问题，有可能使有的队列空间不够或过多造成浪费。　　基于上述情况，对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。　　3）链式存储结构　　假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。\n　　在链式存储方式中，要求每一个结点由两部分组成：一部分用于存放数据元素，你为数据域；另一部分用于存放指针，称为指针域。该指针用于指向该结点的前一个或后一个结点。　　在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。　　链式存储结构既可以用于线性结构，也可用于非线性结构。　　4）线性链表　　线性表的链式存储结构称为线性链表。　　将存储空间划分成若干的小块，每块占用若干个字节，这些小块称为存储结点。　　将存储结点分为两个部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储元素之间的前后件关系，即存放下一个元素在存储序号（即存储地址），即指向后件结点，称为指针域。　　在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放第一个元素的地址）。线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空（用Null或0表示），表示链终结。　　在线性链表中，各元素的存储序号是不连续的，元素间的前后件关系与位置关系也是不一致的。在线性链表中，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指针HEAD称为头指针，当HEAD=NULL时，表示该链表为空。　　对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。　　这种线性链表称为线性单链表，即可以从表头开始向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。　　这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。在某些应用时，如果对链表中的元素设置两个指针域，一个为指向前件的指针域，称为左指针（LLink），一个为指向后件的指针域，称为右指针（RLink）。则这种链表是双向链表。　　5）带链的栈　　带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。　　当需要存储结点时，即从可利用的栈的顶部取出栈顶结点；当系统要释放一个存储结点时，将该结点空间放回到可利用栈的栈顶。　　即在计算机中所有空闲的空间，均可以以结点的方式链接到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈和入栈操作。\n　　6）带链的队列　　队列也是线性表，也可利用链式存储结构来进行保存。2．线性链表的基本运算　　线性链表包括的基本运算：　　在链表中包含指定元素的结点之前插入一个新元素　　在链表中删除包含指定元素的结点　　将两个线性链表按要求合并成一个线性链表　　将一个线性链表按要求进行分解　　逆转线性链表　　复制线性链表　　线性链表的排序　　线性链表的查找　　1）线性链表中查找指定的元素　　在线性链表中查找元素X：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。　　元素的查找，经常是为了进行插入或删除操作而进行的，因此，在查找时，往往是需要记录下该结点的前一个结点。　　2）线性链表的插入　　线性链表的插入即在链式存储结构的线性表中插入一个新元素。　　在线性链表中包含元素x的结点之前插入新元素b，插入过程：　　（1）从可利用栈中取得一个结点，设该结点号为p，即取得的结点的存储序号存放在变量p中。并置结点p的数据域为插入的元素值b。　　（2）在线性链表中寻找包含元素x的前一个结点，该结点的存储序号为q。　　（3）将结点p插入到结点q之后。具体的操作：首先，使结点p插入到结点q之后（即结点q的后件结点），然后，使结点q的指针域内容改为指向结点p。\n　　线性链表的插入操作，新结点是为来自于可利用栈，因此不会造成线性表的溢出。同样，由于可利用栈可被多个线性表利用，因此，不会造成存储空间的浪费，大家动态地共同使用存储空间。　　3）线性链表的删除　　线性链表的删除，即是在链式存储结构下的线性表中删除指定元素的结点。　　操作方式：　　（1）在线性表中找到包含指定元素x的前一个结点p　　（2）将该结点p后的包含元素x的结点从线性链表中删除，然后将被删除结点的后一个结点q的地址提供给结点p的指针域，即将结点p指向结点q。　　（3）将删除的结点送回可利用栈。　　从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性表所不能实现的。同时，此操作还可更有效地利用计算机的存储空间。　　3．循环链表及其基本操作　　在线性链表中，虽然对数据元素的插入和删除操作比较简单，但由于它对第一个结点和空表需要单独处理，使得空表与非空表的处理不一致。　　循环链表，即是采用另一种链接方式，它的特点如下：　　（1）在循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。　　（2）循环链表中最后一个结点的指针域不是空的，而是指向表头结点。在循环链表中，所有结点的指针构成一个环状链。　　在循环链表中，只要指出表中任何一个结点的位置，均可以从它开始扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链表，只能按照指针的方向进行扫描。　　循环链表中设置了一个表头结点，因此，在任何时候都至少有一个结点，因此空表与非空表的运算相统一。　　（六）树与二叉树　　1．树的基本概念　　树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。\n　　在树结构中，每一个结点只有一个前件，称为父结点。如A即为结点B、C、D的父结点。　　没有父结点的结点只有一个，称为根结点。如上图所示，结点A即为根结点。　　每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、H、I是结点D的子结点。　　没有后件的结点，称为叶子结点。上图中，叶子结点有：J、M、N、L、C、G、H、I。　　在树结构中，一个结点所拥有的后件结点个数称为该结点的度。例如，结点D的度为3，结点E的度为1等，按此原则，所有叶子结点的度均为0。　　在树中，所有结点中最大的度称为该树的度。上图所示的树中，所有结点中最大的度是3，所以该树的度为3。　　树分层，根结点为第一层，往下依次类推。同一层结点的所有子结点均在下一层。如上图：A结点在第1层，B、C、D结点在第2层；E、F、G、H、I在第3层；J、K、L在第4层；M、N在第5层。　　树的最大层次称为树的深度。上图树的深度为5。　　在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。　　在计算机中，可以用树来表示算术表达式。原则如下：　　（1）表达式中每一个运算符在树中对应一个结点，称为运算符结点　　（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）　　（3）运算对象中的单变量均为叶子结点　　树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该结点的度而定义。\n　　如果在树中，每一个结点的子结点的个数不相同，因此在多重链中各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。　　2．二叉树及其基本性质　　1）二叉树的定义　　二叉树的特点：　　非空二叉树只有一个根结点　　每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，分别称为左子树和右子树　　在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。　　在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。　　2）二叉树的性质　　性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。　　性质2：深度为m的二叉树最多有2m-1个结点。　　性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。　　性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。3）满二叉树与完全二叉树　　（1）满二叉树　　满二叉树的特点：　　除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树上的第k层上有2k-1个结点。如下即为一棵满二叉树。\n　　（2）完全二叉树　　特点：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干个结点。　　即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。　　对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，若其右分支下的子树结点的最大层次为p，则其分支下的子结点的最大层次为p或p+1。　　完全二叉树具有的性质：　　性质5：具有n个结点的完全二叉树的深度为[log2n]+1　　性质6：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1、2……、n给结点编号，对于编号为k（k=1,2,……n）的结点有如下结论：　　①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。　　②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（当然也没有右子结点）\n　　③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。　　3．二叉树的存储结构　　二叉树的存储常采用链式存储结构。　　存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。　　存储结构如下：　　即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。　　如图所示的二叉树：　　如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：\n　　当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。　　4．二叉树的遍历　　二叉树的遍历即是不重复地访问二叉树的所有结点。　　在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。　　1）前序遍历　　前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。　　操作的具体方式：　　若二叉树为空，则结束返回。　　否则：访问根结点®前序遍历左子树®前序遍历右子树　　如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O\n　　2）中序遍历　　中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。　　具体的操作方式：　　若二叉树为空，则结束返回。　　否则：中序遍历左子树®访问根结点®中序遍历右子树　　这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。　　如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O　　3）后序遍历　　后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。　　具体的操作方式：　　若二叉树为空，则结束返回。　　否则：前序遍历左子树®前序遍历右子树®访问根结点　　如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A（七）查找技术　　查找即是指在一个给定的数据结构中查找某个指定的元素。　　1．顺序查找　　顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。　　基本操作方法是：　　从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都不相等，则该元素在指定的线性表中不存在。　　顺序查找的最好情况：要查找的元素在线性表的第一个元素，则查找效率最高；如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素，这种情况是最差情况。\n　　对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：　　线性表为无序表，即表中的元素没有排列不是按大小顺序进行排列的，这类线性表不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进行查找　　即使是有序线性表，如果采用链式存储，也只能采用顺序查找方式　　例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：　　整个线性表的长度为5　　查找计次n=1，将元素6与序列的第一个7元素进行比较，不等，继续查找　　n=2，将6与第二个元素2进行比较，不等，继续　　n=3，将6与第三个元素1进行比较，不等，继续　　n=4，将6与第四个元素5进行比较，不等，继续　　n=5，将6与第五个元素9进行比较，不等，继续　　n=6，将6与第六个元素4进行比较，不等，继续　　n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。　　2．二分查找　　二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列（即由小到大，但允许相邻元素值相等）。　　二分查找的方法如下：　　将要查找的元素与有序序列的中间元素进行比较：　　如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行查找　　如果要查找的元素的值比中间元素的值小，则继续在线性表的前半部分（中间项以前的部分）进行查找　　这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0（说明线性表中没有要查找的元素）　　有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是log2n次，而顺序查找的最坏情况的查找次数是n次。\n　　当然，二分查找的方法也支持顺序存储的递减序列的线性表。　　有非递减有序线性表：1、2、4、5、7、9，要查找元素6。查找的方法是：　　序列长度为n=6，中间元素的序号m=[(n+1)/2]=3　　查找计次k=1，将元素6与中间元素即元素4进行比较，不等，6>4　　查找计次k=2，查找继续在后半部分进行，后半部分子表的长度为3，计算中间元素的序号：m=3+[(3+1)/2]=5，将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，6<7　　查找计次k=3，继续查找在后半部分序列的前半部分子序列中查找，子表长度为1，则中间项序号即为m=3+[(1+1)/2]=4，即与第4个元素5进行比较，不相等，继续查找的子表长度为0，则查找结束　　（八）排序技术　　排序即是将一个无序的序列整理成按值非递减顺序排列的有序序列。在这里，我们讨论的是顺序存储的线性表的排序操作。　　1．交换类排序法　　交换类排序法，即是借助于数据元素之间的互相交换进行排序的方法。　　1）冒泡排序法　　冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。　　操作过程如下：　　从表头开始扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若相邻两个元素中前一个元素的值比后一个元素的值大，将两个元素位置进行交换，当扫描完成一遍时，则序列中最大的元素被放置到序列的最后。　　再继续对序列从头进行扫描，这一次扫描的长度是序列长度减1，因为最大的元素已经就位了，采用与前相同的方法，两两之间进行比较，将次大数移到子序列的末尾。　　按相同的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的长度为1时，排序结束。　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。　　采用冒泡排序法，具体操作步骤如下：　　序列长度n=7\n　　扫描的次数，最多需要扫描n-1次，如果序列已经就位，则扫描结束。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，则说明数据排序结束。　　2）快速排序法　　冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进行交换，可以消除多个逆序。　　快速排序的方法是：　　从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界线，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。　　再将前后两个子表再进行相同的快速排序，将子表再进行分割，直到所有的子表均为空，则完成快速排序操作。　　在快速排序过程中，随着对各子表不断的进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不用的子表记忆起来，这里可用栈来实现。\n　　对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表进行分割。　　这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。　2．插入类排序法　　1）简单插入排序　　插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。　　插入排序操作的思路：在线性表中，只包含第1个元素的子表，作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。　　该方法与冒泡排序方法的效率相同，最坏的情况下需要n(n-1)/2次比较。　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。　　采用简单插入排序法，具体操作步骤如下：　　序列长度n=7　　插入排序后的结果　　2）希尔排序法　　希尔排序法的基本思想：　　将整个无序序列分割成若干小的子序列分别进行插入排序。\n　　子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。　　增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n为待排序序列的长度。　　3．选择类排序法　　1）简单选择排序法　　基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。　　对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。　　采用简单选择排序法，具体操作步骤如下：　　2）堆排序法　　堆排序法属于选择类排序方法。　　堆的定义：具有n个元素的序列（h1,h2,…,hn），当且仅当满足　（I=1,2,…,n/2）时称之为堆。　　本节只讨论满足前者条件的堆。　　由堆的定义看，堆顶元素（即第一个元素）必为最大项。　　可以用一维数组或完全二叉树来表示堆的结构。　　用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的最大项。\n　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。　　操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5<9，将5与9进行交换；整后，对左右子树进行堆调整，左子树的根结点2小于其左叶子结点5，调整；右子树的根结点5小于其左右子结点7和6，根据堆的要求，将5与7进行调整。　　根据堆的定义，可以得到堆排序的方法：　　（1）首先将一个无序序列建成堆　　（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。　三、例题分析　　1．选择题　　1）算法指的是　　A）计算机程序　　B）解决问题的计算方法　　C）排序算法　　D）解决问题的有限运算序列　　【答案】D　　2）线性表采用链式存储时，结点的存储地址　　A）必须是不连续的　　B）连续与否均可　　C）必须是连续的\n　　D）和头结点的存储地址相连续　　【答案】B　　3）将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为　　A）O（1）　　B）O（n）　　C）O（m）　　D）O（m+n）　　【答案】C　　5）树型结构最适合用来描述　　A）有序的数据元素　　B）无序的数据元素　　C）数据元素之间的具有层次关系的数据　　D）数据元素之间没有关系的数据　　【答案】C　　6）若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树的结点数是　　A）15　　B）16　　C）17　　D）18　　【答案】D　　7）若某完全二叉树的深度为h，则该完全二叉树中至少有多少个结点　　A）2h　　B）2h-1　　C）2h-1-1\n　　D）2h-1+1　　【答案】B　　8）在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该　　A）只有左子树上的所有结点　　B）只有左子树上的部分结点　　C）只有右子树上的所有结点　　D）只有右子树上的部分结点　　【答案】A　　9）设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为　　A）front=front+1　　B）front=(front+1)%(m-1)　　C）front=(front-1)%m　　D）front=(front+1)%m　　【答案】D　　10）用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：　　20，15，21，25，47，27，68，35，84　　15，20，21，25，35，27，47，68，84　　15，20，21，25，27，35，47，68，84　　则所采用的排序方法是　　A）选择排序　　B）希尔排序　　C）归并排序　　D）快速排序\n　　【答案】D　　2．填空题　　1）数据的逻辑结构是从逻辑关系上描述数据，它与数据的_______无关，是独立于计算机的。　　【答案】存储（或存储结构）　　2）栈顶的位置是随着_______操作而变化的。　　【答案】进栈和退栈　　3）已知一棵完全二叉树中共有768结点，则该树中共有_______个叶子结点。　　【答案】384　　4）对于顺序存储的栈，因为栈的空间是有限的，在进行_______运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。　　【答案】进栈PUSH出栈POP　　5）在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_______，且存在一条从根到该结点的_______。　　【答案】前驱路径　　6）给出下列二叉树的前序遍历序列_______。　　【答案】CABEFDHG　　7）数据的逻辑结构被分为___________、____________、___________和___________四种。　　【答案】线性表队列栈树　　8）在一棵二叉树中，第5层上的结点数最多为_________。\n　　【答案】16　　9）以二分查我方法查找一个线性表时，此线性表必须是___________存储的________表。　　【答案】顺序有序　　10）在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为________。　　【答案】2　　四、小结　　通过本章的学习，要求了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利用图形的方式表示数据结构；了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的线性表的基本运算；了解栈和队列的基本概念，并掌握它们的基本运算；了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循环链表的基本概念和基本操作；理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存储结构和遍历技术；掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；学会利用相关的排序技术实现无序数列的排序操作。第二章程序设计基础　　一、学习目标与要求　　1．了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序设计的基本规则；　　2．了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点；　　3．了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。　　二、内容要点　　（一）程序设计方法与风格　　程序设计方法：主要经过了面向过程的结构化程序设计和面向对象的程序设计方法。　　程序设计风格，是指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。　　要形成良好的程序设计的风格，应考虑如下因素：　　1．源程序文档化\n　　（1）符号名的命名：符号名的命名要具有一定的实际含义，便于对程序的理解，即通常说的见名思义；　　（2）程序注释：正确的程序注释能够帮助他人理解程序。注释一般包括序言性注释和功能性注释；　　（3）视觉组织：为了使程序一目了然，可以对程序的格式进行设置，适当地通过空格、空行、缩进等使程序层次清晰。　　2．数据说明方法　　（1）数据说明的次序规范化；　　（2）说明语句中变量安排有序化；　　（3）使用注释来说明复杂的数据结构。　　3．语句的结构　　（1）在一行内只写一条语句；　　（2）程序的编写应该优先考虑清晰性；　　（3）除非对效率有特殊的要求，否则，应做到清晰第一，效率第二；　　（4）首先保证程序的正确，然后再要求速度；　　（5）避免使用临时变量使程序的可读性下降；　　（7）尽量使用库函数，即尽量使用系统提供的资源；　　（8）避免采用复杂的条件语句；　　（9）尽量减少使用“否定”条件的条件语句；　　（10）数据结构要有利于程序的简化；　　（11）要模块化，使模块功能尽可能单一化；　　（12）利用信息隐蔽，确保每一个模块的独立性；　　（13）从数据出发去构造程序；　　（14）不要修补不好的程序，要重新编写。　　4．输入和输出\n　　（1）对所有的输入输出数据都要检验数据的合法性；　　（2）检查输入项的各种重要组合的合理性；　　（3）输入格式要简单，以使得输入的步骤和操作尽可能简单；　　（4）输入数据时，应允许自由格式；　　（5）应允许缺省值；　　（6）输入一批数据时，最好使用输入结束标志；　　（7）以交互式输入输出方式进行输入时，要在屏幕上使用提示符明确输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；　　（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。　　（二）结构化程序设计　　1．结构化程序设计的原则　　结构化程序设计方法的主要原则：自顶而下、逐步求精，模块化，限制使用goto语句。　　1）自顶而下　　程序设计时，应先考虑总体，后考虑细节；先考虑全局，后考虑局部目标。即先从最上层总目标开始设计，逐步使问题具体化。　　2）逐步求精　　对复杂问题，应设计一些子目标作为过渡，逐步细化。　　3）模块化　　一个复杂问题，都是由若干个稍简单的问题构成的。模块化即是将复杂问题进行分解，即将解决问题的总目标分解成若干个分目标，再进一步分解为具体的小目标，把每一个小目标称作一个模块。　　4）限制使用goto语句　　goto语句可以提高效率，但对程序的可读性、维护性都造成影响，因此应尽量不用goto语句。　　2．结构化程序设计的基本结构与特点\n　　结构化程序设计是程序设计的先进方法和工具，采用结构化程序设计可以使程序结构良好、易读、易理解、易维护。　　1）顺序结构　　顺序结构即是顺序执行的结构，是按照程序语句行的自然顺序，一条一条语句地执行程序。　　2）选择结构　　选择结构又称分支结构，它包括简单选择和多分支选择结构。程序的执行是根据给定的条件，选择相应的分支来执行。　　3）重复结构　　重复结构又称循环结构，根据给定的条件，决定是否重复执行某一相同的或类似的程序段。利用重复结构可以大量简化程序行。　　3．结构化程序设计原则和方法的应用　　1．使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；　　2．选用的控制结构只允许有一个入口和一个出口；　　3．程序语句组成容易识别的块，每块只有一个入口和一个出口；　　4．复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；　　5．语言中所有没有的控制结构，应该采用前后一致的方法来模拟；　　6．严格控制goto语句的使用：　　（1）用一个非结构化的程序设计语言去实现一个结构化的构造；　　（2）若不使用goto语句会使功能模糊；　　（3）在某种可以改善而不是损害程序可读性的情况下。（三）面向对象的程序设计　　1．关于面向对象方法　　面向对象方法的本质，是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够反映问题域，即系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。\n　　面向对象的优点：　　1）与人类习惯的思维方法一致　　传统的程序设计方法是以算法作为核心，将程序与过程相互独立。　　面向对象方法和技术是以对象为核心，对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以实现模拟世界中不同事物之间的联系。　　2）稳定性好　　面向对象方法基于构造问题领域的对象模型，以对象为中心构造软件系统。它的基本方法是用对象模拟问题领域中的实体，以对象间的联系刻画实体间的联系。　　3）可重用性好　　软件的重用性是指在不同的软件开发过程中重复使用相同或相似的软件元素的过程。　　4）易于开发大型软件产品　　在使用面向对象进行软件开发时，可以把大型产品看作是一系列本质上相互独立的小产品来处理，降低了技术难度，也使软件开发的管理变得容易。　　5）可维护性好　　（1）利用面向对象的方法开发的软件稳定性比较好　　（2）用面向对象的方法开发的软件比较容易修改　　（3）用面向对象的方法开发的软件比较容易理解　　（4）易于测试和调试　　2．面向对象方法的基本概念　　1）对象　　在面向对象程序设计方法中，对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它执行的一组操作组成。　　对象的基本特点：　　（1）标识的唯一性　　对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。\n　　（2）分类性　　指可以将具有相同属性和操作的对象抽象成类。　　（3）多态性　　指同一个操作可以是不同对象的行为。　　（4）封装性　　从外面看只能看到对象的外部特征，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。　　（5）模块独立性好　　对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内容各种元素彼此相结合得很紧密，内聚性强。　　2）类和实例　　将属性、操作相似的对象归为类。具有共同的属性、共同的方法的对象的集合，即是类。　　类是对象的抽象，它描述了属于该对象的所有对象性质，而一个对象则是其对应类的一个实例。　　3）消息　　消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一个要求的信息，它统一了数据流和控制流。　　消息只包含传递者的要求，它告诉接受者需要做哪些处理，并不指示接受者怎样去完成这些处理。　　4）继承　　继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可作为派生类来引用。　　继承即是指能够直接获得已有的性质和特征，而不必重复定义它们。　　5）多态性　　对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。\n　　在面向对象技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息可以发送给父类对象也可以发送给子类对象。　　多态性机制增加了面向对象软件系统的灵活性，减少了信息冗余，而且显著提高了软件的可重用性可扩充性。　　三、例题分析　　1．选择题　　1）程序是计算任务的　　A）处理对象的描述　　B）计算方法的表示　　C）软件动作的描述　　D）处理对象和处理规则的描述　　【答案】D　　2）结构化方法的详细设计，其主要任务是_________。　　A）定义模块的算法　　B）给出加工说明　　C）给出模块结构图　　D）设计处理对象　　【答案】C　　3）结构化程序设计主要强调的是　　A）程序的规模　　B）程序的效率　　C）程序设计语言的先进性　　D）程序易读性　　【答案】D　　4）程序的三种基本控制结构是\n　　A）过程、子程序和分程序　　B）顺序、选择和重复　　C）递归、堆栈和队列　　D）调用、返回和转移　　【答案】B　　5）程序的三种基本控制结构的共同特点是　　A）不能嵌套使用　　B）只能用来写简单程序　　C）已经用硬件实现　　D）只有一个入口和一个出口　　【答案】D　　6）下面对对象概念描述错误的是　　A）任何对象都必须有继承性　　B）对象是属性和方法的封装体　　C）对象间的通讯靠消息传递　　D）操作是对象的动态属性　　【答案】A　　2．填空题　　1）在面向对象方法中，信息隐蔽是通过对象的_________性来实现的。　　【答案】封装　　2）类是具有共同属性、共同方法的_________的集合。　　【答案】对象　　3）在面向对象方法中，类之间共享属性和操作的机制称为_________。　　【答案】继承\n　　四、小结　　通过本章的学习，要求了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序设计的基本规则；了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点；了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。第三章软件工程基础　　一、学习目标与要求　　1．了解软件工程的基本概念；　　2．了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；　　3．了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需求分析的方法和需要完成的任务；　　4．了解数据流图的使用方法；　　5．了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些常用用工具；　　6．了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件测试方法的区别和各自的功能与特点；　　7．了解程序调试的方法和原则。　　二、内容要点　　（一）软件工程基本概念　　1．软件定义与软件特点　　1）软件的定义　　与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。　　2）软件的特点　　（1）软件是一种逻辑实体，而不是物理实体，具有抽象性；　　（2）软件的生产与硬件不同，它没有明显的制作过程；　　（3）软件在运行、使用期间不存在磨损、老化问题；但为了适应硬件、环境以及需求的变化要进行修改，会导致一些错误的引入，导致软件失效率升高，从而使得软件退化；\n　　（4）软件的开发、运行对计算机系统具有依赖性，受到计算机系统的限制，这导致了软件移植的问题；　　（5）软件复杂性高，成本昂贵。软件开发需要投入大量、高强度的脑力劳动，成本高，风险大；　　（6）软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户的机构设置，体制问题以及管理方式等，甚至涉及到人们的观念和心理，软件知识产权及法律等问题。　　3）软件的分类　　按功能分，可分为：　　应用软件：为解决特定领域的应用而开发的软件　　系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件　　支撑软件（或工具软件）：介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件　　2．软件危机与软件工程　　1）软件危机　　泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。它主要表现在：　　（1）软件需求的增长得不到满足，用户对系统不满意的情况经常发生；　　（2）软件开发成本和进度无法控制。开发的成本超预算和开发周期的超期经常出现；　　（3）软件质量难以保证；　　（4）软件不可维护或维护程度非常低；　　（5）软件成本不断提高；　　（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。　　2）软件工程　　软件工程的定义：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。　　软件工程包括3个要素：方法、工具和过程。\n　　方法：完成软件工程项目的技术手段；　　工具：支持软件的开发、管理、文档生成；　　过程：支持软件开发的各个环节的控制、管理。　　3．软件工程过程与软件生命周期　　1）软件工程过程　　软件工程过程把输入转化为输出的一组彼此相关的资源和活动。支持软件工程过程的两方面内涵：　　（1）软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。它包括4种基本活动：　　P—软件规格说明。规定软件的功能及其运行时的限制；　　D—软件开发。产生满足规格说明的软件；　　C—软件确认。确认软件能够满足客户提出的要求；　　A—软件演进过程。为满足客户的变更要求，软件必须在使用的过程中演进。　　（2）使用适当的资源（包括人员、硬软件工具、时间等），为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。　　软件工程过程是将软件工程的方法和工具综合起来，以达到合理、及时地进行计算机软件开发的目的。　　2）软件生命周期　　将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。即软件的生命周期就是软件产品从开始考虑其概念开始，到软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。这些活动可以有重复，执行时也可以有迭代。　　生命周期的主要阶段：　　软件定义　　软件开发　　软件维护　　软件生命周期的主要活动阶段是：\n　　（1）可行性研究与计划制定：确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实话计划；　　（2）需要分析。对待开发软件提出的需求进行分析并给出详细的定义；　　（3）软件设计。系统设计人员和程序设计人员给出软件的结构、模块的划分、功能的分配以及处理流程；　　（4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划；　　（5）软件测试。在设计测试用例的基础上，检验软件的各个组成部分，编写测试分析报告；　　（6）运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要且可能的扩充和删改。　　4．软件工程的目标与原则　　1）软件工程的目标　　软件工程的目标：在给定成本、进度的情况下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。　　软件工程需要达到的基本目标：　　付出较低的开发成本　　达到要求的软件功能　　取得较好的软件性能　　开发的软件易于移植　　需要较低的维护费用　　能按时完成开发，及时交付使用　　软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。　　（1）软件开发技术　　软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。软件开发方法学是根据不同的软件类型，按不同的观点和原则，对软件开发中应遵循的策略、原则、步骤和必须产生的文档资料都做出规定，从而使软件开发能够进入规范化和工程化的阶段。\n　　（2）软件工程管理　　软件工程管理：软件管理学、软件工程经济学、软件心理学等内容。　　软件工程管理学包括：人员组织、进度安排、质量保证、配置管理、项目计划等。　　软件工程经济学：是研究软件开发中成本的估算、成本效益分析的方法和技术，用经济学的基本原理事研究软件工程开发中的经济效益问题。　　软件心理学：从个体心理、人类行为、组织行为和企业文化等角度来研究软件管理和软件工程。2）软件工程的原则　　（1）抽象。抽取事物取基本的特征和行为，忽略非本质细节。采用分层次抽象，自顶向下，逐层细化的办法控制软件开发过程的复杂性；　　（2）信息隐蔽。采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单；　　（3）模块化。模块是程序中相对独立的成分，一个独立的编程单位，应有良好的接口定义。块太大会使模块内部过渡复杂，不利于对模块的理解和修改，也不利于模块的调试和重用；模块太小会使程序结构过于复杂，难于控制；　　（4）局部化。在同一个物理模块中集中逻辑上相互关联的计算资源，保证模块间具有松散的耦合关系，模块内部有较强的内聚性；　　（5）确定性。所有的概念表达应是确定的、无歧义且规范。　　（6）一致性。包括程序、数据和文档的整个软件系统的各模块应使用已知的概念、符号和术语；程序内外部接口保持一致，系统规格说明与系统行为应保持一致；　　（7）完备性。软件系统不丢失任何重要成份，完全实现系统所需要的功能；　　（8）可验证性。开发大型软件系统需要对系统自顶向下，逐层分解。　　5．软件开发工具与软件开发环境　　1）软件开发工具　　早期的软件开发，最早使用的是单一的程序设计语言，没有相应的开发工具，效率很低，随着软件开发工具的发展，提供了自动的或半自动的软件支撑环境，为软件开发提供了良好的环境。　　2）软件开发环境\n　　软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。　　计算机辅助软件工程将各种软件工具、开发机器和一个存放开发过程信息的中心数据库组成起来，形成软件工程环境。　　（二）结构化分析方法　　1．需求分析与需求分析方法　　1）需求分析　　软件需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。　　（1）定义　　软件需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。　　（2）需求分析阶段的工作　　①需求获取。需求获取的目的是确定对目标系统的各方面需求；　　②需求分析。对获取的需求进行分析和综合，最终给出系统的解决方案和目标系统的逻辑模型；　　③编写需求规格说明书。为用户、分析人员和设计人员之间进行交流提供方便。　　④需求评审。对需求分析阶段的工作进行复审，验证需求文档的一致性、可靠性、完事性和有效性。　　2）需求分析方法　　（1）结构化分析方法　　包括：　　面向数据流的结构化分析方法　　面向数据结构的Jackson方法　　面向数据结构的结构化数据系统开发方法　　（2）面向对象的分析方法　　从需求分析建立模型的特性分，需求分析方法又分为静态分析方法和动态分析方法。\n　　2．结构化分析方法　　1）关于结构化分析方法　　结构化分析方法的实质是：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。　　结构化分析的步骤：　　通过对用户的调查，以软件需求为线索，获得系统的具体模型；　　去掉模型的非本质因素，抽象出系统的逻辑模型；　　根据计算机的特点分析当前系统与目标系统的差别，建立目标系统的逻辑模型；　　完善目标系统交补充细节，写出目标系统的软件需求规格说明；　　评审直到确认完全符合用户对软件的需求。　　2）结构化分析的常用工具　　（1）数据流图　　数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。　　数据流图下的图形元素：　　（圆），加工（转换）。输入数据经过加工变换产生输出　　（箭头），数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名　　（平行的二条直线），存储文件（数据源）。表示处理过程中存放各种数据的文件。　　（长方形），源，潭。表示系统和环境的接口，属于系统之外的实体。　　（2）数据字典　　数据字典是结构化分析方法的核心。对数据流图中出现的被命名的图形元素的确切解释。通常包括：名称、别名、何处使用/如何使用、内容描述、补充信息等。　　（3）判定树　　利用判定树，对数据结构中的数据之间的关系进行描述，弄清楚判定条件之间的从属关系、并列关系、选择关系。　　（4）判定表\n　　在数据流图中的加工要依赖于多个条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的情况。它与判定树是相似的，但更适宜于较复杂的条件组合。　　3．软件需求规格说明书　　是需求分析阶段的最后成果，是软件开发的重要文档之一。　　1）作用　　便于用户、开发人员进行理解和交流　　反映用户问题的结构，可以作为软件开发工作的基础和依据　　作为确认测试和验收的依据　　2）内容　　在软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他与要求有关的数据。　　3）特点　　软件需求规格说明书是确保软件质量的措施，它的内涵是：　　正确性　　无歧义性　　完整性　　可验证性　　一致性　　可理解性　　可修改性　　可追踪性（三）结构化设计方法　　1．软件设计的基本概念　　1）软件设计的基础\n　　软件设计包括软件结构设计、数据设计、接口设计、过程设计。其中，结构设计是定义软件系统各主要部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信；过程设计是把系统结构部件转换成软件的过程性描述。　　软件设计的一般过程：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。　　2）软件设计的基本原理　　（1）抽象　　抽象的层次从概要设计到详细设计逐渐降低。在软件概要设计中的模块分层也是由抽象到具体逐步分析和构造出来的。　　（2）模块化　　模块是指把一个待开发的软件分解成若干小的简单的部分。　　模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。　　（3）信息隐蔽　　在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。　　（4）模块独立性　　独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。　　衡量软件的模块独立性的标准：　　内聚性：一个模块内部各个元素间彼此结合的紧密程度的度量　　耦和性：模块间相互连接的紧密程序的度量　　3）结构化设计方法　　即将软件设计成相对独立、单一功能的模块组成结构。　　2．概要设计　　1）概要设计的任务　　①设计软件系统结构\n　　即将系统划分成模块以及模块的层次结构。　　②数据结构及数据库设计　　数据设计是实现需求定义和规格说明过程中提出的数据对象的逻辑表示。　　数据设计的具体任务是：　　确定输入、输出文件的详细数据结构　　结合算法设计，确定算法所必须的逻辑数据结构及其操作　　确定对逻辑数据结构所必须的那些操作的程序模块，限制和确定各个数据设计决策的影响范围　　需要与操作系统或调度程序接口所必须的控制表进行数据交换时，确定其详细的数据结构和使用规则　　数据的保护性设计：防卫性、一致性、冗余性设计　　③编写概要设计文档　　需要编写的文档有：　　概要设计说明书　　数据库设计说明书　　集成测试计划　　④概要设计文档评审　　需要评审的内容：设计部分是否完整地实现了需求中规定的功能、性能等要求，设计方案的可行性，关键的处理及内外部接口定义的正确性、有效性，各部分之间的一致性等　　软件结构设计工具是结构图，描述软件系统的层次和分块结构关系，它反映了整个系统的功能实现以及模块与模块之间的联系与通讯，是未来程序中的控制层次体系。　　结构图的元素：　　矩形表示一个模块，在矩形内注明模块的功能和名字　　箭头表示模块间的调用关系。带实心圆的箭头表示传递的是控制信息，带空心圆的箭头表示传递的是数据　　结构图中常有的模块类型：\n　　传入模块　　传出模块　　变换模块　　协调模块　　2）面向数据流的设计方法　　①数据流类型　　变换型。将数据流分成三个部分：输入数据、中心变换和输出数据三个部分。　　事务型。在事务中心接收数据，分析数据以确定它的类型，再选取一条活动的通路　　②面向数据流设计方法的实施要点与设计过程　　3）设计的准则　　提高模块的独立性　　模块规模适中　　深度、宽度、扇出和扇入适当　　使模块的作用域在该模块的控制域内　　应减少模块的接口和界面的复杂性　　设计成单入口、单出口的模块　　设计功能可预测的模块　　3．详细设计　　详细设计，即为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种工具表示算法和数据结构的细节。　　常用的设计工具有：　　图形工具：程序流程图，N-S，PAD，HIPO　　表格工具：判定表　　语言工具：PDL（伪码）\n　　（四）软件测试　　1．软件测试的目的　　使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是否弄清预期的结果与实际结果之间的差别。　　2．软件测试的准则　　所有测试应追溯到需求　　严格执行测试计划，排除测试的随意性　　充分注意测试中的群集现象　　程序员应避免检查自己的程序　　穷举测试不可能　　妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便　　3．软件测试技术与方法综述　　1）静态测试与动态测试　　静态测试包括：代码检查、静态结构分析、代码质量度量等。　　动态测试是基于计算机的测试，根据软件需求设计测试用例，利用这些用例去运行程序，以发现程序错误的过程。　　2）白盒测试方法与测试用例设计　　白盒测试也称结构测试或逻辑驱动测试。　　白盒测试的原则：保证所有的测试模块中每一条独立路径至少执行一次；保证所有的判断分支至少执行一次；保证所有的模块中每一个循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性　　主要的方法有：逻辑覆盖（包括语句覆盖、路径覆盖、判定覆盖、条件覆盖和判断—条件覆盖）、基本路径测试等　　3）黑盒测试方法与测试用例设计　　黑盒测试方法也称功能测试或数据驱动测试，是对软件已经实现的功能是否满足需求进行测试和验证。\n　　黑盒测试主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错。　　黑盒测试方法主要有：等价类划分法（包括有效等价类和无效等价类）、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。4．软件测试的实施　　1）单元测试　　对模块进行测试，用于发现模块内部的错误　　2）集成测试　　测试和组装软件的过程，主要用于发现与接口有关的错误。　　集成测试包括的内容：软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试等。　　集成测试分为：增量方式组装（包括自顶而下、自底而上、自顶向下和自底向上的混合增量方式）与非增量方式组装。　　3）确认测试　　验证软件的功能和性能及其他特征是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确。　　4）系统测试　　将经过测试后的软件，与计算机的硬件、外设、支持软件、数据和人员等其他元素组合在一起，在实际运行环境中进行一系列的集成测试和确认测试。　　（五）程序的调试　　1．基本概念　　程序调试活动包括：根据错误的迹象确定程序中错误的确切性质、原因和位置；对程序进行修改，排除错误。　　1）基本步骤进行回溯测试，防止引进新的错误。®修改设计和代码，以排除错误®　　错误定位　　2）程序调试的原则　　（1）确定错误的性质和位置\n　　分析与错误有关的信息　　避开死胡同　　调试工具只是一种辅助手段，只能帮助思考，不能代替思考　　避免用试探法　　（2）修改错误的原则　　在出现错误的地方，有可能还有别的错误，在修改时，一定要观察和检查相关的代码，以防止其他的错误　　一定要注意错误代码的修改，不要只注意表象，而要注意错误的本身，把问题解决　　注意在修正错误时，可能代入新的错误，错误修改后，一定要进行回归测试，避免新的错误产生　　修改错误也是程序设计的一种形式　　修改源代码程序，不要改变目标代码　　2．软件调试方法　　1）强行排错法　　通过内存全部打印来排错　　在程序特定部位设置打印语句—即断点法　　自动调试工具。　　2）回溯法　　适合小规模程序的排错。发现错误，分析错误表象，确定位置，再回溯到源程序代码，找到错误位置或确定错误范围。　　3）原因排除法　　原因排除法包括：演绎法、归纳法和二分法。　　演绎法：是一种从一般原理或前提出法，经过排除和精化的过程来推导出结论的思考方法。　　归纳法：从一种特殊推断出一般的系统化思考方法。其基本思想是从一些线索着手，通过分析寻找到潜在的原因，从而找出错误。\n　　二分法：如果已知每个变量在程序中若干个关键点的正确值，则可以使用定值语句在程序中的某点附近给这些变量赋值，然后运行程序并检查程序的输出。　　三、例题分析　　1．选择题　　1）软件开发的需求活动，其主要任务是　　A）给出软件解决方案　　B）给出系统模块结构　　C）定义模块算法　　D）定义需求并建立系统模型　　【答案】D　　2）软件可用性意指　　A）用户界面友好的程度　　B）软件结构、实现及文档为用户可用的程度　　C）修改软件错误的难易程度　　D）符合用户使用习惯的程度　　【答案】B　　3）软件过程是　　A）特定的开发模型　　B）一种软件求解的计算逻辑　　C）活动的集合　　D）软件生存周期模型　　【答案】D　　4）需求分析阶段的任务是确定　　A）软件开发方法\n　　B）软件开发工具　　C）软件开发费　　D）软件系统的功能　　【答案】D　　5）软件测试方法中的静态测试方法之一为　　A）静态结构分析　　B）黑盒法　　C）路径覆盖　　D）边界值分析　　【答案】A　　6）可行性研究要进行一次什么类型的需求分析　　A）详细的　　　B）全面的　　C）简化的、压缩的　　　D）彻底的　　【答案】C　　7）软件开发过程中，抽取和整理用户需求并建立问题域精确模型的过程叫　　A）生存期　　B）面向对象设计　　C）面向对象程序设计　　D）面向对象分析　　【答案】D　　8）原型化方法是一种什么型的设计过程　　A）自外向内B）自顶向下\n　　C）自内向外D）自底向上　　【答案】A　　9）为了提高测试的效率，应该__________。　　A）随机地选取测试数据　　B）取一切可能的输入数据作为测试数据　　C）在完成编码以后制定软件的测试计划　　D）选择发现错误可能性大的数据作为测试数据　　【答案】D　　10）使用白盒测试方法时，确定测试数据应根据什么和指定的覆盖标准。　　A）程序的内部逻辑　　B）程序的复杂结构　　C）使用说明书　　D）程序的功能　　【答案】A　　2．填空题　　1）软件工程的基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、__________和__________。　　【答案】完备性可验证性　　2）系统流程图是描述物理模型的传统工具，用图形符号表示系统中各个元素表达了系统中各种元素之间的__________情况。　　【答案】信息流动　　3）详细设计的任务是确定每个模块的内部特性，即模块的算法、__________。　　【答案】使用的数据　　4）所有软件维护申请报告要按规定方式提出，该报告也称__________报告。　　【答案】软件问题\n　　5）软件测试过程一般包括4个步骤，即单元测试、集成测试、验收测试（确认测试）和__________。　　【答案】系统测试　　四、小结　　通过本章的学习，要求了解软件工程的基本概念；了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需求分析的方法和需要完成的任务；了解数据流图的使用方法；了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些常用工具；了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件测试方法的区别和各自的功能与特点；了解程序调试的方法和原则。　Point4：程序设计方法与风格　　考点精讲　　1、养成良好的程序设计的设计风格，主要应考虑下述因素：　　(1)源程序文档化：①符号名的命名有一定含义，便于理解；②正确的注释帮助读者理解程序；③程序层次清晰。　　-16-　　(2)数据说明的方法：①数据说明的次序规范化；②说明语句中变量安排有序化；③使月注释来说明复杂数据结构。　　(3)语句的结构：程序应该简单易懂，语句构造应该简单直接。　　(4)输入和输出。　　2、注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。　　真题分析　　【真题1】下列选项不符合良好程序设计风格的是________。（2006年9月）　　A)避免滥用goto语句　　B)模块设计要保证高耦合、高内聚　　C)源程序要文档化　　D)数据说明的次序要规范化\n　　解析：编程风格是在不影响性能的前提下，有效地编排和组织程序，以提高可读性和可维护性。更直接地说，风格就是意味着要按照规则进行编程。这些规则包括:编程风格是在不影响性能的前提下，有效地编排和组织程序，以　　提高可读性和可维护性。更直接地说，风格就是意味着要按照规则进行编程。　　(1)程序文档化。就是程序文档包含恰当的标识符，适当的注解和程序的视觉组织等。　　(2)数据说明。出于阅读理解和维护的需要，最好使模块前的说明语句次序规范化。此外，为方便查找，在每个说明语句的说明符后，数据名应按照字典顺序排列。　　(3)功能模块化。即把源程序代码按照功能划分为低耦合、高内聚的模块。　　(4)注意goto语句的使用。合理使用goto语句可以提高代码的运行效率，但goto语句的使用会破坏程序的结构特性。因此，除非确实需要，否则最好不使用goto语句。　　答案：B　　【真题2】下列叙述中，不符合良好程序设计风格要求的是________。（2007年9月）　　A)程序中要有必要的注释　　B)输入数据前要有提示信息　　C)程序的效率第一，清晰第二　　D)程序的可读性好　　解析：一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序设计风格总体而言应该强调简单和清晰，程序必须是可以理解的。著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。　　答案：C　Point5：结构化程序设计　　考点精讲　　1、结构化程序设计的主要目的是使程序结构良好、易读、易理解、易维护。它的原则主要包括：①自顶向下；②逐步求精；③模块化；④限制使用goto语句。　　2、结构化程序设计方法可用三种基本结构实现：①顺序结构；②选择结构；③重复结构。3、在结构化程序设计的具体实施中，要注意把握如下要素：　　(1)使用程序设计语言中的顺序结构、选择结构、循环结构等控制结构来表示程序的控制逻辑。\n　　(2)选用的控制结构只准许有一个入口和一个出口。　　(3)程序语句组成容易识别的程序块，每块只有一个入口和一个出口。　　(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。　　(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。　　(6)严格控制goto语句的使用。　　真题分析　　【真题1】下列选项中不属于结构化程序设计原则的是________。（2009年9月）　　A)模块化　　B)逐步求精　　C)可封装　　D)自顶向下　　解析：结构化程序设计的原则主要包括：①自顶向下；②逐步求精；③模块化；④限制使用goto语句。　　答案：C　　【真题2】符合结构化原则的三种基本控制结构是：选择结构、循环结构和__【3】__结构。（2009年3月）　　解析：结构化程序设计的3种基本控制结构是：选择结构（分支结构）、循环　　结构、顺序结构。　　答案：顺序　　【真题3】结构化程序设计的基本原则不包括________。（2008年4月）　　A)模块化　　B)逐步求精　　C)多态性　　D)自顶向下\n　　-18-解析：结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化和限制使用GOTO语句，其中不包括多态性。　　答案：C　　【真题4】下列选项中不属于结构化程序设计方法的是________。（2006年4月）　　A)模块化　　B)可复用　　C)自顶向下　　D)逐步求精　　解析：结构化程序设计方法的主要原则有四点：自顶向下(先从最上层总目标开始设计，逐步使问题具体化)、逐步求精(对于复杂问题，设计一些子目标作为过渡，逐步细化)、模块化(将程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标作为一个模块)、限制使用GOTO语句。不存在可复用原则。　　答案：B　　【真题5】仅由顺序、选择(分支)和重复(循环)结构构成的程序是__【4】__程序。（2010年9月）　　解析：本题主要考查结构化程序的基本概念。仅由顺序、选择(分支)和重复(循　　环)结构构成的程序是结构化程序。　　答案：结构化　Point6：面向对象的程序设计方法　　考点精讲　　1、对象(object)：对象用来表示客观世界中的任何实体。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。　　2、类(class)和实例(instance)：将属性、操作相似的对象归为类，类是具有共同属性、共同方法的对象的集合；一个具体对象称为类的实例。　　3、消息(message)：面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这个机制称为消息。消息是一个实例与另一个实例之间传递的信息，是请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。\n　　-19-　　4、继承(inheritance)：继承是面向对象方法的一个主要特征。继承是使用已有的类作为基础（直接获得已有的性质和特征）建立新类的定义技术。已有的类可以当做基类引用，则新类可当做派生类引用。　　5、多态性(polymorphism)：对象根据所接受的消息而作出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。　　真题分析　　【真题1】在面向对象方法中，不属于“对象”基本特点的是________。（2008年9月）　　A)多态性　　B)标识唯一性　　C)一致性　　D)分类性　　解析：对象具有如下特征：标识唯一性、分类性、多态性、封装性、模块独立　　性。　　答案：C　　【真题2】在面向对象方法中，实现信息隐蔽是依靠________。（2007年9月）　　A)对象的封装　　B)对象的分类　　C)对象的继承　　D)对象的多态　　解析：对象的封装性是指从外部看只能看到对象的外部特征，即只需知道数据的取值范围和可以对该数据施加的操作，而不需要知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。　　答案：A　　【真题3】在面向对象方法中，__【2】__描述的是具有相似属性与操作的一组对象。（2006年4月）\n　　解析：在面向对象方法中，类描述的是具有相似属性与操作的一组对象。　　答案：类　　【真题4】在面向对象方法中，类的实例称为__【2】__。（2005年4月）　　解析：类描述的是具有相似性质的一组对象。例如，每本具体的书是一个对　　象，而这具体的书都有共同的性质，它们都属于更一般的概念“书”这一类对象。　　一个具体的对象称为类的实例。　　答案：对象　　-20-　　【真题5】下面选项中不属于面向对象程序设计特征的是________。（2007年3月）　　A)类比性　　B)封装性　　C)继承性　　D)多态性　　解析：向对象程序设计的三个主要特征是：封装性、继承性和多态性。　　1、封装性即只需知道数据的取值范围和可以对该数据施加的操作，而无需知道　　数据的具体结构以及实现操作的算法。　　2、继承性是指使用已有的类定义作为基础建立新类的定义技术。　　3、对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致　　完全不同的行动，该现象称为多态性。　　答案：A　　【真题6】面向对象方法中，继承是指________。（2010年9月）　　A)各对象之间的共同性质　　B)类之间共亨属性和操作的机制　　C)一组对象所具有的相似性质\n　　D)一个对象具有另一个对象的性质　　解析：继承性指的是一个新类可以从现有的类中派生出来，新类具有父类中所有的特性，直接继承了父类的操作和属性，同时也允许多个新类继承于一个父类，也可以实现多层继承，可以说继承是类之间共享属性和操作的机制。　　答案：B　Point7：基本排序与查找的算法　　考点精讲　　1、查找　　(1)顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于长度为n的有序线性表，在最坏情况下，顺序查找需要比较n次。　　(2)对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：　　①无序的线性表；　　②即使是有序的线性表，如果采用链式存储结构，也只能顺序查找。　　-21-(3)二分查找是针对有序表进行查找的简单、有效而又较常用的方法。其基本思想是：首先选择有序表中间位置的记录，将其关键字与给定关键字k进行比较，若相等，则查找成功；否则，若k值比该关键字值大，则要找的元素一定在表的后半部分(或称右子表)，则继续对右子表进行二分查找；若k值比该关键字值小，则要找的元素一定在表的前半部分(左子表)，同样应继续对左子表进行二分查找。每进行一次比较，要么找到要查找的元素，要么将查找的范围缩小一半。如此递推，直到查找成功或把要查找的范围缩小为空(查找失败)。　　(4)显然，仅当有序线性表为顺序存储时才能用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。　　2、排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常用的排序方法(1)交换类排序法：　　①冒泡排序法，需要比较的次数为n(n-1)/2；　　②快速排序法，最坏情况需要比较的次数为n(n-1)/2。　　(2)插入类排序法：\n　　①简单插入排序法，最坏情况需要n(n-1)/2次比较；　　②希尔排序法，最坏情况需要O(n1.5)次比较。　　(3)选择类排序法：　　①简单选择排序海最坏情况需要n(n-1)/2次比较；　　②堆排序法，最坏情况需要O(nlog2n)次比较。　　真题分析　　【真题1】下列排序方法中，最坏情况下比较次数最少的是________。（2009年3月）　　A)直接插入排序　　B)堆排序　　C)冒泡排序　　D)简单选择排序　　解析：冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为：n(n-1)/2。而堆排序法在最坏的情况下需要比较的次数为O(nlog2n)　　答案：B　　【真题2】对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是________。（2008年4月）　　A)直接插入排序　　B)堆排序　　C)快速排序　　D)冒泡排序　　　　-22-解析：排序方法中最坏情况下需要比较的次数分别为：冒泡排序n(n-1)/2、　　快速排序n(n-1)/2、简单插入排序n(n-1)/2、希尔排序O(n^1.5)、简单选择排序n(n-1)/2、堆排序O(nlog2n)。　　答案：B\n　　【真题3】冒泡排序在最坏情况下的比较次数是________。（2007年9月）　　A)n(n-1)/2　　B)n/2　　C)n(n+1)/2　　D)nlog2n　　解析：对n个结点的线性表采用冒泡排序，在最坏情况下，冒泡排序需要经过n遍的从前往后的扫描和(n-1)/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。　　答案：A　　【真题4】对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__【1】__。（2006年4月）　　解析：在冒泡排序中，最坏情况下，需要比较的次数为n(n-1)/2，也就是：　　10*(10-1)/2=45。　　答案：45　　【真题5】对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是________。（2005年4月）　　A)快速排序为n　　B)快速排序为n(n-1)/2　　C)冒泡排序为n/2　　D)冒泡排序为n　　解析：假设线性表的长度为n，在最坏情况下，冒泡排序和快速排序需要的比　　较次数为n(n-1)/2。　　答案：B　　【真题6】在长度为n的有序线性表中进行二分法查找，最坏情况下需要比较的次数是________。（2008年9月）　　A)O(log2n)　　B)O(nlog2n)\n　　C)O(n)　　D)O(n)2　　解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需比较n次。　　答案：A　　-23-【真题7】在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为________。（2006年9月）　　A)6　　B)7　　C)63　　D)64　　解析：在长度为64的有序线性表中，其中的64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后按照线性表的顺序查找算法。　　首先用被查找的数据和线性表的第一个数据元素进行比较，若相等，则查找成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。　　因此，在长度为64的有序线性表中进行顺序查找，最坏的情况下需要比较64次。　　答案：D　　【真题8】下列数据结构中，能用二分法进行查找的是________。（2005年9月）　　A)二叉链表　　B)有序线性链表　　C)顺序存储的有序线性表　　D)线性链表　　解析：二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)的。\n　　答案：C　　【真题9】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为________。（2005年4月）　　A)n　　B)n+1　　C)log2n　　D)n/2　　解析：在长度为n的线性表中进行顺序查找，最坏情况下需要比较n次。　　答案：A　　【真题10】下列叙述中正确的是________。（2010年3月）　　A)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)　　B)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)　　C)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n　　D)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)　　解析：二分查找要求线性表中的结点必须按关键字值的递增或递减的顺序排序。它首先把要查找的关键字K与中间位置的结点关键字相比较，若相等，则查找成功；若不相等，则缩小范围。根据关键字与中间结点关键字的比较大小确定下一步查找哪个子表，这样一直递归下去，直到找到满足条件的结点或者确认表中没有这样的结点为止。对分查找即二分法查找，二分法查找只能适用于顺序存储的有序表。　　答案：C　　【真题11】在长度为n的线性表中，寻找最大项至少需要比较__【2】__次。（2010年9月）　　解析：本题我们分两种情况说明：一种是无序的线性表。在这种情况下，要找n个数据中值最大的数据，应该要和其他所有元素进行一次比较才能确定其值是最大的。如果有一个元素没比较，那么也不能确定当前元素是值最大的元素，因此至少需要比较的次数是n-1次。另一种是有序的线性表，在这种情况下，不管是升序还是降序线性表，其最大值的位置都是确定的，无须比较。当然本题考查的应该是第一种情况，因此答案为n-1。　　答案：n-1\n　第2天：软件工程与数据库设计　　Point1：数据模型　　考点精讲　　1、数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。　　2、数据模型分为三种：　　(1)概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。主要有：E-R模型、扩充的E-R模型、面向对象模型及谓词模型等。(2)逻辑数据模型：又称物理模型，是一种面向数据库系统的模型，该模型着重于在数据库系统一级的实现。主要有：层次模型、网状模型、关系模型、面向对象模型等。(3)物理数据模型：又称物理模型，它是一种面向计算机物理表示的模型，此模型给出　　-25-了数据模型在计算机上物理结构的表示。　　3、E-R模型　　(1)E-R模型的基本概念　　①实体：现实世界中的事物；　　②属性：事物的特性；　　③联系：现实世界中事物间的关系。　　(2)实体集的关系有一对一（一个学校和一个校长）、一对多（学生和宿舍）、多对多（老师与学生）的联系。两个实体集间联系可分为：　　①一对一联系(onetoonerelationship)简记为1:1。　　②一对多联系(onetomanyrelationship)简记为1:m或m:1。　　③多对多联系(monytomanyrelationship)简记为m:n。　　(3)E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。　　(4)E-R模型的图示法：　　①实体集表示法：在矩形内写上实体集的名字；\n　　②属性表示法：在椭圆形内写上属性的名称；　　③联系表示法：用菱形内写上联系的名称；　　④实体集与属性的联接关系：用无向线段来表示；　　⑤实体集与联系间的联接关系；E-R模型由实体、属性、联系这三个基本概念细成。只有实体、联系、属性三者结合起来才能表示一个现实世界。　　4、关系模型　　(1)在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。表中的每一列称为一个属性，相当于记录中的一个数据项，对属性的命名称为属性名，表中的一行称为一个元组，相当于记录值。　　(2)在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。　　(3)关系中的数据约束：　　①实体完整性约束：约束关系的主键中属性值不能为空值；　　②参照完全性约束：是关系之间的基本约束；　　③用户定义的完整性约束：它反映了具体应用中数据的语义要求。　　(4)关系模型的数据操作即是建立在关系上的数据操作，一般有查询、增加、删除和修改四种操作。　　真题分析　　【真题1】在E-R图中，用来表示实体联系的图形是________。（2009年9月）　　A)菱形　　B)三角形　　C)椭圆形　　D)矩形　　-26-解析：在E-R图中，用矩形表示实体集，用椭圆形表示属性，用菱形(内部写　　上联系名)表示联系。　　答案：A\n　　【真题2】在E-R图中，图形包括矩形框、菱形框、椭圆框、其中表示实体联系的是__【5】__框。（2009年3月）　　解析：在E-R图中，用菱形框来表示实体之间的联系。矩形框表示实体集，椭　　圆形框表示属性　　答案：菱形　　【真题3】将E—R图转换为关系模式时，实体和联系都可以表示为________。（2009年3月）　　A)关系　　B)域　　C)属性　　D)键　　解析：将E—R图转换为关系模式时，实体和联系都可以表示为关系。　　答案：A　　【真题4】一间宿舍可住多个学生，则实体宿舍和学生之间的联系是________。（2008年9月）　　A)多对一　　B)多对多　　C)一对一　　D)一对多　　解析：两个实体集间的联系可以有下面几种：一对一的联系、一对多或多对一　　联系、多对多。由于一个宿舍可以住多个学生，但一个学生只能住在一个宿　　舍，所以它们的联系是一对多联系。　　答案：D　　【真题5】在E-R图中，矩形表示__【5】__。（2007年9月）　　解析：矩形表示实体，椭圆形表示属性，菱形表示联系。\n　　答案：实体【真题6】在E-R图中，用来表示实体之间联系的图形是________。（2007年3月）　　A)菱形　　B)平行四边形　　C)矩形　　D)椭圆形　　解析：E—R图具有三个要素：①实体用矩形框表示，框内为实体名称。②属性用椭圆形来表示，并用线与实体连接。属性较多时也可以将实体及其属性单独列表。③实体间的联系用菱形框表示。用线将菱形框与实体相连，并在线上标注联系的类型。　　答案：A　　【真题7】在E-R图中，用来表示实体的图形是________。（2006年4月）　　A)菱形　　B)三角　　C)矩形　　D)椭圆形　　解析：在E-R图中，用三种图框分别表示实体、属性和实体之间的联系，其规定如下：用矩形框表示实体，框内标明实体名；用椭圆状框表示实体的属性，框内标明属性名；用菱形框表示实体问的联系，框内标明联系名。　　答案：C　　【真题8】在二维表中，元组的__【5】__是不能再分成更小的数据项的。（2008年9月）　　解析：元组分量的原子性是指二维表中元组的分量是不可分割的基本数据项。　　答案：分量　　【真题9】在关系数据库中，用来表示实体之间联系的是__【4】__。（2008年4月）　　解析：在关系数据库中，用关系来表示实体之间的联系。　　答案：关系\n　　【真题10】下列叙述中正确的是________。（2007年9月）　　A)一个关系的属性名表称为关系模式　　B)一个关系可以包括多个二维表　　C)为了建立一个关系，首先要构造数据的逻辑结构　　D)表示关系的二维表中各元组的每一个分量还可以分成若干个数据项　　解析：二维表中元组的分量是不可分割的基本数据项，这就是元组分量的原子性；二维表中元组的分量是不可分割的基本数据项，这就是元组分量的原子性；关系的框架称为关系模式；二维表中元组的分量是不可分割的基本数据项，这就是元组分量的原子性；关系的框架称为关系模式；　　一个满足“元组个数有限性、元组的唯一性、元组的次序无关性、元组分量的原子性、属性名唯一性、属性的次序无关性、分量值域的同一性”7个性质的二维表称为关系。　　-28-答案：C　　【真题11】一个关系表的行称为__【3】__。（2006年9月）　　解析：关系是关系数据模型的核心。关系可以用一个表来直观地表示，表的每　　一列表示关系的一个属性，每一行表示一个记录。　　答案：记录　　【真题12】在关系模型中，把数据看成是二维表，每一个二维表称为一个__【3】__。（2006年4月）　　解析：在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。　　因此，本题的正确答案是关系。　　答案：关系　　【真题13】用树形结构表示实体之间联系的模型是________。（2005年4月）　　A)层次模型　　B)三个都是　　C)关系模型　　D)网状模型\n　　解析：在数据库系统中，由于采用的数据模型不同，相应的数据库管理系统(DBMS)也不同。目前常用的数据模型有三种：层次模型、网状模型和关系模型。在层次模型中，实体之间的联系是用树结构来表示的，其中实体集(记录型)是树中的结点，而树中各结点之间的连线表示它们之间的关系。　　答案：A　　【真题14】在关系数据库中，把数据表示成二维表，每一个二维表称为__【4】__。（2005年4月）　　解析：在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。表中的每一列称为一个属性，相当于记录中的一个数据项，对属性的命名称为属性名表中的一行称为一个元组，相当于记录值。　　答案：关系　　【真题15】在数据库技术中，实体集之间的联系可以是一对一、一对多或多对多的，那么“学生”和“可选课程”的联系为__【4】__。（2009年9月）　　解析：学生与可选课程之间是多对多的关系。学生与可选课程之间是多对多的关系。一个学生可以选择多个“可选课程”，一个“可选课程”又可以有多个学生。所以为多对多的关系。　　答案：多对多　　-29-【真题16】“商品”与“顾客”两个实体集之间的联系一般是________。（2006年4月）　　A)多对一　　B)多对多　　C)一对一　　D)一对多　　解析：本题考核实体集之间的联系。实体集之间的联系有三种：一对一、一对多和多对多。因为一类商品可以由多个顾客购买，而一个顾客可以购买多类商品，所以，“商品”与“顾客”两个实体集之间的联系一般是“多对多”。　　答案：B　　【真题17】数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为__【5】__独立性。（2006年4月）\n　　解析：数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为物理独立性。　　答案：物理　　【真题18】层次型、网状型和关系型数据库划分原则是________。（2010年9月）　　A)联系的复杂程度　　B)数据之间的联系方式　　C)记录长度　　D)文件的大小　　解析：层次模型、网状模型和关系模型是目前数据库中最常用的三种数据模型，划分它们的原则是数据之间的联系方式。层次模型用树型结构来表示各实体与实体间的联系；而网状模型用网状结构来表示各实体与实体间的联系；而关系模型用表格形式表示实体类型及其实体间的联系。　　答案：B　　【真题19】一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员与实体计算机之间的联系是________。（2010年9月）　　A)多对多　　B)多对一　　C)一对一　　D)一对多　　解析：此题所列联系同“课程与学生”之间联系是一样的，即一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员与实体计算机之间具有多对多联系。　　答案：A　　Point2：软件定义阶段　　考点精讲　　1、软件定义阶段：包括制定计划与需求分析。可行性研究与计划制定：确定总目标，可行性研究，探讨解决方案，制定开发计划。\n　　2、需求分析：对待开发软件提出的需求进行分析并给出详细的定义。主要工作是编写软件需求规格说明书及用户手册。　　(1)需求分析的任务是导出目标系统的逻辑模型，解决“做什么”的问题。　　(2)需求分析一般分成4个阶段：需求获取，需求分析，编写需求规格说明书，需求评审。　　(3)软件需求规格说明书（SRS），是需求分析阶段的最后成果，是软件开发中的重要文档之一。该说明把在软件计划中确定的软件范围加以展开，制定出完整的信息描述，详细的功能说明，恰当的检验标准以及其他与要求有关的数据。其特点有：①正确性；②无岐义性；③完整性；④可验证性；⑤一致性；⑥可理解性；⑦可追踪性。　　(4)需求分析的方法：　　①结构化分析方法：包括面向数据流的结构化分析方法（SA），面向数据结构的Jackson方法（JSD）和面向数据结构的结构化数据系统开发方法（DSSD）。　　②面向对象的分析的方法（OOA）。从需求分析建立的模型的特性来分：静态分析和动态分析。　　3、结构化方法的核心和基础是结构化程序设计理论。结构化分析方法的实质：面向数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。数据字典是结构化分析的核心。　　(1)结构化分析的常用工具有：①数据流图；②数据字典；③判定树；④判定表。(2)数据流图（DFD）：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。建立数据流图的步骤：由外向里，自顶向下，逐层分解，完善求精。数据流图的主要图形元素：　　①椭圆：代表加工（转换）。输入数据经加工变换产生输出。　　②箭头：代表数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。　　③双横线：代表存储文件（数据）。表示处理过程中存入各种数据的文件。　　④矩形：代表源，潭。表示系统和环境的接口，属系统之外的实体。　　(3)数据字典：是结构化分析的核心。是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。概括地说，数据字典是对DFD中出现的被命名的图形元素的确切解释。　　(4)判定树：是从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。　　(5)判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。真题分析　　【真题1】数据流图中带有箭头的线段表示的是________。（2008年9月）\n　　A)模块调用　　B)数据流　　C)控制流　　D)事件驱动　　解析：数据流图是从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。其中,带箭头的线段表示数据流，沿箭头方向传递数据的通道，一般在旁边标注数据流名。　　答案：B　　【真题2】在软件开发中，需求分析阶段可以使用的工具是________（2008年9月）　　A)PAD图　　B)程序流程图　　C)N-S图　　D)DFD图　　解析：在软件开发中，需求分析阶段常使用的工具有数据流图(DFD)、数据字典(DD)、判断树和判断表。　　答案：D　　【真题3】在结构化分析使用的数据流图（DFD)中，利用__【5】__对其中的图形元素进行确切解释。（2007年3月）　　解析：数据字典(DataDictionary，简称DD)的作用是对DFD中出现的被命名图形元素进行确切解释。通常数据字典包含的信息有名称、别名、何处使用、如何使用、内容描述、补充信息等。　　答案：数据字典　　【真题4】数据流程图(DFD图)是________。（2010年3月）　　A)结构化方法的需求分析工具　　B)面向对象方法的需求分析工具　　C)软件概要设计的工具　　D)软件详细设计的工具\n　　解析：数据流图(DataFlowDiagram，DFD)用来描绘系统的逻辑模型，它以图形的方式描绘数据在系统中流动和处理的过程，反映系统必须完成的逻辑功能。DFD是结构化分析的工具，结构化分析是需求分析的一种方法。　　答案：APoint3：关系代数　　考点精讲　　1、关系模型的基本运算：并、差、交、广义笛卡尔积、投影、选择、连接、除。关系是有序组的集合，可将关系操作看成是集合的运算。　　2、并、差、交　　(1)并运算。R∪S。　　(2)差运算。R-S。　　(3)交运算。交运算是将两个关系中共有元组表示为R∩S。　　3、广义笛卡尔积、除　　(1)广义笛卡尔积。笛卡儿积运算：两个关系的合并操作可用笛卡儿积表示。设有n元关系R及m元关系R，它们分别有p，q个元组，则R与S的笛卡儿积为R×S，该关系是一个n+m元关系，元组个数是p×q。　　(2)除运算。将一个关系中元组去除另一个关系中元组，表示为：R/S。　　4、投影运算：投影运算是一个一元运算，一个关系通过投影运算后仍为一个关系R'。R'是这样一个关系，它是R中投影运算所指出的那些域的列所组成的关系。　　5、选择运算：选择运算是一个一元运算，关系R通过选择运算后仍为一个关系。这个关系是由R中那些满足逻辑条件的元组所组成。　　6、连接运算：　　真题分析　　【真题1】有如下三个关系R、S和T：有如下三个关系R、S和T：　　其中关系T由关系R和S通过某种操作得到，该操作为________。（2009年9月）　　A)交　　B)并\n　　C)选择　　D)投影　　解析：给定两个相同类型的关系A和B，两者的并是相同类型的一个关系，关系的主体由出现在A中或B中或同时出现在两者之中的所有元组组成。　　答案：B　　【真题2】有两个关系R，S如下：有两个关系R，S如下：　　由关系R通过运算得到关系S，则所使用的运算为________。（2009年3月）　　A)插入　　B)连接　　C)选择　　D)投影　　解析：一个关系R通过投影运算后仍为一个关系R'，R'是由R中投影运算所指出的那些域的列所组成的关系。所以题目中关系s是由关系R经过投影运算所得。(选择运算主要是对关系R中选择由满足逻辑条件的元组所组成的一个新关系)　　答案：D　　【真题3】有三个关系R、S和T如下：有三个关系R、S和T如下：　　由关系R和S通过运算得到关系T，则所使用的运算为________。（2008年9月）　　A)并　　B)自然连接　　C)笛卡尔积　　D)交　　解析：在实际应用中，最常用的连接是自然连接的特例。它满足下面的条件：两关系间有公共字段；通过公共字段的相等值进行连接。通过观察二个关系R、S、T的结果可知，关系T是由关系R和S进行自然连接得到的。　　答案：B\n　　【真题4】在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是________。（2007年3月）　　A)投影　　B)笛卡儿乘积　　C)并　　D)交　　解析：关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组所组成，记为R∩S形式，定义如下：R∩S={t∈R∧t∈S}=R-(R-S)。所以不改变关系表中的属性个数，但能减少元组个数的是关系之间的交操作。　　答案：D【真题5】设有如下三个关系表设有如下三个关系表，下列操作中正确的是________。（2006年9月）　　A)T=R×S　　B)T=R／S　　C)T=R∪S　　D)T=R∩S　　解析：本题考查数据库的关系代数运算。R表中只有一个域名A，有两个记录(也叫元组)，分别是m和n；s表中有两个域名，分别是B和C，其所对应的记录分别为1和3。注意观察表T，它是由R的第一个记录依次与s的所有记录组合，然后再由R的第二个记录与s的所有记录组合，形成的一个新表。上述运算恰恰符合关系代数的笛卡尔积运算规则。关系代数中，笛卡尔积运算用“×”来表示。因此，上述运算可以表示为T=R×S。　　答案：A　　【真题6】设有如下关系表:设有如下关系表:　　（2005年9月）　　A)T＝R×S　　B)T＝R／S　　C)T＝R∩S　　D)T＝R∪S\n　　解析：“∩、∪、×”分别进行交运算、并运算、笛卡尔积运算，“／”是除关系运算。T由属于关系R以及关系S的元组组成，简单来说，就是S和R的元组之和，是并运算。　　答案：D　　【真题7】有两个关系R和T如下：则由关系R得到关系T的操作是________。（2010年3月）　　A)交　　B)并　　C)选择　　D)投影　　解析：选择是由R中那些满足逻辑条件的元组所组成。　　答案：C　　【真题8】有三个关系R、S和T如下有三个关系R、S和T如下　　由关系R和S通过运算得到关系T，则所使用的运算为________。（2008年4月）　　A)笛卡儿积　　B)交　　C)并　　D)自然连接　　解析：关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组组成的，记为R∩S。　　答案：B　　【真题9】有三个关系R、S和T如下：　　则由关系R和S得到关系T的操作是________。（2010年9月）　　A)投影　　B)并　　C)自然连接　　D)交\n　　解析：由“自然连接”运算的定义可知，此题中关系R和S通过自然连接运算得到关系T。　　答案：CPoint4：软件设计阶段　　考点精讲　　1、软件设计是软件工程的重要阶段，是一个把软件需求持换为软件表示的过程。软件设计的基本目标是用比较抽象慨括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。　　(1)需求分析主要解决“做什么”问题，软件设计解决“怎么做”的问题。　　从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。　　①结构设计：定义软件系统各主要部件之间的关系。　　②数据设计：将分析时创建的模型转化为数据结构的定义。　　③接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。　　④过程设计：把系统结构部件转换成软件的过程描述。　　(2)从工程管理角度来看，软件设计包括：概要设计和详细设计。　　2、软件设计中应该遵循的基本原理和与软件设计有关的概念　　(1)抽象：就是把事物本质的共同特征提取出来而不考虑其他细节。　　(2)模块化：是指把一个待开发的软件分解成若干小的简单的部分。但划分模块不是越多越好。　　(3)信息隐蔽：是指在一个模块中包含的信息，对于不需求这些信息的其他模块来说是不能访问的。　　(4)模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。这是评价设计好坏的重要度量标准。　　3、衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准：　　(1)内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。　　(2)耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性的强弱取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚、低耦合。　　4、软件概要设计\n　　(1)概要设计的基本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设计文档；概要设计文档评审。　　(2)结构图（SC），是概要设计阶段的工具。其图形元素为：　　①矩形表示一般模块。　　②箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。　　③用带实心圆的箭头表示传递的是控制信息。　　④空心圆箭心表示传递的是数据。　　结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。　　结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。　　结构图的形态特征：包括深度、宽度、扇出、扇入。　　①深度：表示控制的层数　　②宽度：表示整体控制跨度　　③扇入：调用一个给定模块的模块个数。　　④扇出：一个模块直接调用的其他模块数。　　(3)面向数据流的设计方法：　　典型的数据流类型有两种：变换型和事务型。　　变换型系统结构图由输入、中心变换、输出三部分组成。　　事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。　　5、软件详细设计　　(1)是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。　　(2)常见的过程设计工具有：　　①图形工具：程序流程图（PDF），N-S，PAD（问题分析图），HIPO　　②表格工具：判定表\n　　③语言工具：PDL（伪码）　　真题分析　　【真题1】软件详细设计产生图如下：软件详细设计产生图如下：　　该图是________。（2009年9月）　　A)程序流程图　　B)E-R图　　-38-C)N-S图　　D)PAD图　　解析：程序流程图是一种传统的、应用，广泛的软件过程设计表示工具，通常也称为程序框图。　　答案：A　　【真题2】程序流程图中带有箭头的线段表示的是________。（2008年4月）　　A)控制流　　B)调用关系　　C)图元关系　　D)数据流　　解析：程序流程图是一种传统的、应用广泛的软件过程设计工具，通常也称为程序框图。其中，用带箭头的线段表示控制流，用矩形表示加工步骤，用菱形表示逻辑条件。　　答案：A　　【真题3】在软件开发中，需求分析阶段产生的主要文档是________。（2008年4月）　　A)概要设计说明书　　B)集成测试计划　　C)可行性分析报告　　D)软件需求规格说明书　　解析：需求分析的最终结果是生成软件需要规格说明书，可以为用户、分析人员和设计人员之间的交流提供方便，可以直接支持目标的确认，又可以作为控制软件开发进程的依据。\n　　答案：D　　【真题4】软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是__【1】__。（2007年9月）　　解析：软件需求规格说明书是确保软件质量的有力措施，是需求分析阶段的最终成果。其质量好坏的标准、标准的优先级及标准的内涵是：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等。其中最重要的特性是无歧义性，即需要规格说明书应该是精确的、无二义的，需求说明书越精确，以后出现错误、混淆、反复的可能性越小。　　答案：无歧义性　　【真题5】下列选项中不属于软件生命周期开发阶段任务的是________。（2006年9月）　　A)软件维护　　B)详细设计　　C)软件测试　　D)概要设计　　解析：软件生命周期由软件定义、软件开发和软件维护三个时期组成，每个时期又进一步划分为若干个阶段。软件定义时期的基本任务是确定软件系统的工程需求。软件定义可分为软件系统的可行性研究和需求分析两个阶段。　　1、软件开发时期是具体设计和实现在前一时期定义的软件，它通常由下面五个阶段组成：概要设计、详细设计、编写代码、组装测试和确认测试。　　2、软件维护时期的主要任务是使软件持久地满足用户的需要。即当软件在使用过程中发现错误时应加以改正；当环境改变时应该修改软件，以适应新的环境；当用户有新要求时应该及时改进软件，以满足用户的新要求。　　根据上述对软件生命周期的介绍，可知软件维护不是软件生命周期开发阶段的任务。　　答案：A【真题6】软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于________。（2010年3月）　　A)维护阶段　　B)上述三个阶段　　C)定义阶段　　D)开发阶段\n　　解析：详细设计属于软件生命周期中开发阶段的第一步骤，即设计。　　答案：D　　【真题7】软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中__【3】__阶段产生“软件需求规格说明书”。（2009年9月）　　解析：软件开发过程为：需求确认-->概要设计-->详细设计-->编码-->单元测试-->集成测试-->系统测试-->维护。其中，需求分析阶段产生需求规格说明书；概要设计阶段产生系统用例图和用例场景；详细设计阶段产生系统设计报告和数据库设计报告；测试阶段产生测试用例报告。　　答案：需求分析　　【真题8】从工程管理角度，软件设计一般分为两步完成，它们是________。（2006年9月）　　A)软件结构设计与数据设计　　B)过程设计与数据设计　　C)概要设计与详细设计　　D)数据设计与接口设计　　解析：从工程管理的角度，软件设计可分为概要设计和详细设计两大步骤。　　1、概要设计是根据需求确定软件和数据的总体框架；　　2、详细设计是将其进一步细化成软件的算法、数据结构和接口。　　而在技术上，概要设计和详细设计又由若干活动组成，包括总体结构设计、数据设计和过程设计。　　答案：C　　【真题9】在软件设计中，不属于过程设计工具的是________。（2005年9月）　　A)N-S图　　B)DFD图　　C)PDL(过程设计语言)　　D)PAD图　　解析：数据流图DFD，是结构化分析方法最主要的一种图形工具，不属于过程　　设计工具。\n　　答案：B　　【真题10】下列软件系统结构图的宽度为__【1】__。（2006年9月）　　解析：题目中的图形是倒置的树状结构，这是用层次图表示的软件结构。结构图中同一层次模块的最大模块个数称为结构的宽度，它表示控制的总分布。根据上述结构图宽度的定义，从图中可以看出，第二层的模块个数最多，即为3。因此，这个系统结构图的宽度就为3。　　答案：3　　【真题11】软件设计中划分模块的一个准则是________。（2009年9月）　　A)低内聚高耦合　　B)高内聚高耦合　　C)低内聚低耦合　　D)高内聚低耦合　　解析：模块的划分应遵循一定的要求，以保证模块划分合理，并进一步保证以此为依据开发出的软件系统可靠性强，易于理解和维护。模块之间的耦合应尽可能的低，模块的内聚度应尽可能的高。　　答案：D　　【真题12】耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是________。（2009年3月）　　A)耦合性是指一个模块内部各个元素间彼此结合的紧密程度　　B)内聚性是指模块间互相连接的紧密程度　　C)提高耦合性、降低内聚性有利于提高模块的独立性　　D)降低耦合性、提高内聚性有利于提高模块的独立性　　解析：耦合性是反映模块间互相连接的紧密程度，内聚性是指一个模块内部各个元素间彼此接合的紧密程度。提高模块的内聚性，降低模块的耦合性有利于提高模块的独立性。　　答案：D　　【真题13】软件设计中模块划分应遵循的准则是________。（2008年4月）　　A)低内聚高耦合　　B)高内聚高耦合\n　　C)低内聚低耦合　　D)高内聚低耦合　　解析：耦合性和内聚性是模块独立性的两个定性标准，各模块的内聚性越强，则耦合性越弱。软件设计应该遵循高内聚低耦合。　　答案：D　　【真题14】在结构化程序设计中，模块划分的原则是________。（2007年3月）　　A)各模块之间的联系应尽量紧密　　B)模块内具有高内聚度、模块间具有低耦合度　　C)各模块应包括尽量多的功能　　D)各模块的规模应尽量大　　解析：内聚性是对一个模块内部各个元素间彼此结合的紧密程度的度量。耦合性是对模块间互相连接的紧密程度的度量。在结构化程序设计中，模块划分应遵循高内聚、低耦合的原则，即减弱模块之间的耦合性和提高模块内聚性，有利于提高软件模块的独立性。　　答案：B　　【真题15】为了使模块尽可能独立，要求________。（2005年4月）　　A)模块的内聚程度要尽量低，且各模块间的紧密程度要尽量弱　　B)模块的内聚程度要尽量低，且各模块间的紧密程度要尽量强　　C)模块的内聚程度要尽量高，且各模块间的紧密程度要尽量强　　D)模块的内聚程度要尽量高，且各模块间的紧密程度要尽量弱　　解析：系统设计的质量主要反映在模块的独立性上。系统设计的质量主要反映在模块的独立性上。　　1、评价模块独立性的主要标准有两个：　　一是模块之间的耦合，它表明两个模块之间互相独立的程度；　　二是模块内部之间的关系是否紧密，称为内聚。　　2、一般来说，要求模块之问的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。　　答案：D\n　　【真题16】两个或两个以上模块之间关联的紧密程度称为________。（2006年4月）　　A)复杂度　　B)数据传输特性　　C)耦合度　　D)内聚度　　解析：本题考核模块独立性的评价。评价模块独立性的主要标准有两个：一是模块之间的耦合，它表明两个模块之间互相独立的程度，也可以说是两个或两个以上模块之间关联的紧密程度；二是模块内各部分之间的关系是否紧密，称为内聚。一般来说，要求模块内各部分之间的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。　　答案：C　Point2：软件定义阶段　　考点精讲　　1、软件定义阶段：包括制定计划与需求分析。可行性研究与计划制定：确定总目标，可行性研究，探讨解决方案，制定开发计划。　　2、需求分析：对待开发软件提出的需求进行分析并给出详细的定义。主要工作是编写软件需求规格说明书及用户手册。　　(1)需求分析的任务是导出目标系统的逻辑模型，解决“做什么”的问题。　　(2)需求分析一般分成4个阶段：需求获取，需求分析，编写需求规格说明书，需求评审。　　(3)软件需求规格说明书（SRS），是需求分析阶段的最后成果，是软件开发中的重要文档之一。该说明把在软件计划中确定的软件范围加以展开，制定出完整的信息描述，详细的功能说明，恰当的检验标准以及其他与要求有关的数据。其特点有：①正确性；②无岐义性；③完整性；④可验证性；⑤一致性；⑥可理解性；⑦可追踪性。　　(4)需求分析的方法：　　①结构化分析方法：包括面向数据流的结构化分析方法（SA），面向数据结构的Jackson方法（JSD）和面向数据结构的结构化数据系统开发方法（DSSD）。　　②面向对象的分析的方法（OOA）。从需求分析建立的模型的特性来分：静态分析和动态分析。　　3、结构化方法的核心和基础是结构化程序设计理论。结构化分析方法的实质：面向数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。数据字典是结构化分析的核心。\n　　(1)结构化分析的常用工具有：①数据流图；②数据字典；③判定树；④判定表。(2)数据流图（DFD）：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。建立数据流图的步骤：由外向里，自顶向下，逐层分解，完善求精。数据流图的主要图形元素：　　①椭圆：代表加工（转换）。输入数据经加工变换产生输出。　　②箭头：代表数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。　　③双横线：代表存储文件（数据）。表示处理过程中存入各种数据的文件。　　④矩形：代表源，潭。表示系统和环境的接口，属系统之外的实体。　　(3)数据字典：是结构化分析的核心。是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。概括地说，数据字典是对DFD中出现的被命名的图形元素的确切解释。　　(4)判定树：是从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。　　(5)判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。真题分析　　【真题1】数据流图中带有箭头的线段表示的是________。（2008年9月）　　A)模块调用　　B)数据流　　C)控制流　　D)事件驱动　　解析：数据流图是从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。其中,带箭头的线段表示数据流，沿箭头方向传递数据的通道，一般在旁边标注数据流名。　　答案：B　　【真题2】在软件开发中，需求分析阶段可以使用的工具是________（2008年9月）　　A)PAD图　　B)程序流程图　　C)N-S图　　D)DFD图\n　　解析：在软件开发中，需求分析阶段常使用的工具有数据流图(DFD)、数据字典(DD)、判断树和判断表。　　答案：D　　【真题3】在结构化分析使用的数据流图（DFD)中，利用__【5】__对其中的图形元素进行确切解释。（2007年3月）　　解析：数据字典(DataDictionary，简称DD)的作用是对DFD中出现的被命名图形元素进行确切解释。通常数据字典包含的信息有名称、别名、何处使用、如何使用、内容描述、补充信息等。　　答案：数据字典　　【真题4】数据流程图(DFD图)是________。（2010年3月）　　A)结构化方法的需求分析工具　　B)面向对象方法的需求分析工具　　C)软件概要设计的工具　　D)软件详细设计的工具　　解析：数据流图(DataFlowDiagram，DFD)用来描绘系统的逻辑模型，它以图形的方式描绘数据在系统中流动和处理的过程，反映系统必须完成的逻辑功能。DFD是结构化分析的工具，结构化分析是需求分析的一种方法。　　答案：APoint3：关系代数　　考点精讲　　1、关系模型的基本运算：并、差、交、广义笛卡尔积、投影、选择、连接、除。关系是有序组的集合，可将关系操作看成是集合的运算。　　2、并、差、交　　(1)并运算。R∪S。　　(2)差运算。R-S。　　(3)交运算。交运算是将两个关系中共有元组表示为R∩S。　　3、广义笛卡尔积、除\n　　(1)广义笛卡尔积。笛卡儿积运算：两个关系的合并操作可用笛卡儿积表示。设有n元关系R及m元关系R，它们分别有p，q个元组，则R与S的笛卡儿积为R×S，该关系是一个n+m元关系，元组个数是p×q。　　(2)除运算。将一个关系中元组去除另一个关系中元组，表示为：R/S。　　4、投影运算：投影运算是一个一元运算，一个关系通过投影运算后仍为一个关系R'。R'是这样一个关系，它是R中投影运算所指出的那些域的列所组成的关系。　　5、选择运算：选择运算是一个一元运算，关系R通过选择运算后仍为一个关系。这个关系是由R中那些满足逻辑条件的元组所组成。　　6、连接运算：　　真题分析　　【真题1】有如下三个关系R、S和T：有如下三个关系R、S和T：　　其中关系T由关系R和S通过某种操作得到，该操作为________。（2009年9月）　　A)交　　B)并　　C)选择　　D)投影　　解析：给定两个相同类型的关系A和B，两者的并是相同类型的一个关系，关系的主体由出现在A中或B中或同时出现在两者之中的所有元组组成。　　答案：B　　【真题2】有两个关系R，S如下：有两个关系R，S如下：　　由关系R通过运算得到关系S，则所使用的运算为________。（2009年3月）　　A)插入　　B)连接　　C)选择　　D)投影\n　　解析：一个关系R通过投影运算后仍为一个关系R'，R'是由R中投影运算所指出的那些域的列所组成的关系。所以题目中关系s是由关系R经过投影运算所得。(选择运算主要是对关系R中选择由满足逻辑条件的元组所组成的一个新关系)　　答案：D　　【真题3】有三个关系R、S和T如下：有三个关系R、S和T如下：　　由关系R和S通过运算得到关系T，则所使用的运算为________。（2008年9月）　　A)并　　B)自然连接　　C)笛卡尔积　　D)交　　解析：在实际应用中，最常用的连接是自然连接的特例。它满足下面的条件：两关系间有公共字段；通过公共字段的相等值进行连接。通过观察二个关系R、S、T的结果可知，关系T是由关系R和S进行自然连接得到的。　　答案：B　　【真题4】在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是________。（2007年3月）　　A)投影　　B)笛卡儿乘积　　C)并　　D)交　　解析：关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组所组成，记为R∩S形式，定义如下：R∩S={t∈R∧t∈S}=R-(R-S)。所以不改变关系表中的属性个数，但能减少元组个数的是关系之间的交操作。　　答案：D【真题5】设有如下三个关系表设有如下三个关系表，下列操作中正确的是________。（2006年9月）　　A)T=R×S　　B)T=R／S\n　　C)T=R∪S　　D)T=R∩S　　解析：本题考查数据库的关系代数运算。R表中只有一个域名A，有两个记录(也叫元组)，分别是m和n；s表中有两个域名，分别是B和C，其所对应的记录分别为1和3。注意观察表T，它是由R的第一个记录依次与s的所有记录组合，然后再由R的第二个记录与s的所有记录组合，形成的一个新表。上述运算恰恰符合关系代数的笛卡尔积运算规则。关系代数中，笛卡尔积运算用“×”来表示。因此，上述运算可以表示为T=R×S。　　答案：A　　【真题6】设有如下关系表:设有如下关系表:　　（2005年9月）　　A)T＝R×S　　B)T＝R／S　　C)T＝R∩S　　D)T＝R∪S　　解析：“∩、∪、×”分别进行交运算、并运算、笛卡尔积运算，“／”是除关系运算。T由属于关系R以及关系S的元组组成，简单来说，就是S和R的元组之和，是并运算。　　答案：D　　【真题7】有两个关系R和T如下：则由关系R得到关系T的操作是________。（2010年3月）　　A)交　　B)并　　C)选择　　D)投影　　解析：选择是由R中那些满足逻辑条件的元组所组成。　　答案：C　　【真题8】有三个关系R、S和T如下有三个关系R、S和T如下　　由关系R和S通过运算得到关系T，则所使用的运算为________。（2008年4月）\n　　A)笛卡儿积　　B)交　　C)并　　D)自然连接　　解析：关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组组成的，记为R∩S。　　答案：B　　【真题9】有三个关系R、S和T如下：　　则由关系R和S得到关系T的操作是________。（2010年9月）　　A)投影　　B)并　　C)自然连接　　D)交　　解析：由“自然连接”运算的定义可知，此题中关系R和S通过自然连接运算得到关系T。　　答案：CPoint4：软件设计阶段　　考点精讲　　1、软件设计是软件工程的重要阶段，是一个把软件需求持换为软件表示的过程。软件设计的基本目标是用比较抽象慨括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。　　(1)需求分析主要解决“做什么”问题，软件设计解决“怎么做”的问题。　　从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。　　①结构设计：定义软件系统各主要部件之间的关系。　　②数据设计：将分析时创建的模型转化为数据结构的定义。　　③接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。　　④过程设计：把系统结构部件转换成软件的过程描述。\n　　(2)从工程管理角度来看，软件设计包括：概要设计和详细设计。　　2、软件设计中应该遵循的基本原理和与软件设计有关的概念　　(1)抽象：就是把事物本质的共同特征提取出来而不考虑其他细节。　　(2)模块化：是指把一个待开发的软件分解成若干小的简单的部分。但划分模块不是越多越好。　　(3)信息隐蔽：是指在一个模块中包含的信息，对于不需求这些信息的其他模块来说是不能访问的。　　(4)模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。这是评价设计好坏的重要度量标准。　　3、衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准：　　(1)内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。　　(2)耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性的强弱取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚、低耦合。　　4、软件概要设计　　(1)概要设计的基本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设计文档；概要设计文档评审。　　(2)结构图（SC），是概要设计阶段的工具。其图形元素为：　　①矩形表示一般模块。　　②箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。　　③用带实心圆的箭头表示传递的是控制信息。　　④空心圆箭心表示传递的是数据。　　结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。　　结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。　　结构图的形态特征：包括深度、宽度、扇出、扇入。　　①深度：表示控制的层数\n　　②宽度：表示整体控制跨度　　③扇入：调用一个给定模块的模块个数。　　④扇出：一个模块直接调用的其他模块数。　　(3)面向数据流的设计方法：　　典型的数据流类型有两种：变换型和事务型。　　变换型系统结构图由输入、中心变换、输出三部分组成。　　事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。　　5、软件详细设计　　(1)是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。　　(2)常见的过程设计工具有：　　①图形工具：程序流程图（PDF），N-S，PAD（问题分析图），HIPO　　②表格工具：判定表　　③语言工具：PDL（伪码）　　真题分析　　【真题1】软件详细设计产生图如下：软件详细设计产生图如下：　　该图是________。（2009年9月）　　A)程序流程图　　B)E-R图　　-38-C)N-S图　　D)PAD图　　解析：程序流程图是一种传统的、应用，广泛的软件过程设计表示工具，通常也称为程序框图。　　答案：A　　【真题2】程序流程图中带有箭头的线段表示的是________。（2008年4月）\n　　A)控制流　　B)调用关系　　C)图元关系　　D)数据流　　解析：程序流程图是一种传统的、应用广泛的软件过程设计工具，通常也称为程序框图。其中，用带箭头的线段表示控制流，用矩形表示加工步骤，用菱形表示逻辑条件。　　答案：A　　【真题3】在软件开发中，需求分析阶段产生的主要文档是________。（2008年4月）　　A)概要设计说明书　　B)集成测试计划　　C)可行性分析报告　　D)软件需求规格说明书　　解析：需求分析的最终结果是生成软件需要规格说明书，可以为用户、分析人员和设计人员之间的交流提供方便，可以直接支持目标的确认，又可以作为控制软件开发进程的依据。　　答案：D　　【真题4】软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是__【1】__。（2007年9月）　　解析：软件需求规格说明书是确保软件质量的有力措施，是需求分析阶段的最终成果。其质量好坏的标准、标准的优先级及标准的内涵是：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等。其中最重要的特性是无歧义性，即需要规格说明书应该是精确的、无二义的，需求说明书越精确，以后出现错误、混淆、反复的可能性越小。　　答案：无歧义性　　【真题5】下列选项中不属于软件生命周期开发阶段任务的是________。（2006年9月）　　A)软件维护　　B)详细设计　　C)软件测试\n　　D)概要设计　　解析：软件生命周期由软件定义、软件开发和软件维护三个时期组成，每个时期又进一步划分为若干个阶段。软件定义时期的基本任务是确定软件系统的工程需求。软件定义可分为软件系统的可行性研究和需求分析两个阶段。　　1、软件开发时期是具体设计和实现在前一时期定义的软件，它通常由下面五个阶段组成：概要设计、详细设计、编写代码、组装测试和确认测试。　　2、软件维护时期的主要任务是使软件持久地满足用户的需要。即当软件在使用过程中发现错误时应加以改正；当环境改变时应该修改软件，以适应新的环境；当用户有新要求时应该及时改进软件，以满足用户的新要求。　　根据上述对软件生命周期的介绍，可知软件维护不是软件生命周期开发阶段的任务。　　答案：A【真题6】软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于________。（2010年3月）　　A)维护阶段　　B)上述三个阶段　　C)定义阶段　　D)开发阶段　　解析：详细设计属于软件生命周期中开发阶段的第一步骤，即设计。　　答案：D　　【真题7】软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中__【3】__阶段产生“软件需求规格说明书”。（2009年9月）　　解析：软件开发过程为：需求确认-->概要设计-->详细设计-->编码-->单元测试-->集成测试-->系统测试-->维护。其中，需求分析阶段产生需求规格说明书；概要设计阶段产生系统用例图和用例场景；详细设计阶段产生系统设计报告和数据库设计报告；测试阶段产生测试用例报告。　　答案：需求分析　　【真题8】从工程管理角度，软件设计一般分为两步完成，它们是________。（2006年9月）　　A)软件结构设计与数据设计　　B)过程设计与数据设计\n　　C)概要设计与详细设计　　D)数据设计与接口设计　　解析：从工程管理的角度，软件设计可分为概要设计和详细设计两大步骤。　　1、概要设计是根据需求确定软件和数据的总体框架；　　2、详细设计是将其进一步细化成软件的算法、数据结构和接口。　　而在技术上，概要设计和详细设计又由若干活动组成，包括总体结构设计、数据设计和过程设计。　　答案：C　　【真题9】在软件设计中，不属于过程设计工具的是________。（2005年9月）　　A)N-S图　　B)DFD图　　C)PDL(过程设计语言)　　D)PAD图　　解析：数据流图DFD，是结构化分析方法最主要的一种图形工具，不属于过程　　设计工具。　　答案：B　　【真题10】下列软件系统结构图的宽度为__【1】__。（2006年9月）　　解析：题目中的图形是倒置的树状结构，这是用层次图表示的软件结构。结构图中同一层次模块的最大模块个数称为结构的宽度，它表示控制的总分布。根据上述结构图宽度的定义，从图中可以看出，第二层的模块个数最多，即为3。因此，这个系统结构图的宽度就为3。　　答案：3　　【真题11】软件设计中划分模块的一个准则是________。（2009年9月）　　A)低内聚高耦合　　B)高内聚高耦合　　C)低内聚低耦合　　D)高内聚低耦合\n　　解析：模块的划分应遵循一定的要求，以保证模块划分合理，并进一步保证以此为依据开发出的软件系统可靠性强，易于理解和维护。模块之间的耦合应尽可能的低，模块的内聚度应尽可能的高。　　答案：D　　【真题12】耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是________。（2009年3月）　　A)耦合性是指一个模块内部各个元素间彼此结合的紧密程度　　B)内聚性是指模块间互相连接的紧密程度　　C)提高耦合性、降低内聚性有利于提高模块的独立性　　D)降低耦合性、提高内聚性有利于提高模块的独立性　　解析：耦合性是反映模块间互相连接的紧密程度，内聚性是指一个模块内部各个元素间彼此接合的紧密程度。提高模块的内聚性，降低模块的耦合性有利于提高模块的独立性。　　答案：D　　【真题13】软件设计中模块划分应遵循的准则是________。（2008年4月）　　A)低内聚高耦合　　B)高内聚高耦合　　C)低内聚低耦合　　D)高内聚低耦合　　解析：耦合性和内聚性是模块独立性的两个定性标准，各模块的内聚性越强，则耦合性越弱。软件设计应该遵循高内聚低耦合。　　答案：D　　【真题14】在结构化程序设计中，模块划分的原则是________。（2007年3月）　　A)各模块之间的联系应尽量紧密　　B)模块内具有高内聚度、模块间具有低耦合度　　C)各模块应包括尽量多的功能　　D)各模块的规模应尽量大\n　　解析：内聚性是对一个模块内部各个元素间彼此结合的紧密程度的度量。耦合性是对模块间互相连接的紧密程度的度量。在结构化程序设计中，模块划分应遵循高内聚、低耦合的原则，即减弱模块之间的耦合性和提高模块内聚性，有利于提高软件模块的独立性。　　答案：B　　【真题15】为了使模块尽可能独立，要求________。（2005年4月）　　A)模块的内聚程度要尽量低，且各模块间的紧密程度要尽量弱　　B)模块的内聚程度要尽量低，且各模块间的紧密程度要尽量强　　C)模块的内聚程度要尽量高，且各模块间的紧密程度要尽量强　　D)模块的内聚程度要尽量高，且各模块间的紧密程度要尽量弱　　解析：系统设计的质量主要反映在模块的独立性上。系统设计的质量主要反映在模块的独立性上。　　1、评价模块独立性的主要标准有两个：　　一是模块之间的耦合，它表明两个模块之间互相独立的程度；　　二是模块内部之间的关系是否紧密，称为内聚。　　2、一般来说，要求模块之问的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。　　答案：D　　【真题16】两个或两个以上模块之间关联的紧密程度称为________。（2006年4月）　　A)复杂度　　B)数据传输特性　　C)耦合度　　D)内聚度　　解析：本题考核模块独立性的评价。评价模块独立性的主要标准有两个：一是模块之间的耦合，它表明两个模块之间互相独立的程度，也可以说是两个或两个以上模块之间关联的紧密程度；二是模块内各部分之间的关系是否紧密，称为内聚。一般来说，要求模块内各部分之间的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。　　答案：C\n　Point5：数据库设计与管理　　考点精讲　　1、数据库设计是数据应用的核心。　　数据库设计的两种方法：　　(1)面向数据：以信息需求为主，兼顾处理需求；　　(2)面向过程：以处理需求为主，兼顾信息需求。　　2、数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。　　3、数据库设计包括：需求分析、概念设计、逻辑设计、物理设计。　　(1)需求分析：常用结构分析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。　　对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。　　数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。　　(2)数据库概念设计的目的是分析数据间内在语义关联，并建立数据的抽象模型。设计的方法有两种：　　①集中式模式设计法（适用于小型或并不复杂的单位或部门）；　　②视图集成设计法。　　常见的方法有：E-R模型与视图集成。视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。　　视图集成的实质是将所有的局部视图统一与合并成一个完整的数据模式，常见的几种局部设计的冲突：命名冲突、概念冲突、域冲突、约束冲突。　　(3)数据库的逻辑设计主要工作是将E-R图转换成RDBMS中的关系模式。　　逻辑设计的另一个重要内容是关系视图的设计，又称为外模式设计。关系视图设计：关系视图的设计又称外模式设计。　　关系视图的主要作用：　　①提供数据逻辑独立性：使应用程序不爱逻辑模式变化的影响。\n　　②能适应用户对数据的不同需求；　　③有一定数据保密功能。　　(4)数据库的物理设计主要目标是对数据内部物理结构做调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。　　4、数据库管理的内容：　　(1)数据库的建立；　　(2)数据库的调整；　　(3)数据库的重组；　　(4)数据库安全性与完整性控制；　　(5)数据库的故障恢复；　　(6)数据库监控。　　真题分析　　【真题1】数据库应用系统中的核心问题是________。（2009年3月）　　A)数据库维护　　B)数据库管理员培训　　C)数据库设计　　D)数据库系统设计　　解析：在数据库应用系统中的一个核心问题就是设计一个能满足用户要求，性能良好的数据库，这就是数据库设计。所以数据库设计是数据库应用的核心。　　答案：C　　【真题2】数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和________。（2006年9月）　　A)运行阶段　　B)物理设计　　C)编码设计\n　　D)测试阶段　　解析：数据库的生命周期可以分为两个阶段：一是数据库设计阶段；二是数据库实现阶段。数据库的设计阶段又分为如下四个子阶段：即需求分析、概念设计、逻辑设计和物理设计。　　答案：B　　【真题3】在数据库系统中，用户所见的数据模式为________。（2006年9月）　　A)内模式　　B)物理模式　　C)概念模式　　D)外模式　　解析：数据库管理系统的三级模式结构由外模式、模式和内模式组成。数据库管理系统的三级模式结构由外模式、模式和内模式组成。　　1、外模式也称子模式或用户模式，是指数据库用户所看到的数据结构，是用户看到的数据视图。　　2、模式也称逻辑模式，是数据库中对全体数据的逻辑结构和特性的描述，是所有用户所见到的数据视图的总和。　　3、内模式也称存储模式或物理模式，是指数据在数据库系统内的存储介质上的表示，即对数据的物理结构和存取方法的描述。　　答案：D　　【真题4】数据库设计包括概念设计、__【4】__设计和物理设计。（2008年9月）　　解析：数据库设计目前一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的若干阶段。它们是需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进一步修改阶段。在数据库设计中采用前4个阶段。　　答案：逻辑　　【真题5】在数据库设计中，将E-R图转换成关系数据模型的过程属于________。（2008年4月）　　A)逻辑设计阶段　　B)物理设计阶段　　C)需求分析阶段\n　　D)概念设计阶段　　解析：数据库的设计阶段包括需要分析、概念设计、逻辑设计和物理设计，其中将E-R图转换成关系数据模型的过程属于逻辑设计阶段。　　答案：A　　【真题6】数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的________。（2010年3月）　　A)概念设计阶段　　B)物理设计阶段　　C)需求分析阶段　　D)逻辑设计阶段　　解析：E-R图是概念模式，在第二阶段概念设计阶段构造。　　答案：A　　【真题7】数据库设计的四个阶段是：需求分析，概念设计，逻辑设计和__【5】__。（2010年9月）　　解析：数据库的设计包括需求分析、概念设计、逻辑设计和物理设计四个阶段。　　答案：物理设计　Point6：软件测试　　考点精讲　　1、软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。　　2、软件测试的目的：软件测试是为了发现错误而执行程序的过程。　　3、软件测试的准则：①所有测试都应追溯到需求；②严格执行测试计划，排除测试的随意性；③充分注意测试中的群集现象；④程序员应避免检查自己的程序；⑤穷举测试不可能。　　4、软件测试的方法和技术分类：从是否需要执行被测试软件的角度，分为静态测试和动态测试方法；按照功能划分，分为白盒测试和黑盒测试方法。\n　　5、静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行；动态测试是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。6、白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本路径测试。黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据率访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。　　7、软件测试过程一般按四个步骤进行：单元测试、集成测试、验收测试(确认测试)和系统测试。　　(1)单元测试：是对软件设计的最小单位（模块）进行正确性检验的测试，目的是发现各模块内部可能存在的各种错误。依据是详细设计说明书和源程序。采用的技术有表静态分析和动态测试。对动态测试以白盒测试为主，辅助以黑盒测试。　　单元测试的内容包括：模块接口测试，局部数据结构测试，重要的执行路径的检查，出错处理测试，影响以上各点及其相关点的边界条件测试。　　单元测试需要辅助模块：驱动模块和桩模块。驱动模块相当于被测试模块的主程序，桩模块是主程序调用的其他模块。　　(2)集成测试：是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误，依据是概要设计说明书。集成测试所涉及的内容包括：软件单元的接口测试，全局数据结构测试，边界条件和非法输入的测试。　　集成测试将模块组装成程序通常采用：非增量方式和增量方式组装。增量方式包括自顶向下，自底向上，自顶向下和自向上相结合。　　(3)确认测试的任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求，主要依据的是软件需求规格说明书。确认测试主要运用黑盒测试法。(4)系统测试的目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。系统测试的具体实施一般包括：功能测试，性能测试，操作测试，配置测试，外部接口测试，安全测试等。　　真题分析　　【真题1】软件测试可分为白盒测试和黑盒测试。基本路径测试属于__【2】__测试。（2009年3月）　　解析：软件测试按照功能可以分为白盒测试和黑盒测试，白盒测试方法也称为结构测试或逻辑驱动测试，其主要方法有逻辑覆盖、基本路径测试等。　　答案：白盒　　【真题2】下面叙述中错误的是________。（2009年3月）　　A)程序调试通常也称为Debug　　B)软件测试应严格执行测试计划，排除测试的随意性　　C)软件测试的目的是发现错误并改正错误　　D)对被调试的程序进行“错误定位”是程序调试的必要步骤\n　　解析：软件测试是为了发现错误而执行程序的过程。软件调试的目的是发现错误并改正错误。软件测试要严格执行测试计划，排除测试的随意性。程序调试通常也称Debug，对被调试的程序进行“错误定位”是程序调试的必要步骤。　　答案：C　　【真题3】按照软件测试的一般步骤，集成测试应在__【2】__测试之后进行。（2008年9月）　　解析：软件测试过程分4个步骤，即单元测试、集成测试、验收测试和系统测试。所以集成测试在单元测试之后。　　答案：单元　　【真题4】测试用例包括输入值集与__【1】__值集。（2008年4月）　　解析：测试用例由测试输入数据(输入值集)和与之对应的预期输出结果(输出值集)两部分组成。　　答案：输出　　【真题5】在两种基本测试方法中，__【2】__测试的原则之一是保证所测试模块中每一个独立路径至少要执行一次。（2007年9月）　　解析：白盒测试的基本原则是：保证所测模块中每一个独立路径至少执行一次；保证所测模块所有判断的每一个分支至少执行一次；保证所测模块每一条循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。按照白盒测试的基本原则，“白盒”法是穷举路径测试。　　答案：白盒【真题6】下列叙述中正确的是________。（2007年3月）　　A)为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作　　B)软件测试是证明软件没有错误　　C)软件测试的主要目的是发现程序中的错误　　D)软件测试的主要目的是确定程序中错误的位置　　解析：软件测试是为了发现错误而执行程序的过程。一个好的测试用例是指尽可能地找到迄今为止尚未发现的错误的用例；一个成功的测试是指发现了至今尚未发现的错误的测试。为了达到好的测试效果，应该由独立的第三方来构造测试，程序员应尽量避免检查自己的程序。　　答案：C　　【真题7】软件测试分为白盒测试和黑盒测试。等价类划分法属于__【2】__测试。（2007年3月）\n　　解析：黑盒测试也称功能测试或数据驱动测试。它是对软件已经实现的功能是否满足需求进行测试和验证。黑箱测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。黑箱测试方法主要有等价类划分法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。　　答案：黑盒　　【真题8】程序测试分为静态分析和动态测试。其中__【4】__是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误。（2006年4月）　　解析：程序测试分为静态分析和动态测试。其中，静态分析是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误。　　答案：静态分析　　【真题9】下列叙述中正确的是________。（2005年9月）　　A)程序经调试改错后还应进行再测试　　B)程序经调试改错后不必进行再测试　　C)程序设计就是编制程序　　D)程序的测试必须由程序员自己去完成　　解析：软件测试仍然是保证软件可靠性的主要手段，测试的目的是要尽量发现程序中的错误，调试主要是推断错误的原因，从而进一步改正错误。测试和调试是软件测试阶段的两个密切相关的过程，通常是交替进行的。　　答案：A　　【真题10】在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块（桩模块）。其中__【3】__模块的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。（2005年9月）　　解析：由于模块不是一个独立的程序，不能单独运行，因此，在进行模块测试时，还应为每个被测试的模块另外设计两类模块：驱动模块和承接模块。由于模块不是一个独立的程序，不能单独运行，因此，在进行模块测试时，还应为每个被测试的模块另外设计两类模块：驱动模块和承接模块。其中驱动模块的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果；承接模块的作用是模拟被测试模块的下层模块。通常，承接模块有多个。　　答案：驱动　　【真题11】下列对于软件测试的描述中正确的是________。（2005年4月）　　A)软件测试的目的是尽可以多地发现程序中的错误\n　　B)软件测试的目的是使程序符合结构化原则　　C)软件测试的目的是证明程序是否正确　　D)软件测试的目的是使程序运行结果正确　　解析：　　1、软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。　　2、软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。　　3、测试不是为了证明程序是正确的，而是在设想程序有错误的前提下进行的，其目的是设法暴露程序中的错误和缺陷。　　答案：A　　【真题12】软件测试的目的是________。（2010年9月）　　A)改正程序中的错误　　B)发现程序中的错误　　C)评估软件可靠性　　D)发现并改正程序中的错误　　解析：软件测试的目的是尽可能多的发现程序中的错误，而不是为了单纯的改正程序中的错误。　　答案：BPoint7：程序的调试　　考点精讲　　1、程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。　　2、程序调试的基本步骤：(1)错误定位；(2)修改设计和代码，以排除错误；(3)进行回归测试，防止引进新的错误。　　3、程序调试可分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试。主要调试方法有：(1)强行排错法；(2)回溯法；(3)原因排除法。　　真题分析　　【真题1】软件调试的目的是________。（2007年9月）\n　　A)改善软件的性能　　B)验证软件的正确性　　C)发现错误　　D)改正错误　　解析：软件调试的任务是诊断和改正程序中的错误。程序调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位置；二是对程序进行修改，排除这个错误。　　答案：D　　【真题2】软件__【2】__阶段的任务是诊断和改正程序中的错误。（2006年9月）　　解析：软件测试的目的是发现程序中的错误，而调试的目的是确定程序中错误的位置和引起错误的原因，并加以改正。换句话说，调试的目的就是诊断和改正程序中的错误。调试不是测试，但是它总是发生在测试之后。。　　答案：调试　　【真题3】下列叙述中正确的是________。（2006年4月）　　A)软件维护只包括对程序代码的维护　　B)三种说法都不对　　-50-C)软件测试应该由程序开发者来完成　　D)程序经调试后一般不需要再测试　　解析：本题考核软件测试、软件调试和软件维护的概念。软件测试具有挑剔性，测试不是为了证明程序是正确的，而是在设想程序有错误的前提下进行的，其目的是设法暴露程序中的错误和缺陷，就是说，测试是程序执行的过程，目的在于发现错误；一个好的测试在于能发现至今未发现的错误；一个成功的测试是发现了至今未发现的错误。由于测试的这一特征，一般应当避免由开发者测试自己的程序。　　调试也称排错，目的是发现错误的位置，并改正错误，经测试发现错误后，可以立即进行调试并改正错误；经过调试后的程序还需进行回归测试，以检查调试的效果，同时也可防止在调试过程中引进新的错误。　　软件维护通常有四类：为纠正使用中出现的错误而进行的改正性维护；为适应环境变化而进行的适应性维护；为改进原有软件而进行的完善性维护；为将来的可维护和可靠而进行的预防性维护。软件维护不仅包括程序代码的维护，还包括文档的维护。文档可以分为用户文档和系统文档两类。但无论是哪类文档，都必须与程序代码同时维护。只有与程序代码完全一致的文档才有意义和价值。　　答案：B\n　　【真题4】诊断和改正程序中错误的工作通常称为软件__【3】__。（2005年4月）　　解析：调试也称排错，调试的目的是发现错误的位置，并改正错误。一般的调试过程分为错误检查、错误诊断和改正错误。　　答案：调试　　【真题5】软件（程序）调试的任务是________。（2010年3月）　　A)发现并改正程序中的所有错误　　B)确定程序中错误的性质　　C)诊断和改正程序中的错误　　D)尽可能多地发现程序中的错误　　解析：调试也称排错或纠错。它与成功的测试形影相随，测试成功的标志是发现错误。根据错误迹象，诊断错误的原因和位置，进而改正程序中的错误，这就是调试的任务。　　答案：C　　【真题6】下列叙述中正确的是________。（2005年9月）　　A)软件交付使用后其生命周期就结束　　B)软件维护是指修复程序中被破坏的指令　　C)软件交付使用后还需要进行维护　　D)软件一旦交付使用就不需要再进行维护　　解析：本题考核软件维护的概念。维护是软件生命周期的最后一个阶段，也是持续时间最长、付出代价最大的阶段，在软件交付使用后，还需要进行维护。　　软件维护通常有以下四类：　　1、为纠正使用中出现的错误而进行的改正性维护；　　2、为适应环境变化而进行的适应性维护；　　3、为改进原有软件而进行的完善性维护；　　4、为将来的可维护和可靠而进行的预防性维护。软件维护不仅包括程序代码的维护，还包括文档的维护。　　答案：C\n第3天：数据结构：栈、队列、二叉树等　　Point1：数据结构的定义　　出题趋势　　考试日期07-9　09-9　　出题次数1　　　1　　考点精讲　　1、数据结构：是指相互有关联的数据元素的集合。　　(1)数据结构研究以下三个方面的问题：　　①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；　　②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；　　③对各种数据结构进行的运算。　　研究以上问题的主要目的是为了提高数据处理的效率（一是提高数据处理的速度，二是节省数据处理过程所占的空间。）　　(2)数据的逻辑结构反映数据元素之间的逻辑关系，即前、后件关系，分为线性结构（线性表、栈和队列）和非线性结构（树和图）。包含：　　①表示数据元素的信息；　　②表示各数据元素之间的前后件关系。　　(3)数据的存储结构，是指数据逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一般来说，一种数据逻辑结构根据需要可以表示成多种存储结构，常用的数据的存储结构有顺序、链接、索引等。　　2、数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有顺序、链接、索引等。采用不同的存储结构，数据处理的效率是不相同的。　　真题分析　　【真题1】下列数据结构中，属于非线性结构的是________。（2009年9月）　　A)二叉树\n　　-52-B)带链栈　　C)循环队列　　D)带链队列　　解析：线性结构，是最简单最常用的一种数据结构。线性结构的特点是结构中的元素之间满足线性关系，按这个关系可以把所有元素排成一个线性序列，如：线性表、串、栈和队列都属于线性结构。而非线性结构是指在该类结构中至少存在一个数据元素，它具有两个或者两个以上的前件或后件，如树和二叉树等。　　答案：A　　【真题2】下列叙述正确的是________。（2007年9月）　　A)程序执行的效率只取决于所处理的数据量　　B)以上三种说法都不对　　C)程序执行的效率与数据的存储结构密切相关　　D)程序执行的效率只取决于程序的控制结构　　解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别，其中，链式存储结构的效率要高一些。　　答案：CPoint2：线性表、线性链表和循环链表　　出题趋势　　考试日期06-4　06-9　09-3　10-9　　出题次数1　　　1　　　1　　　1　　考点精讲　　1、如果在一个数据结构中一个数据元素都没有，则称为空的数据结构。根据数据结构中各数据元素之间的前后件关系的复杂程度，分为线性结构与非线性结构。　　2、如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性表是一个典型的线性结构。常见的有：线性表，栈，队列，循环队列和线性链表等。\n　　3、不满足线性结构条件的数据结构，就是非线性结构。常见的有：数组、广义表、树、二叉树和图都是非线性结构。　　4、在计算机内，线性表的存储结构有两种：顺序存储（称为线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。　　真题分析　　【真题1】下列叙述中正确的是________。（2009年3月）　　A)循环队列是非线性结构　　B)有序线性表既可以采用顺序存储结构，也可以采用链式存储结构　　C)栈是“先进先出”的线性表　　D)队列是“先进后出”的线性表　　解析：主要考查了栈、队列、循环队列的概念，栈是“先进后出”的线性表，队列是“先进先出”的线性表。根据数据结构中各数据元素之问的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。循环队列也是线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。　　答案：B　　【真题2】数据结构分为线性结构和非线性结构，带链的队列属于__【5】__结构。（2006年9月）　　解析：数据结构分为线性结构和非线性结构，其中队列属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为带链队列。题目中所说的带链的队列就是指带链队列。无论队列采取哪种存储结构，其本质还是队列，仍属于一种线性结构。因此，本题的正确答案是线性结构。　　答案：线性　　【真题3】下列叙述中正确的是________。（2006年4月）　　A)双向链表是非线性结构　　B)只有根结点的二叉树是线性结构　　C)线性链表是线性表的链式存储结构　　D)栈与队列是非线性结构　　解析：线性链表是线性表的链式存储结构。栈与队列是特殊的线性表，它们也是线性结构；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构；二叉树是非线性结构，而不是线性结构。\n　　一个非空的数据结构如果满足下列两个条件：　　(1)有且只有一个根结点；　　(2)每一个结点最多有一个前件，也最多有一个后件，则称之为线性结构。　　答案：C　　【真题4】下列叙述中正确的是________。（2010年9月）　　A)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构　　B)上述三种说法都不对　　C)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的　　D)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构　　解析：可以从存储密度的角度，比较链式存储结构和顺序存储结构的存储空间：所谓存储密度是指结点数据本身所占的存储量除以结点结构所占的存储总量所得的值。这个值越大，存储空间利用率越高。顺序表是静态分配的，其存　　储密度为1；而链式存储是动态分配的，其存储密度小于1。　　答案：DPoint3：栈、队列和循环队列　　出题趋势考试日期05-405-906-406-907-307-908-408-909-309-910-310-9出题次数111111222222　　考点精讲　　1、栈（Stack）又称堆栈。　　(1)栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。　　(2)由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（LastInFirstOut，简称LIFO）；先进栈的元素必定后出栈，所以又把栈称为先进后出表（FirstInLastOut，简称FILO）。\n　　2、队列（Queue）简称队。　　(1)队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作队尾（rear），允许删除的一端称作队首（front）。　　(2)向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。(3)由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（FirstInFirstOut，简称FIFO）。3、循环队列。就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。真题分析　　【真题1】对于循环队列，下列叙述中正确的是________。（2009年9月）　　A)队头指针一定小于队尾指针　　B)队头指针可以大于队尾指针，也可以小于队尾指针　　C)队头指针是固定不变的　　D)队头指针一定大于队尾指针　　解析：循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追　　赶尾指针。所以队头指针可以大于队尾指针，也可以小于队尾指针。　　答案：B　　【真题2】下列叙述中正确的是________。（2008年9月）　　A)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况　　B)循环队列中元素的个数是由队头指针和队尾指针共同决定　　C)循环队列有队头和队尾两个指针，因此循环队列是非线性结构　　D)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况　　解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。　　答案：B　　【真题3】设某循环队列的容量为50，头指针front=5(指向队头元素)，尾指针rear=29(指向队尾元素)，则该循环队列中共有__【3】__个元素。（2008年4月）\n　　解析：在循环队列中因为头指针指向的是队头元素的前一个位置，所以是从第6个位置开始有数据元素，即计算从6到29之间有多少个元素，所以队列中的数据元素的个数为：29-6+1=29-5=24。　　答案：24　　【真题4】线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的__【3】__存储结构。（2007年9月）　　解析：队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。　　答案：顺序　　【真题5】下列对队列的叙述正确的是________。（2007年3月）　　A)队列在队尾删除数据　　B)队列按“先进先出”原则组织数据　　C)队列属于非线性表　　D)队列按“先进后出”原则组织数据　　解析：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数据结构中，最先插入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。　　答案：B　　【真题6】一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为__【1】__。（2010年3月）　　解析：对于队列来讲，是先进先出。　　答案：A,B,C,D,E,F,5,4,3,2,1　　【真题7】设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有__【2】__个元素。（2010年3月）　　解析：这次头指针在尾指针之后，因为是循环队列，所以应该是从46到50，再从1到10构成了这个队列。　　答案：15　　【真题8】下列数据结构中，能够按照“先进后出”原则存取数据的是________。（2009年9月）\n　　A)队列　　B)二叉树　　C)循环队列　　D)栈　　解析：由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以栈被称为后进先出表(LastInFirstOut,简称LIFO)；先进栈的元素必定后出栈，所以又把栈称为先进后出表(FirstInLastOut,简称FILO)。　　答案：D　【真题9】假设用一个长度为50的数组(数组元素的下标从0到49作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30(数组下标),则栈中具有__【1】__个元素。（2009年3月）　　解析：栈底指针到栈顶指针就是当前栈中的所有元素的个数。(注意，此处最容易错误的算成19)　　答案：20　　【真题10】支持子程序调用的数据结构是________。（2009年3月）　　A)队列　　B)二叉树　　C)栈　　D)树　　解析：这个部分的知识超过了教材的范围，但考试也考到过。下面的解析很多同学反应不能理解，建议大家记住答案就可以了。这个部分的知识超过了教材的范围，但考试也考到过。下面的解析很多同学反应不能理解，建议大家记住答案就可以了。　　栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。　　答案：C　　【真题11】一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是________。（2008年9月）　　A)ABCDE12345\n　　B)54321EDCBA　　C)12345ABCDE　　D)EDCBA54321　　解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是EDCBA54321。　　答案：D　　【真题12】下列关于栈的叙述正确的是________。（2008年4月）　　A)只能在栈底插入数据　　B)不能删除数据　　C)栈按“先进先出”组织数据　　D)栈按“先进后出”组织数据　　解析：栈是限定在顶端进行数据插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。　　答案：D　　【真题13】按“先进后出”原则组织数据的数据结构是__【4】__。（2006年9月）　　解析：栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行组织。　　答案：栈　　【真题14】按照“后进先出”原则组织数据的数据结构是________。（2006年4月）　　A)双向链表　　B)二叉树　　C)队列　　D)栈　　解析：“后进先出”表示最后被插入的元素最先能被删除。“后进先出”表示最后被插入的元素最先能被删除。\n　　1、队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则；　　2、栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先进先出”和“后进先出”的数据组织方式。　　3、双向链表使用链式存储方式，二叉树也通常采用链式存储方式，它们的存储数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。　　答案：D　　【真题15】下列关于栈的描述正确的是________。（2005年9月）　　A)栈是特殊的线性表，只能在一端插入或删除元素　　B)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素　　C)在栈中只能插入元素而不能删除元素　　D)在栈中只能删除元素而不能插入元素　　解析：栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。　　答案：A　　【真题16】下列关于栈的描述中错误的是________。（2005年4月）　　A)栈具有记忆作用　　B)对栈的插入与删除操作中，不需要改变栈底指针　　C)栈是先进后出的线性表　　D)栈只能顺序存储　　解析：本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。　　1、栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素。　　2、栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用。　　3、对栈进行插入和删除操作时，栈顶位置是动态变化的，栈底指针不变。\n　　答案：D　　【真题17】下列叙述中正确的是________。（2010年9月）　　A)在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化　　B)上述三种说法都不对　　C)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化　　D)在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化　　解析：栈是限定仅在一端进行插入和删除操作的线性表。允许插入和删除的一端叫做栈顶，另一端叫做栈底，因此栈中元素随栈顶指针的变化而动态变化，而栈底指针不变。　　答案：A　　【真题18】一个栈的初始状态为空。首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈(包括中间退栈的元素)的顺序为__【1】__。（2010年9月）　　解析：本题主要考查栈的出入操作。栈是一种先进后出的数据结构。题目告诉我们将5，4，3，2，1依次入栈，然后退栈一次，很显然这时退栈的是1，接着将A，B，C，D入栈，然后全部退栈，其栈中各元素的退栈顺序是DCBA2345。所以最后出栈的顺序应该是1DCBA2345。　　答案：1DCBA2345