二级公共基础知识培训

全国全国计算机等算机等级考考试之之二二级公共基公共基础知知识l二级公共基础知识分值10分,全部为选择题。l包括内容：包括内容：l数据结构与算法（40%）l程序设计基础（20%）l软件工程基础（20%）l数据库设计基础（20%）第一章第一章数据数据结构与算法构与算法l算法是指解算法是指解题方案的准确而完整的描述。方案的准确而完整的描述。换句句话说，算法是，算法是对特定特定问题求解步求解步骤的一种描述。的一种描述。l算法不等于程序，也不等于算法不等于程序，也不等于计算方法。程序的算方法。程序的编制不可能制不可能优于算法的于算法的设计。l所所谓算法，是一算法，是一组严谨地定地定义运算运算顺序的序的规则，并且每一个，并且每一个规则都是有效的，且是明确的，此都是有效的，且是明确的，此顺序将在有限的次数下序将在有限的次数下终止。止。算法定算法定义l（1）可行性。）可行性。针对实际问题而而设计的算法，的算法，执行后能行后能够得到得到满意的意的结果。果。l（2）确定性。每一条指令的含）确定性。每一条指令的含义明确，无二明确，无二义性。并且在任何条件下，算法只有唯一的一条性。并且在任何条件下，算法只有唯一的一条执行路径，即行路径，即相同的相同的输入只能得出相同的入只能得出相同的输出。出。l（3）有）有穷性。算法必性。算法必须在有限的在有限的时间内完成。有两重含内完成。有两重含义，一是算法中的操作步，一是算法中的操作步骤为有限个，二是每个步有限个，二是每个步骤都能在有限都能在有限时间内完成。内完成。l（4）拥有足有足够的情的情报。一个算法。一个算法执行的行的结果果总是与是与输入的初始数据有关，不同的入的初始数据有关，不同的输入将会有不同的入将会有不同的结果果输出。当出。当输入不入不够或或输入入错误时，算法将无法，算法将无法执行或行或执行有行有错。一般。一般说来，当算法来，当算法拥有足有足够的情的情报时，此算法，此算法才是有效的；而当提供的情才是有效的；而当提供的情报不不够时，算法可能无效。，算法可能无效。算法的基本特征算法的基本特征l算法算法时间复复杂度是指度是指执行算法所需要的行算法所需要的计算工作量算工作量，可以用，可以用执行算法的行算法的过程中所需程中所需基本运算的基本运算的执行次数行次数来来度量。度量。l算法空算法空间复复杂度是指度是指执行行这个算法所需要的个算法所需要的内存空内存空间。算法复算法复杂度度思考：算法的思考：算法的时间复复杂度与空度与空间复复杂度是否相关？度是否相关？真真题示例示例答案：答案：C答案：答案：D(2)算法的算法的时间复复杂度是指（度是指（）(2010.3)A.算法的算法的执行行时间B.算法所算法所处理数据和数据量理数据和数据量C.算法程序中的算法程序中的语句或指令条数句或指令条数D.算法在算法在实现过程中所需要的基本运算次数程中所需要的基本运算次数l数据数据结构是指相互有关构是指相互有关联的数据元素的集合。的数据元素的集合。l数据数据结构主要研究和构主要研究和讨论以下三个方面的以下三个方面的问题：l数据集合中各数据元素之数据集合中各数据元素之间所固有的所固有的逻辑关系，即关系，即数据的数据的逻辑结构。数据的构。数据的逻辑结构包含：构包含：1）表示数据元素的信息；）表示数据元素的信息；2）表）表示各数据元素之示各数据元素之间的前后件关系。的前后件关系。l在在对数据数据进行行处理理时，各数据元素在，各数据元素在计算机中的存算机中的存储关系，即关系，即数据的存数据的存储结构（物理构（物理结构）。数据的存构）。数据的存储结构有构有顺序、序、链接、索引等接、索引等。l对各种数据各种数据结构构进行的运算。行的运算。l注：逻辑结构和物理构和物理结构不是一一构不是一一对应关系关系。数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构是数据的物理结构在计算机存储空间中的存放形式。同一种同一种逻辑结构的数据可以采用不同的存构的数据可以采用不同的存储结构，但影响构，但影响数据数据处理效率。理效率。数据数据结构的基本概念构的基本概念l线性性结构构：1）有且只有一个根）有且只有一个根结点点2）每一个）每一个结点最点最多有一个前件，也最多有一个后件。常多有一个前件，也最多有一个后件。常见的的线性性结构有构有线性表、性表、栈、队列和列和线性性链表等。表等。l非非线性性结构构：不：不满足足线性性结构条件的数据构条件的数据结构。常构。常见的非的非线性性结构有构有树、二叉、二叉树和和图等。等。数据数据结构的构的类型型数据数据结构分构分为线性性结构和非构和非线性性结构，构，带链的的队列属于（列属于（）（）（2006.9）带链的的栈属于（属于（）(2011.9)l线性表由一性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相的相对位置是位置是线性的。性的。线性性表是由表是由n(n0)个数据元素个数据元素组成的一个有限序列，成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件件，除了最后一个外，有且只有一个后件。线性表中性表中数据元素的个数数据元素的个数称称为线性表的性表的长度。度。线性表可以性表可以为空空表表。（a1,a2,a3,ai-1,ai,ai+1,an)l线性表是一种存性表是一种存储结构，它的存构，它的存储方式：方式：顺序和序和链式。式。线性表及其性表及其顺序存序存储结构构l特点：（特点：（1）线性表中所有元素所占的存性表中所有元素所占的存储空空间是是连续的；（的；（2）线性表中各数据元素在存性表中各数据元素在存储空空间中是按中是按逻辑顺序序依次存放的。依次存放的。l顺序表的插入、序表的插入、删除、除、查找运算找运算演示演示顺性表的插入运算性表的插入运算时需要移需要移动元素，在等概率情况下，平均需要移元素，在等概率情况下，平均需要移动n/2个个元素；元素；进行行顺性表的性表的删除运算除运算时也需要移也需要移动元素，在等概率情况下，平均元素，在等概率情况下，平均需要移需要移动（n-1）/2个元素。插入、个元素。插入、删除运算不方便。除运算不方便。线性表性表顺序存序存储结构构真真题练习：在：在长度度为n的的顺序存序存储的的线性表中插入一个元素，最坏情况下需要移性表中插入一个元素，最坏情况下需要移动表中表中()个元素个元素(2011.9)，删除一个元素最坏情况下需要移除一个元素最坏情况下需要移动的元素个数的元素个数为（）(2012.3)答案答案:n,n-1l是限定是限定在一端在一端进行插入与行插入与删除运算除运算的的线性表性表l在在栈中，允中，允许插入与插入与删除的一端称除的一端称为栈顶，不允，不允许插入与插入与删除的另一端称除的另一端称为栈底底。栈顶元素元素总是最后被插是最后被插入的元素，入的元素，栈底元素底元素总是最先被插入的元素。即是最先被插入的元素。即栈是按照是按照“先先进后出后出”或或“后后进先出先出”的原的原则组织数据的。数据的。栈具有具有记忆作用，支持子作用，支持子过程程调用用。l栈的基本运算：的基本运算：1）插入元素称）插入元素称为入入栈运算；运算；2）删除元素称除元素称为退退栈运算；运算；3）读栈顶元素是将元素是将栈顶元素元素赋给一个指定的一个指定的变量，此量，此时指指针无无变化。化。l栈的存的存储方式和方式和线性表性表类似，也有两种，即似，也有两种，即顺序序栈和和链式式栈。栈及其基本运算（演示）及其基本运算（演示）l一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA答案：答案：Bl假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_个元素答案：答案：20真真题示例示例u下列关于下列关于栈的叙述正确的是（的叙述正确的是（）。）。A）栈按按“先先进先出先出”组织数据数据B）栈按按“先先进后出后出”组织数据数据C）只能在）只能在栈底插入数据底插入数据D）不能）不能删除数据除数据u一个一个栈的初始状的初始状态为空。首先将元素空。首先将元素5,4,3,2,1依次入依次入栈，然后，然后退退栈一次一次，再将元素，再将元素A,B,C,D依次入依次入栈，之后将所有元素，之后将所有元素全部退全部退栈，则所有元素退所有元素退栈（包括中（包括中间退退栈的元素）的的元素）的顺序序为_（2010.9）真真题示例示例答案：答案：1DCBA2345u下列关于栈的叙述中，正确的是（）A)栈底元素一定是最后入栈的元素B）栈操作遵循先进后出的原则C)栈顶元素一定是最先入栈的元素D)以上三种说法都不对u设栈的存储空间为S（1:40），初始状态为bottom=0,top=0。现经过一系列入栈与出栈运算后，top=20，则当前栈中有_个元素答案：答案：20真真题示例示例(2012.9)l是指允是指允许在一端（在一端（队尾）尾）进入插入，而在另一端（入插入，而在另一端（队头）进行行删除的除的线性表。尾指性表。尾指针（Rear）指向）指向队尾元尾元素，素，头指指针（front）指向排）指向排头元素的前一个位置（元素的前一个位置（队头）。）。l队列是列是“先先进先出先出”或或“后后进后出后出”的的线性表。性表。l队列运算包括：列运算包括：1）入）入队运算：从运算：从队尾插入一个元素；尾插入一个元素；2）退）退队运算：从运算：从队头删除一个元素。除一个元素。队列及其基本运算列及其基本运算（演示）（演示）l循循环队列列，就是将，就是将队列存列存储空空间的最后一个位置的最后一个位置绕到第一个位置，形成到第一个位置，形成逻辑上的上的环状空状空间，供，供队列循列循环使使用。在循用。在循环队列中，用列中，用队尾指尾指针rear指向指向队列中的列中的队尾元素，用排尾元素，用排头指指针front指向排指向排头元素的前一个位置，元素的前一个位置，因此，从因此，从头指指针front指向的后一个位置直到指向的后一个位置直到队尾指尾指针rear指向的位置之指向的位置之间，所有的元素均，所有的元素均为队列中的元素。列中的元素。l循循环队列一般用列一般用顺序存序存储。循循环队列列（演示）（演示）循循环队列中元素的个数是由列中元素的个数是由队头指指针和和队尾指尾指针共同决定共同决定l（1）循）循环队列元素的个数列元素的个数为（rear-front+m）%m，其中，其中m为循循环队列容量。列容量。l（2）如果）如果rear-front0,则循循环队列元素个数列元素个数为rear-front;如果如果rear-front0,则循循环队列元素个数列元素个数为rear-front+m;l真真题示例：示例：（1）设某循某循环列列队的容量的容量为50，如果，如果头指指针front=45（指向（指向队头元素的前一位置），尾指元素的前一位置），尾指针rear=10（指向（指向队尾元素），尾元素），则该循循环队列中共有列中共有_个元素。个元素。答案：答案：15（2010.3）（2）对于循于循环队列，下列叙述中正确的是（列，下列叙述中正确的是（）lA)队头指指针是固定不是固定不变的的lB)队头指指针是一定大于是一定大于队尾指尾指针lC)队头指指针一定小于一定小于队尾指尾指针lD)队头指指针可以大于可以大于队尾指尾指针，也可以小于，也可以小于队尾指尾指针计算循算循环队列个数两种方法：列个数两种方法：真真题示例：示例：（3）下列叙述中正确的是：（）下列叙述中正确的是：（）（2012.3）lA)循循环队列是列是队列的一种列的一种顺序存序存储结构构lB)循循环队列是列是队列的一种列的一种链式存式存储结构构lC)循循环队列是非列是非线性性结构构D)循循环队列是一直列是一直逻辑结构构（4）设循循环队列的存列的存储空空间为Q(1:30),初始状初始状态为front=rear=30。现经过一系列入一系列入队与退与退队运算后，运算后，front=16，rear=15，则循循环队列中有列中有_个元素。个元素。（2012.3）(5)设循循环队列的存列的存储空空间为Q（1:35），初始状），初始状态为ront=rear=35.现经过一系列入一系列入队与退与退队运算后，运算后，front=15,rear=15，则循循环队列中的元素个数列中的元素个数为（）（2012.9）lA)20B)0或或35C)15D)16答案：答案：A，29,20l线性表性表顺序存序存储的缺点：（的缺点：（1）插入或插入或删除的运算效率很低除的运算效率很低。在。在顺序存序存储的的线性表中，插入或性表中，插入或删除数据元素除数据元素时需要移需要移动大量的数据元素；（大量的数据元素；（2）线性表的性表的顺序存序存储结构下，构下，线性表的性表的存存储空空间不便于不便于扩充充；（；（3）线性性表的表的顺序序存存储结构不便于构不便于对存存储空空间的的动态分配分配。l线性性链表：表：线性表的性表的链式存式存储结构称构称为线性性链表，是一种物理存表，是一种物理存储单元上元上非非连续、非非顺序序的存的存储结构，数构，数据元素的据元素的逻辑顺序是通序是通过链表中的指表中的指针链接来接来实现的。因此，在的。因此，在链式存式存储方式中，每个方式中，每个结点由两部分点由两部分组成：成：一部分用于存放数据元素的一部分用于存放数据元素的值，称，称为数据域数据域；另一部分用于存放指；另一部分用于存放指针，称，称为指指针域域，用于指向，用于指向该结点的前点的前一个或后一个一个或后一个结点（即前件或后件）点（即前件或后件）线性性链表表（演示）（演示）线性性链表分表分为单链表、双向表、双向链表和循表和循环链表三种表三种类型型。在在单链表中，每一个表中，每一个结点只有一个指点只有一个指针域，由域，由这个指个指针只能找到其后件只能找到其后件结点，而不能找到其前件点，而不能找到其前件结点。点。在某些在某些应用中，用中，对于于线性性链表中的每个表中的每个结点点设置两个指置两个指针，一个称，一个称为左指左指针，指向其前件，指向其前件结点；另一个点；另一个称称为右指右指针，指向其后件，指向其后件结点，点，这种种链表称表称为双向双向链表表l下列叙述中正确的是（下列叙述中正确的是（）（2010.9）A）线性表的性表的链式存式存储结构与构与顺序存序存储结构所需要的存构所需要的存储空空间是相同的是相同的B）线性表的性表的链式存式存储结构所需要的存构所需要的存储空空间一般要多于一般要多于顺序存序存储结构构C）线性表的性表的链式存式存储结构所需要的存构所需要的存储空空间一般要少于一般要少于顺序存序存储结构构D）上述三种）上述三种说法都不法都不对真真题示例示例答案：答案：Bl下列关于下列关于线性性链表的叙述中，正确的是（）表的叙述中，正确的是（）（2011.9）A)各数据各数据结点的存点的存储空空间可以不可以不连续，但它，但它们的存的存储顺序与序与逻辑顺序必序必须一致一致B)各数据各数据结点的存点的存储顺序与序与逻辑顺序可以不一致，但它序可以不一致，但它们的存的存储空空间必必须连续C)进行插入与行插入与删除除时，不需要移，不需要移动表中的元素。表中的元素。D)以上三种以上三种说法都不法都不对真真题示例示例答案：答案：Cl树是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父父结点点。没有前件的结点只有一个，称为树的根结点，简称树的根的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子叶子结点点。l在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有所有结点中最大的度称点中最大的度称为树的度。的度。树的最大的最大层次称次称为树的深度的深度。树的基本概念的基本概念判断哪些判断哪些结点是根与叶子点是根与叶子结点？点？树的度与深度是的度与深度是？真真题练习某系某系统总体体结构构图如下如下图所示所示：该系系统总体体结构构图的深度是（的深度是（）（2011.9）A)7 B)6 C)3 D)2答案：答案：Cl二叉二叉树是一种很有用的非是一种很有用的非线性性结构，它具有以下两个特点：构，它具有以下两个特点：1）非空二叉非空二叉树只有一个根只有一个根结点点；2）每一个）每一个结点最多有两棵子点最多有两棵子树，且分，且分别称称为该结点的左子点的左子树与右子与右子树。l二叉二叉树的基本性的基本性质：二叉二叉树及其基本性及其基本性质计算：深度算：深度为5的二叉的二叉树最多有最多有_个个结点，其中第点，其中第4层上上最多有最多有_个个结点点真真题示例示例l某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（）。A）n+1B）n-1C）2nD）n/2l某二叉某二叉树有有5个度个度为2的的结点以及点以及3个度个度为1的的结点，点，则该二叉二叉树中共有中共有_个个结点点l某二叉树共有7个个结点点，其中叶子叶子结点只有点只有1个个，则该二叉树的深度为（假设根结点在第1层）A）3B）4C）6D）7答案：答案：A14D真真题示例示例l一棵二叉一棵二叉树共有共有25个个节点，其中点，其中5个是叶子个是叶子节点，那么度点，那么度为1的的节点数点数为（）A)4B)6C)10D)16l一棵二叉一棵二叉树中共有中共有70个叶子个叶子结点与点与80个度个度为1的的结点，点，则该二叉二叉树中的中的总结点数点数为（）A）219B）221C）229D）231答案：答案：DAl满二叉二叉树：除最后一：除最后一层外，每一外，每一层上的所有上的所有结点都有两个子点都有两个子结点。点。l完全二叉完全二叉树：除最后一：除最后一层外，每一外，每一层上的上的结点数均达到最大点数均达到最大值；在最后一；在最后一层上只缺少右上只缺少右边的若干的若干结点。点。完全二叉完全二叉树与与满二叉二叉树l第k层上有个结点l深度为m的满二叉树共有个结点满二叉二叉树特性特性真题练习：深度为5的满二叉树有_个叶子结点注：一般二叉一般二叉树通常采用通常采用链式存式存储结构，构，对于于满二叉二叉树与完全二叉与完全二叉树来来说，可以按，可以按层序序进行行顺序存序存储。这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：l（1）前序遍）前序遍历（DLR）：若二叉树为空，则结束返回。否则：首先首先访问根根结点，然后遍点，然后遍历左子左子树，最后遍，最后遍历右子右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。l（2）中序遍）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍首先遍历左子左子树，然后，然后访问根根结点，最后遍点，最后遍历右子右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。l（3）后序遍）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。二叉二叉树遍遍历二叉二叉树遍遍历RACDBEFG练习：对该二叉二叉树进行前序行前序/中序中序/后序遍后序遍历结果果?真真题练习：真真题练习：设二叉二叉树如下：如下：对该二叉二叉树进行后序遍行后序遍历的的结果果为（）。答案答案;EDBGHFCAl一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为_。真真题练习：答案：答案：DEBFCAl下列链表中，其逻辑结构属于非线性结构的是（）（2012.9）lA)双向链表B)带链的栈C)二叉链表D)循环链表真真题练习：答案：答案：Cl查找：找：根据根据给定的某个定的某个值，在，在查找表中确定一个其关找表中确定一个其关键字等于字等于给定定值的数据元素。的数据元素。l查找找结果：果：（查找成功：找到；找成功：找到；查找不成功：没找到。）找不成功：没找到。）l平均平均查找找长度度：查找找过程中关程中关键字和字和给定定值比比较的平均次数。的平均次数。查找技找技术l基本思想：基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。l在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况最坏情况下需要比下需要比较n次次。l顺序查找一个具有n个元素的线性表，其平均复平均复杂度度为O（n），平均），平均长度度为（n+1）/2.顺序序查找找l思想：思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。l前提：前提：必须在具有顺序存序存储结构的有序表构的有序表中进行。l查找找过程：（演示程：（演示过程）程）l1）若中间项（中间项mid=(n-1)/2，mid的值四舍五入取整）的值等于x，则说明已查到；l2）若x小于中间项的值，则在线性表的前半部分查找；l3）若x大于中间项的值，则在线性表的后半部分查找。l特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。l二分法二分法查找只适用于找只适用于顺序存序存储的的线性表，且表中元素必性表，且表中元素必须按关按关键字有序（升序）排列字有序（升序）排列。对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O（log2n）。二分法二分法查找找(演示演示)l排序排序是指将一个无序序列整理成按是指将一个无序序列整理成按值非非递减减顺序排列的有序序列，即是将无序的序排列的有序序列，即是将无序的记录序列序列调整整为有序有序记录序列的一种操作。序列的一种操作。l1、交交换类排序法排序法（方法：冒泡排序，快速排序）。（方法：冒泡排序，快速排序）。l2、插入插入类排序法排序法（方法：（方法：简单插入排序，希插入排序，希尔排序）。排序）。l3、选择类排序法排序法（方法：（方法：简单选择排序，堆排序）。排序，堆排序）。排序技排序技术排序技排序技术总结（1）下列排序方法中，最坏情况下比）下列排序方法中，最坏情况下比较次数最少的是次数最少的是A）冒泡排序）冒泡排序B）简单选择排序排序C）直接插入排序）直接插入排序D）堆排序）堆排序真真题练习冒泡排序、直接插入排序、冒泡排序、直接插入排序、简单选择排序最坏情况下都需排序最坏情况下都需要比要比较n(n-1)/2.堆排序法，最坏情况需要堆排序法，最坏情况需要o(nlong2n)次比次比较（2）对长对长度度为为10的的线线性表性表进进行冒泡排序，最坏情况行冒泡排序，最坏情况下需要比下需要比较较的次数的次数为为_。第二章第二章程序程序设计基基础l主要主要强调“清晰第一、效率第二清晰第一、效率第二”。l主要主要应注重和考注重和考虑下述一些因素下述一些因素：l（1）源程序文档化。）源程序文档化。（2）数据）数据说明明（3）语句的句的结构。构。（4）输入和入和输出。出。程序程序设计风格格l结构化程序设计方法的主要原则可以概括为：自自顶向下向下，逐步求精逐步求精，模模块化化，限制使用限制使用goto语句句。l（1）自自顶向下向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。l（2）逐步求精逐步求精。对复杂问题，应设计一些子目标作过渡，逐步细化。l（3）模模块化化。一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。l（4）限制使用限制使用goto语句句。结构化程序构化程序设计l1）顺序序结构构。一种简单的程序设计，即按照程序语句行的自然顺序，一条语句一条语句地执行程序，它是最基本、最常用的结构。2）选择结构构。又称分支分支结构构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列。3）重复重复结构构。又称循循环结构构，可根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。结构化程序基本构化程序基本结构构流程流程图语句句1语句句2判判读下列流程下列流程图分分别是什么是什么结构？构？(1)下列下列选项中不属于中不属于结构化程序构化程序设计原原则的是（）（的是（）（2009.9）A)可封装可封装B)自自顶向下向下C)模模块化化D)逐步求精逐步求精（2）结构化程序所要求的基本构化程序所要求的基本结构不包括构不包括（）（）(2011.3)A）顺序序结构构B）GOTO跳跳转C）选择（分支）（分支）结构构D）重复（循）重复（循环）结构构真真题练习l客观世界中任何一个事物都可以被看成是一个对象，面向面向对象方法的本象方法的本质就是主就是主张从客从客观世界固有的事物世界固有的事物出出发来构造系来构造系统，提倡人，提倡人们在在现实生活中常用的思生活中常用的思维来来认识、理解和描述客、理解和描述客观事物事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象及对象之间的关系能够如实地反映问题域中固有的事物及其关系。面向面向对象程序象程序设计l面向对象方法的主要优点：（1）与人与人类习惯的思的思维方法一致方法一致；（；（2）稳定性好定性好；（；（3）可重用性好可重用性好；（；（4）易于开易于开发大型大型软件件产品品；（；（5）可可维护性好性好。l面向对象的程序设计主要考虑的是提高提高软件的可重用性件的可重用性。l面向对象三大特征：封装性、封装性、继承性、多承性、多态性性。l对象象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。对象是属性和方法的封装体象是属性和方法的封装体。l属性属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。l操作操作描述了对象执行的功能，操作也称为方法或服务。操作是对象的动态属性。一个对象由对象名象名、属性属性和和操作操作三部分组成。面向面向对象程序象程序设计有关概念有关概念l（1）标识惟一性惟一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。l（2）分分类性性。指可以将具有相同属性的操作的对象抽象成类。l（3）多多态性性。指同一个操作可以是不同对象的行为。l（4）封装性封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。信息信息隐蔽是通蔽是通过对象的封装性来象的封装性来实现的的l（5）模模块独立性好独立性好。对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。对象基本特点象基本特点l类是指具有共同属性、共同方法的对象的集合。所以类是是对象的抽象，象的抽象，对象是象是对应类的一个的一个实例例。消息是一个消息是一个实例与另一个例与另一个实例之例之间传递的信息的信息。l在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。继承承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重承和多重继承承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。l类的继承性承性是类之间共享属性和操作的机制，它提高了软件的可重用性。多多态性性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。面向面向对象程序象程序设计有关概念有关概念l面向对象方法中，继承是指（）（2010.9）A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质C）各对象之间的共同性质D）类之间共享属性和操作的机制真真题示例示例答案：答案：Dl下列选项中属于面向对象设计方法主要特征的是()(2011.9)A)继承B)自顶向下C)模块化D)逐步求精答案：答案：Al常见的软件工程方法有结构化方法和面向对象方法，类、继承以及多态性等概念属于_。(2012.3)第三章第三章软件工程基件工程基础l计算机算机软件是包括件是包括程序程序、数据数据及相关及相关文档文档的完整集合。的完整集合。l软件按功能分件按功能分为应用用软件件、系系统软件件、支撑支撑软件件（或工具（或工具软件）件）软件有关概念件有关概念真真题练习（1）软件按功能可以分件按功能可以分为：应用用软件、系件、系统软件和支撑件和支撑软件（或工具件（或工具软件）。下面属于系件）。下面属于系统软件的是件的是（）（2010.3）A)编辑软件件B)操作系操作系统C)教教务管理系管理系统D)浏览器器(2)软件按功能可以分件按功能可以分为应用用软件、系件、系统软件和支撑件和支撑软件（或工具件（或工具软件）。下面属于件）。下面属于应用用软件的是件的是（）（2011.9）A)学生成学生成绩管理系管理系统B)C语言言编译程序程序C)UNIX操作系操作系统D)数据数据库管理系管理系统答案答案：（1）B（2）Al软件危机件危机是泛指是泛指在在计算机算机软件的开件的开发和和维护过程中所遇到的一系列程中所遇到的一系列严重重问题。主要表。主要表现在成本、在成本、质量、量、生生产率等率等问题。l软件工程件工程是是应用于用于计算机算机软件的定件的定义、开、开发和和维护的一整套方法、工具、文档、的一整套方法、工具、文档、实践践标准和工序。准和工序。l主要思想是将主要思想是将工程化工程化原原则运用到运用到软件开件开发过程，它包括程，它包括3个要素：个要素：方法方法、工具工具和和过程程（2008.9）。方法是）。方法是完成完成软件工程件工程项目的技目的技术手段；工具是支持手段；工具是支持软件的开件的开发、管理、文档生成；、管理、文档生成；过程支持程支持软件开件开发的各个的各个环节的控制、管理。的控制、管理。软件工程件工程过程是把程是把输入入转化化为输出出的一的一组彼此相关的彼此相关的资源和活源和活动。软件工程与件工程与软件危机件危机l软件生命周期是指件生命周期是指软件件产品从提出、品从提出、实现、使用、使用维护到停止使用退役的到停止使用退役的过程。程。l软件生命周期分件生命周期分为软件定件定义、软件开件开发及及软件运行件运行维护三个三个阶段：段：1）软件定件定义阶段段：包括制定：包括制定计划和需求分析。划和需求分析。制定制定计划：确定划：确定总目目标；可行性研究；探；可行性研究；探讨解决方案；制定开解决方案；制定开发计划。划。需求分析：需求分析：对待开待开发软件提出的需求件提出的需求进行分析并行分析并给出出详细的定的定义。l2）软件开件开发阶段段：软件件设计：分：分为概要概要设计和和详细设计两个部分。两个部分。软件件实现：把：把软件件设计转换成成计算机可以接受的程序代算机可以接受的程序代码。软件件测试：在：在设计测试用例的基用例的基础上上检验软件的各个件的各个组成部分。成部分。l3）软件运行件运行维护阶段段：软件投入运行，并在使用中不断地件投入运行，并在使用中不断地维护，进行必要的行必要的扩充和充和删改。改。l软件生命周期中所花件生命周期中所花费最多的最多的阶段是段是软件运行件运行维护阶段段。软件生命周期件生命周期l（1）软件生命周期可分件生命周期可分为定定义阶段，开段，开发阶段和段和维护阶段。段。详细设计属于（属于（）（2010.3）A)定定义阶段段B)开开发阶段段C)维护阶段段D)上述三个上述三个阶段段l（2）软件生命周期可分件生命周期可分为多个多个阶段，一般分段，一般分为定定义阶段、开段、开发阶段和段和维护阶段。段。编码和和测试属于属于_阶段。段。(2007.4)l(3)下面描述中，不属于下面描述中，不属于软件危机表件危机表现的是（的是（）(2010.9)A）软件件过程不程不规范范B）软件开件开发生生产率低率低C）软件件质量量难以控制以控制D）软件成本不断提高件成本不断提高l(4)软件生命周期中的活件生命周期中的活动不包括（不包括（）(2012.3)A)软件件维护B)市市场调研研C)软件件测试D)需求分析需求分析真真题练习软件工程的目件工程的目标和原和原则：参：参见P18l需求分析方法有：1）结构化需求分析方法；2）面向对象的分析方法。需求分析的任需求分析的任务就是导出目标系统的逻辑模型，解决“做什么做什么”的问题。l需求分析一般分为需求需求获取、需求分析、取、需求分析、编写需求写需求规格格说明明书和需求和需求评审四个步骤进行。需求分析需求分析真真题练习：下面不属于需求分析阶段任务的是（）A)确定软件系统的功能需求B)确定软件系统的性能需求B)制定软件集成测试计划D)需求规格说明书审评真真题练习l软件需求规格说明书的作用不包括（）lA）软件设计的依据lB）软件可行性研究的依据lC）软件验收的依据lD）用户与开发人员对软件要做什么的共同理解软件件需求需求规格格说明明书的作用在于便于用的作用在于便于用户、开、开发人人员进行行理解和交流，反映出用理解和交流，反映出用户问题的的结构，可以作构，可以作为软件件设计和开和开发工作的基工作的基础和依据，并作和依据，并作为确确认测试和和验收的依据。收的依据。l实质：着眼于数据流，：着眼于数据流，自自顶向下向下，逐逐层分解分解，建立系建立系统的的处理流程，以数据流理流程，以数据流图和数据字典和数据字典为主要工具，主要工具，建立系建立系统的的逻辑模型。模型。l工具：工具：1）数据流数据流图（DFD）；）；2）数据字典数据字典（DD）；）；3）判定判定树；4）判定表判定表。结构化分析构化分析l定定义：以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。数据流数据流图（DFD）l定定义：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。l数据字典的作用作用是对数据流数据流图中出中出现的被命名的的被命名的图形元素的确切解形元素的确切解释。数据字典是数据字典是结构化分析方法的核心构化分析方法的核心。数据字典（数据字典（DD）真真题练习（1）数据流程数据流程图(DFD图)是（）（2010.3）A)软件概要设计的工具B)软件详细设计的工具C)结构化方法的需求分析工具D)面向对象方法的需求分析工具（2）在结构化分析使用的数据流图（DFD）中，利用_对其中的图形元素进行确切解释。(2007.4)（3）下列关于数据库设计的叙述中，正确的是（）(2011.9)A)在需求分析阶段建立数据字典B)在概念设计阶段建立数据字典C)在逻辑设计阶段建立数据字典D)在物理设计阶段建立数据字典答案：答案：C数据字典数据字典Al需求分析需求分析主要解决“做什么做什么”的问题，而软件件设计主要解决“怎么做怎么做”的问题。l从技术观点来看，软件设计包括软件结构构设计、数据数据设计、接口接口设计、过程程设计。l结构构设计：定义软件系统各主要部件之间的关系。l数据数据设计：将分析时创建的模型转化为数据结构的定义。l接口接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。l过程程设计：把系统结构部件转换成软件的过程性描述。结构化构化设计方法方法l从工程角度来看，软件设计分两步完成，即概要概要设计和详细设计。（2006.9）l概要概要设计：又称结构构设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式。l详细设计：确定每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。结构化构化设计方法方法l软件件设计的基本原理包括：的基本原理包括：抽象抽象、模模块化化、信息信息隐蔽蔽和和模模块独立性独立性l模模块分解的主要指分解的主要指导思想是思想是信息信息隐蔽蔽和和模模块独立性独立性l模模块的的耦合性耦合性和和内聚性内聚性是衡量是衡量软件的模件的模块独立性的两个定性指独立性的两个定性指标。l内聚性内聚性：是一个模：是一个模块内部各个元素内部各个元素间彼此彼此结合的合的紧密程度的度量。密程度的度量。l耦合性耦合性：是模：是模块间互相互相连接的接的紧密程度的度量。密程度的度量。l一个一个设计良好的良好的软件系件系统应具有具有高内聚、低耦合高内聚、低耦合的特征。的特征。（2006.4，2007.4,2008.4,2009.3,2009.9)结构化构化设计方法方法l详细设计的任任务是确定实现算法和局部数据结构，不同于编码或编程，用某种选定的表达工具表示算法和数据结构的细节。l图形工具形工具：程序流程图、N-S（方盒图）、PAD（问题分析图）和HIPO（层次图+输入/处理/输出图）。l表格工具表格工具：判定表。l语言工具言工具：PDL（伪码）：过程设计语言，它是用正文形式表示数据和处理过程的设计工具。详细设计课堂拓展堂拓展该图是程序流程图，其中菱形框表示的是菱形框表示的是逻辑条件条件，矩形表示各种处理功能，流线的箭头表示一个控制过程的流程方向。真真题练习1.下面描述中错误的是()(2011.3)A）系统总体结构图支持软件系统的详细设计B）软件设计是将软件需求转换为软件表示的过程C）数据结构与数据库设计是软件设计的任务之一D）PAD图是软件详细设计的表示工具提示：系提示：系统总体体结构构图是是对软件系件系统结构的构的总体体设计的的图形形显示，示，故故A错误。2.在软件设计中不使用的工具是（）(2011.3)A)系统结构图B)程序流程图C)PAD图D)数据流图（DFD图）提示：提示：DFD图是是进行行结构化需求分析的工具，构化需求分析的工具，故故选D。l目的：尽可能地多目的：尽可能地多发现程序中的程序中的错误，不能也不可能，不能也不可能证明程序没有明程序没有错误。（2007.4，2009.3）l软件件测试方法：方法：静静态测试和和动态测试。l静静态测试：包括代：包括代码检查、静、静态结构分析、代构分析、代码质量度量。不量度量。不实际运行运行软件，主要通件，主要通过人工人工进行。行。（2006.4）l动态测试：是基于：是基于计算机的算机的测试，主要包括白盒，主要包括白盒测试方法和黑盒方法和黑盒测试方法。方法。软件件测试l白盒白盒测试方法也称方法也称为结构构测试或或逻辑驱动测试。它是根据。它是根据软件件产品的内部工作品的内部工作过程，程，检查内部成分，以确内部成分，以确认每种内部操作符合每种内部操作符合设计规格要求。格要求。l白盒白盒测试法的法的测试用例是根据程序的用例是根据程序的内部内部逻辑来来设计的，主要用的，主要用软件的件的单元元测试，主要方法有，主要方法有逻辑覆盖、覆盖、基本路径基本路径测试等等l例：例：软件件测试可分可分为白盒白盒测试和黑盒和黑盒测试。基本路径。基本路径测试属于属于_测试。白盒白盒测试（2007.4，2007.9，2009.3）l黑盒黑盒测试方法也称方法也称为功能功能测试或数据或数据驱动测试。黑盒。黑盒测试是是对软件已件已经实现的功能的功能是否是否满足需求足需求进行行测试和和验证。l黑盒黑盒测试不关心程序内部的不关心程序内部的逻辑，只是根据，只是根据程序的功能程序的功能说明明来来设计测试用例，主要方法有等价用例，主要方法有等价类划分法、划分法、边界界值分析法、分析法、错误推推测法等，主要用法等，主要用软件的件的确确认测试黑盒黑盒测试真真题练习：在黑盒在黑盒测试方式中，方式中，设计测试用例的主要根据是（用例的主要根据是（）（）（2012.3）A)程序外部功能程序外部功能B)程序内部程序内部逻辑C)程序数据程序数据结构构D)程序流程程序流程图真真题练习：下面属于黑盒下面属于黑盒测试方法的是（方法的是（）A）边界界值分析分析B）路径覆盖）路径覆盖C）语句覆盖句覆盖D)逻辑覆盖覆盖l软件测试过程一般按4个步骤进行：单元元测试、集成集成测试、确确认测试和系系统测试。（2008.9）l单元元测试是对软件设计的最小单位模块（程序单元）进行正确性检测的测试，目的是发现各模块内部可能存在的各种错误。l集成集成测试是测试和组装软件的过程，它是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。l确确认测试的任务是验证软件的有效性，即验证软件的功能和性能及其他特性是否与用户的要求一致。l系系统测试的目的在于通过与系统的需求定义进行比较，发现软件与系统定义不符合或与之矛盾的地方。软件件测试过程程真真题练习：对软件件设计的最小的最小单位（模位（模块或程序或程序单元）元）进行的行的测试通常称通常称为_测试。（2011.3）l任任务是是诊断和改正程序中的断和改正程序中的错误，主要在开，主要在开发阶段段进行，主要由程序行，主要由程序员完成。完成。l程序程序调试的基本步的基本步骤：（：（1）错误定位定位；（；（2）纠正正错误；（；（3）回回归测试l软件件调试可分可分为静静态调试和和动态调试。静。静态调试主要是指通主要是指通过人的思人的思维来分析源程序代来分析源程序代码和排和排错，是主要，是主要的的调试手段，而手段，而动态调试是是辅助静助静态调试程序程序调试（2006.9，2007.9，2010.3）例：例：软件件(程序程序)调试的任的任务是（）是（）（2010.3，2011.9）A)诊断和改正程序中的断和改正程序中的错误B)尽可能多地尽可能多地发现程序中的程序中的错误C)发现并改正程序中的所有并改正程序中的所有错误D)确定程序中确定程序中错误的性的性质例：例：软件件调试的目的是（的目的是（B）。（）。（2007.9）A）发现错误B）改正）改正错误C）改善）改善软件的性能件的性能D）验证软件的正确性件的正确性第四章第四章数据数据库设计基基础l数据数据：实际上就是描述事物的符号记录。l数据数据库（DB）：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。数据数据库技技术的根本目的根本目标是解决数据共享是解决数据共享。（2007.4，207.9）l数据数据库管理系管理系统（DBMS）：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据数据库的核心的核心（2007.4，2009.3）。真真题示例：示例：数据数据库管理系管理系统是是（）（2009.9)A)操作系操作系统的一部分的一部分B)在操作系在操作系统支撑下的系支撑下的系统软件件C)一种一种编译系系统D)一种操作系一种操作系统数据数据库系系统的基本概念的基本概念l数据数据库管理管理员（DBA）：）：对数据数据库进行行规划、划、设计、维护、监视等的等的专业管理人管理人员。l数据数据库系系统（DBS）：由）：由数据数据库（数据）、数据（数据）、数据库管理系管理系统（软件）、数据件）、数据库管理管理员（人（人员）、硬件平台）、硬件平台（硬件）、（硬件）、软件平台（件平台（软件）五个部分构成的运行件）五个部分构成的运行实体。体。l数据数据库应用系用系统：由数据：由数据库系系统、应用用软件及件及应用界面三者用界面三者组成。成。数据数据库系系统的基本概念的基本概念数据数据库管理系管理系统提供的数据提供的数据语言言l数据定数据定义语言言：负责数据的模式定数据的模式定义与数据的物理存取构建（与数据的物理存取构建（2008.4，2010.3）l数据操数据操纵语言言：负责数据的操数据的操纵，如，如查询与增、与增、删、改等、改等l数据控制数据控制语言言：负责数据完整性、安全性的定数据完整性、安全性的定义与与检查以及并以及并发控制、故障恢复等。控制、故障恢复等。l关系：关系：DBS包括包括DBMS和和DB。（。（2006.4）有关考点有关考点真真题练习：1.负责数据数据库中中查询操作的数据操作的数据库语言是（言是（）（2011.3）A）数据定）数据定义语言言B）数据管理）数据管理语言言C）数据操）数据操纵语言言D）数据控制）数据控制语言言2.数据数据库管理系管理系统提供的数据提供的数据语言中，言中，负责数据的增、数据的增、删、改和、改和查询的是的是_（2012.3）数据数据库技技术的的发展展人工管理阶段人工管理阶段文件系统阶段文件系统阶段数据库系统阶段数据库系统阶段背景应用背景科学计算科学计算、管理大规模管理硬件背景无直接存取存储设备磁盘、磁鼓大容量磁备盘软件背景没有操作系统有文件系统有数据库管理系统处理方式批处理联机实时处理、批处理联机实时处理、分布处理、批处理特点数据的管理者用户（程序员）文件系统数据库管理系统数据面向的对象某一应用程序某一应用现实世界数据的共享程度无共享，冗余度极大共享性差，冗余度大共享性高，冗余度小数据的独立性不独立，完全依赖于程序独立性差具有高度的物理独立性和一定的逻辑独立性数据的结构化无结构记录内有结构，整体无结构整体结构化，用数据模型描述数据控制能力应用程序自己控制应用程序自己控制由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力l（1）数据的高集成性高集成性。（2）数据的高共享性高共享性与低冗余性低冗余性。l（3）数据独立性数据独立性(2006.4)：数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。也就是说，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。l物理独立性物理独立性：指数据的物理结构(如存储设备更换、物理存储方式)的改变，不影响数据库的逻辑结构，也不会引起应用程序的变化。l逻辑独立性独立性：数据库总体逻辑结构的改变(如修改数据模式、增加新的数据类型、改变数据间联系等)，不需要相应修改应用程序。l（4）数据数据统一管理与控制一管理与控制。数据数据库系系统的特点的特点真真题练习：数据独立性分数据独立性分为逻辑独立性和物理独立性。当独立性和物理独立性。当总体体逻辑结构改构改变时，其局部，其局部逻辑结构可以不构可以不变，从而根据，从而根据局部局部逻辑结构构编写的写的应用程序不必修改，称用程序不必修改，称为_。l概念模式概念模式：数据：数据库系系统中全局中全局数据数据逻辑结构的描述构的描述，是全体用，是全体用户（应用）公共数据用）公共数据视图。l外模式外模式：也称子模式或用：也称子模式或用户模式，它是用模式，它是用户的数据的数据视图，也就是，也就是用用户所所见到的数据模式到的数据模式，它由概念模式推，它由概念模式推导而出。而出。l内模式内模式：又称物理模式，它：又称物理模式，它给出了数据出了数据库物理物理存存储结构与物理存取方法构与物理存取方法。内模式的物理性主要体。内模式的物理性主要体现在操作在操作系系统及文件及文件级上，它上，它还未深入到未深入到设备级上（如磁上（如磁盘及磁及磁盘操作）。操作）。数据数据库系系统的三的三级模式（模式（2011.9）真真题练习：在数据在数据库系系统中，用中，用户所所见的数据模式的数据模式为（）。（）。（2006.9）A）概念模式）概念模式B）外模式）外模式C）内模式）内模式D）物理模式）物理模式l1）概念模式概念模式/内模式的映射内模式的映射：实现了概念模式到内模式之间的相互转换。当数据库的存储结构发生变化时，通过修改相应的概念模式/内模式的映射，使得数据库的逻辑模式不变，其外模式不变，应用程序不用修改，从而保证数据具有很高的物理独立性物理独立性。l2）外模式外模式/概念模式的映射概念模式的映射：实现了外模式到概念模式之间的相互转换。当逻辑模式发生变化时，通过修改相应的外模式/逻辑模式映射，使得用户所