全国计算机等级考试二级公共基础考点.doc

全国计算机等级考试二级公共基础部分考点第一部分 数据结构部分考点1 算法的复杂度1. 算法的基本概念算法是对问题求解过程的精确描述。算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的3种基本控制结构：顺序结构、选择结构、循环结构。算法基本设计方法主要有：列举法、归纳法、递推、递归、减半递推技术、回溯法。指令系统：一台计算机系统能执行的所有指令的集合。2. 算法的复杂度算法的复杂度包括时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行算法所需要的内存空间。典型题例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）A）和B）6问题处理方案的正确而完整的描述称为 。算法考点2 逻辑结构和存储结构1. 数据结构的基本概念(1)数据结构：是指相互有关联的数据元素的集合。(2)数据结构主要研究3个方面的内容：数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；在对资料进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。2. 逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。所以一个数据结构B可以表示成：B=(D，R)例如，如果把一年四季看作一个数据结构，则可表示成：B=(D,R)，其中D=春季，夏季，秋季，冬季，R=（春季，夏季）,（夏季，秋季），（秋季，冬季）。3. 存储结构数据的逻辑结构在计算机存储空间中的存放形式称数据的存储（物理）结构。数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储结构、链接存储结构。顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。链式存储结构就是在每个结点中至少包含一个指标域，用指标来体现数据元素之间逻辑上的联系。考点 3 线性结构和非线性结构1. 线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。如果一非空的数据结构满足：有且仅有一个根结点；每一个结点最多有一个前件，也最多有一件后件。则称该数据结构为线性结构或线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都是线性结构。2. 非线性结构如果一个数据结构不满足线性结构的两个条件的一个或两个，则该结构称为非线性结构。广义表、树和图等数据结构都是非线性结构。3. 线性表的顺序存储结构具有以下两个基本特点(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。例如，对于线性表(a1,a2,ai,an)元素ai的存储位址为：ADR(ai)=ADR(a1)+(i-1)*k其中，ADR(a1)是第一个元素的位址，k代表每个元素所占的位元组数。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）所需空间与其长度成正比考点 4 栈1. 栈的基本概念栈(stack)是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素。栈底元素总是最先被插入的元素，因而也是最后才能被删除的元素。栈是按照“先进后出” (First In Last Out,简称FILO)或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象地表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。2. 栈的顺序存储及其运算 栈的基本运算有3种：入栈、退栈与读栈顶元素。入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变数；读栈顶元素：将栈顶元素赋给一个指定的变数。典型题例1下列关于栈的叙述正确的是 。A）栈按“先进先出”组织数据 B）栈按“先进后出”组织数据C）只能在栈底插入数据 D）不能删除数据2一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是 。A）12345ABCDE B）EDCBA54321C）ABCDE12345 D）54321EDCBA3假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_【1】_个元素。194下列数据结果中，能够按照“先进后出”原则存取资料的是 。A) 循环队列 B) 栈 C)队列 D)二叉树5下列关于栈的叙述中，正确的是 。A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除C)栈底元素永远不能被删除 D)以上三种说法都不对6下列关于栈的叙述中，正确的是 。A)栈底元素一定一定是最后入栈的元素B)栈操作遵循先进后出的原则C)栈顶元素一定是最先入栈的元素D)以上三种说法都不对7数据结构分为线性结构与非线性结构，带链的栈属于 【1】 。线性结构8设栈的存储空间为S（1：40），初始状态为bottom=0,top=0，现经过一系列入栈和出栈运算后，top=20，则当前栈中有 【1】 元素。209以下不是栈的基本运算的是 。A)判断栈是否为空B)将栈置为空栈C)删除栈顶元素D)删除栈底元素考点 5 队列1. 队列的基本概念队列是只允许在一端进行删除，在另一端进行插入的线性表，通常将允许删除的一端称为队头，允许插入的一端称为队尾。当表中没有元素时称为空队列。队列是按照“先进先出”的原则来组织数据的，与栈相反，队列又称为“先进先出”(First In First Out,简称FIFO)或“后进后出”(Last In Last Out,简称LILO)的线性表。例如：火车进隧道，最先进遂道的是火车头，最后是火车尾。而火车出遂道的时候也是火车头先出，最后出的是火车尾。更一般地，若有队列：Q=(q1,q2,qn)那么，q1为队头元素，qn是队尾元素。队列中的元素是按照q1,q2,qn的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1,q2,qn-1都出队之后，qn才能出队。队列体现了一种“先来先服务”的原则。2. 队列的运算入队：往队尾插入一个数据元素；出队：从队列的队头删除一个数据元素。由于存在假“溢出”现象，队列的顺序存储结构一般采用循环队列的形式。计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。例如：设某循环队列的容量为40（序号为039），现经过一系列的入队和出队运算后，有：front=11,rear=19front=19,rear=11则该循环队列中的元素个数分别为：8和32。典型题例1设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有【3】个元素。242下列叙述正确的是 。A）循环队列有队头和队尾两个指针，因此，循环队列是非线形结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数由队头指标和队尾指标共同决定3对于循环队列，下列叙述中正确的是 。A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指标可以大于队尾指标，也可以小于队尾指标4. 一个队列的初始状态为空，先将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为 【1】 。ABCDEF543215. 设某循环列队的容量为50，如果头指标front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有【2】个元素。156. 设循环列队的存储空间为Q（1：30），初始状态为front=rear=30。现经过一系列入队与退队运算后，front=16，rear=15，则该循环队列中共有【2】个元素。297设循环队列的存储空间为Q（1：35），初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为 。A）20 B）0或35C）15D）168下列叙述中正确的是 。 A）栈是“先进先出”的线性表 B）队列是“先进先出”的线性表 C）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构9支持子程序调用的数据结构是 。 A）栈 B）树 C）队列 D）二叉树考点6 链表在链式存储方式中，要求每个结点至少由两部分组成：一部分用于存放数据元素值，称为值域；另一部分用于存放指针，称为指针域。其中指标用于指向该结点的前一个或后一个结点。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。1. 线性链表线性表的链式存储结构称为线性链表。在某些应用中，对线性链表中的每个结点设置两个指标，一个称为左指标，用于指向其前件结点；另一个称为右指标，用于指向其后件结点。这样的链表称为双向链表。在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除，不需要移动链表中的元素。线性单链表中，要设置一个头指针，一般用head来表示，当head=NULL（或0）时称为空表。如果是双向链表，则两个指针通常为：左指标(Llink)指向前件结点，右指标(Rlink)指向后件结点。线性链表的基本运算有：查找、插入、删除等。2. 带链的栈栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。典型题例1下列关于线性链表的叙述中，正确的是 。A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素D.以上三种说法都不对2下列对于线性链表的描述中正确的是 。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的3下列叙述中正确的是 。A) 线性链表是线性表的链式存储结构B) 栈与队列是非线性结构C) 双向链表是非线性结构D) 只有根结点的二叉树是线性结构4数据结构分为线性结构和非线性结构，带链的队列属于 。线性结构考点 7 二叉树及其基本性质1. 二叉树及其基本概念二叉树是一种很有用的非线性结构，具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树。另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。在二叉树中，一个结点可以只有左子树而没有左子树；也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点称为叶子结点。如图1-1中的各结点说明及有关二叉树的基本概念详见表1-1。图1-1 二叉树示例图表1-1 二叉树的基本概念根(父)结点在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。例如，在图1-1中，结点A是树的根。 子结点和叶子结点在树结构中，每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。例如，在图1-1中，结点D、E、F均为叶子结点。度在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。例如，在图 1-1中，根结点 A和结点 B的度为2，结点 C的度为1，叶子结点D，E，F的度为0。所以，该树的度为2。深度若一棵树的根结点所在的层次为1，其它结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。例如，在图 1-1中，根结点 A在第 1层，结点B，C在第2层，结点 D，E，F在第 3层。该树的深度为3。子树在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。2. 二叉树基本性质 二叉树具有以下几个性质：性质1：在二叉树的第k层上，最多有2k-1(k1)个结点； 性质2：深度为 m的二叉树最多有2m-1个结点；性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，即n0=n2+1。 性质4：具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m1个结点。完全二叉树是指这样的二叉树：除了最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干个结点。对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现。对于任何一个结点，若其右分支下的子孙结点的最大层数为p，则其左分支下的子孙结点的最大层数或为p，或为p+1.完全二叉树具有以下两个性质：性质5：具有n个结点的完全二叉树的深度为log2n+1。性质6：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k(k=1，2，n)的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为(int)(k/2)。若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。考点 8 二叉树的遍历1. 二叉树及其基本概念在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。(1)前序遍历前序遍历的次序为：访问根结点、前序遍历左子树、前序遍历右子树。例如，对图1-1中的二叉树进行前序遍历的结果(前序序列)为：ABDECF。(2)中序遍历中序遍历的次序为：中序遍历左子树、访问根结点、中序遍历右子树。例如，对图1-1中的二叉树进行中序遍历的结果（中序序列）为： DBEACF。(3)后序遍历：后序遍历的次序为：后序遍历左子树、后序遍历右子树、访问根结点。例如，对图 1-1中的二叉树进行后序遍历的结果（后序序列）为：DEBFCA。典型题例1深度为5的满二叉树有 个叶子结点。162某二叉树有5个度为2的结点，则该二叉树的叶子结点数是 。 A）10 B）8 C）6 D）43某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有 个结点。144某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层） 。A)3 B)4 C)6 D)75对下列二叉树进行中序遍历的结果是 。DBXEAYFZCDBCFEAZYX6一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历的结果为 。DEBFCA7已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是 。A)ACBDEB)DEABCC)DECAB D)EDBAC8下列关于二叉树的叙述中，正确的是 。A.叶子结点总是比度为2的结点少一个B.叶子结点总是比度为2的结点多一个C.叶子结点数是度为2的结点数的两倍D.度为2的结点数是度为1的结点数的两倍9某二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数是 。 A）16 B）10 C）6 D）410设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中叶子结点的个数为 。8DBCFGEAH 11设二叉数如下：对该二叉树进行后序遍历的结果为 。EDBGHFCA12一棵二叉树共有47个结点，其中有23个度为2的结点。假设根结点在第1层上，则该二叉树的深度为 。6考点 9 顺序查找查找是指在一个给定的数据结构中查找某指定元素。可从线性表的第1个元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中的所有元素都与被查找元素进行了比较，但都不等，则表示查找失败。在下列两种情况下，只能采用顺序查找：(1)如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找；(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。考点10 二分法查找二分法查找，也称折半查找，这是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：(1)用顺序存储结构； (2)线性表是有序表。为了简化问题，“有序”是特指元素按非递减排列，但允许相邻元素相等。对于长度为n的有序线性表，利用二分法查找元素X的过程如下：步骤1：将 X与线性表的中间项比较；步骤2：如果 X的值与中间项的值相等，则查找成功，结束查找；步骤3：如果 X小于中间项的值，则在线性表的前半部分以二分法继续查找；步骤4：如果 X大于中间项的值，则在线性表的后半部分以二分法继续查找。例如，长度为8的线性表关键码序列为：6,13,27,30,38,46,47,70，被查元素为38，首先将与线性表的中间项比较，即与第4个数据元素30相比较，38大于中间项 30的值，则在线性表38,46,47,70 继续查找；再与该子表的中间项比较，即与第2个元素46相比较，38小于46，则在线性表38中继续查找，最后一次比较相等，查找成功，查找38时，共进行了3次比较。顺序查找法每一次比较，只将查找范围减少1，而二分法查找每比较一次，可将查找范围减少为原来的一半，效率大大提高。对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。典型题例1下列叙述中正确的是_。A)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)C)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)D)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)2在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是 。A）O(n) B）O(n2) C）O(log2n) D）O(nlog2n)3有序线性表能进行二分查找的前提是该线性表必须是 存储的。顺序4在长度为n的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中 个元素。n5在长度为64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A)63 B)64 C)6 D)76下列数据结构中，能用二分法进行查找的是_。A)顺序存储的有序线性表B)线性链表C)二叉链表D)有序线性链表7对长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。A)log2n B) n/2 C) n D) n+18在长度为n 的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为_。log2n9设有一个已按各元素的值排好序的线性表（长度大于2），对给定的k值，分别用顺序顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是_。A)s=b B) sbC) sb D) sb考点11 排序1. 交换类排序法(1)冒泡排序法冒泡排序法的算法思想是：从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最大者到了线性表的最后；对剩下的线性表重复上述过程，直到剩下的线性表变为空为止，此时已经排好序。在最坏的情况下，冒泡排序需要的比较次数为n(n-1)/2，算法复杂度为O(n2)。(2)快速排序法任取待排序序列中的某元素作为基准（一般取第1个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行快速排序，直至整个序列有序。快速排序最坏情况下的复杂度为O(n2)。2. 插入类排序法简单插入排序法，最坏情况需要n(n-1)/2次比较；复杂度为O(n2)。希尔排序法，最坏情况需要O(n1.5)3. 选择类排序简单选择排序法，最坏情况需要n(n-1)/2次比较；复杂度为O(n2)。堆排序法，最坏情况需要nlog2n次比较。复杂度为O(nlog2n)。相比以上几种排序法（除希尔排序法外），堆排序法的时间复杂度最小。4. 几种排序的比较假设线性表的长度为n，在最坏的情况下进行比较的次数：表1-2 几种排序的比较交换类排序法1冒泡排序：n(n-1)/2，O(n2)2快速排序：n(n-1)/2，O(n2)插入类排序法3简单插入排序：n(n-1)/2，O(n2)4希尔排序：O(n1.5)选择类排序法5简单选择排序：n(n-1)/2，O(n2)6堆排序：O(nlog2n)典型题例1对长度为n的线性表排序，最坏情况下，比较次数不是n(n-1)/2的排序方法是 。A）快速排序 B）冒泡排序 C）直接插入排序 D）堆排序2下列排序方法中，最坏情况下比较次数最少的是 。 A）冒泡排序 B）简单选择排序C）直接插入排序 D）堆排序3在最坏的情况下，冒泡排序的时间复杂度为_。O(n2)4简单的交换排序方法是 。 A）快速排序 B）选择排序C）堆排序 D）冒泡排序5在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是 。 A）左、右两个子表都已各自排好序B）左边子表中的元素都不大于右边子表中的元素C）左边子表的长度小于右边子表的长度D）左、右两个子表中元素的平均值相等第二部分 程序设计基础考点1 程序设计的方法与风格养成良好的程序设计风格，主要考虑下述因素：1. 源程序文檔化（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。（2）程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释。语句结构要遵循“清晰第一、效率第二”的原则。（3）视觉组织：通过在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。2. 数据说明的方法为使程序中的数据说明易于理解和维护，应使说明数据次序规范化、变量安排有序化、使用注释。 3程序的结构应该简单易懂，语句构造应该简单直接。4输入和输出合理。考点2 结构化程序设计1. 构化程序设计的原则 结构化程序设计方法引入了工程思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。自顶向下：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标。逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化。模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。限制使用 goto语句：在程序开发过程中要限制使用goto语句。2. 结构化程序设计的基本结构结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。考点3 面向对象方法面向对象方法(Object-Oriented Method)是一种把面向对象的思想应用于软件开发过程中，指导开发活动的系统方法，简称OO (Object-Oriented)方法，是建立在“对象”概念基础上的方法学。一般意义上的对象是指现实世界中一个实际存在的事物，它可以是有形的（比如一辆汽车），也可以是无形的（比如一项计划）。对象是构成世界的一个独立单位，它具有二个基本特征：(1)静态特征：可以用某种数据来描述；(2)动态特征：对象所表现的行为或具有的功能。面向对象方法中的对象是系统中用来描述客观事物的一个实体，它是用来构成系统的一个基本单位。对象由一组属性和一组行为构成。属性：用来描述对象静态特征的数据项。行为：用来描述对象动态特征的操作序列。1面向对象方法的基本要素(1)对象如前所述，面向对象中的对象是指一些属性及行为的封装体，是现实世界中某个具体的物理实体在计算机逻辑中的映像和体现。对象具有一组属性和一组操作。这些属性的值刻画了一个对象的状态，而这些操作是对象的行为，通过操作改变对象的状态（即属性值）。数据和操作封装于对象的统一体中，而不是分开。封装即信息隐藏。对象是一个很好的封装体。它向外提供的接口包括一组数据结构（属性）和一组操作（服务），而把内部的实现细节（如函数体）隐蔽起来。例如：窗口菜单（属性：颜色、式样、位置、标题等；行为：选择、移动、增加等）。通常把对象的操作称为方法或服务。操作描述了对象执行的功能，若通过信息的传递，还可以为其它对象使用。(2)抽象抽象是指强调实体的本质、内在的属性。使用抽象可以尽可能避免过早考虑一些细节。类实现了对象的数据（即状态）和行为的抽象。(3)类和实例类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质。属于类的某一个对象则被称为类的一个实例。例如：类：手表，对象：老王的手表。类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。(4)消息消息是对象之间相互请求或相互协作的途径，一条消息往往要告诉一个对象做什么，它需要指出：发送者、接收者、需要执行的服务、需要的参数。消息具有三个性质：(1)同一对象可接收不同形式的多个消息，产生不同的回应；(2)相同形式的消息可以送给不同对象，所作出的响应可以是不同的；(3)对消息的响应并不是必须的。对象具有如下特征：标识惟一性、分类性、封装性、继承性、多态性、模块独立性。2. 面向对象的主要特征有：(1) 物件唯一性每个物件都有自身唯一的标识，通过这种标识，可找到相应的物件。在对象的整个生命期中，它的标识都不改变，不同的对象不能有相同的标识。(2)分类性分类性是指将具有一致的数据结构(属性)和行为(操作)的对象抽象成类。一个类就是这样一种抽象，它反映了与应用有关的重要性质，而忽略其它一些无关内容。任何类的划分都是主观的，但必须与具体的应用有关。(3)封装性（信息隐藏）封装性是保证软件部件具有优良的模块性的基础。面向对象的类是封装良好的模块，类定义将其说明（用户可见的外部接口）与实现（用户不可见的内部实现）显式地分开，其内部实现按其具体定义的作用域提供保护。对象是封装的最基本单位。封装防止了程序相互依赖性而带来的变动影响。面向对象的封装比传统语言的封装更为清晰、更为有力。(4)继承性继承性是子类自动共享父类数据结构和方法的机制，这是类之间的一种关系。在定义和实现一个类的时候，可以在一个已经存在的类的基础之上来进行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容。继承体现了一种共享机制。继承性是面向对象程序设计语言不同于其它语言的最重要的特点，是其它语言所没有的。在类层次中，子类只继承一个父类的数据结构和方法，则称为单重继承。在类层次中，子类继承了多个父类的数据结构和方法，则称为多重继承。 (5)多态性多态性使指相同的操作或函数、过程可作用于多种类型的对象上并获得不同的结果。不同的对象，收到同一消息可以产生不同的结果，这种现象称为多态性。多态性允许每个对象以适合自身的方式去响应共同的消息。多态性增强了软件的灵活性和重用性。(6)模块独立性模块独立性指每个模块只完成系统要求的独立的子功能，并且与其它模块的联系最少且接口简单。这样可通过类库这种机制和结构而方便地实现不同应用中的信息共享。典型题例1程序流程图中有箭头的线段表示的是 。A）像素关系 B）数据流 C）控制流 D）调用关系2. 结构化程序设计的基本原则不包括 。A）多态性 B）自顶向下 C）模块化 D）逐步求精3. 在面向对象的方法中，不属于“对象”基本特点的是 。A） 一致性 B）分类性 C）多态性 D）标识唯一性4. 软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软件)，下面属于应用软件的是 。 A）编译程序 B）操作系统 C）教务管理系统 D）汇编程序5. 符合结构化原则的三种基本控制结构是：选择结构、循环结构和 。顺序结构6. 下列选项中不属于结构化程序设计原则的是 。A) 可封装 B) 自顶向下 C) 模块化 D) 逐步求精7. 程序流程图中的菱形框表示的是 。判断（逻辑）条件8. 结构化程序所要求的基本结构不包括 。 A) 顺序结构 B) GOTO跳转C)选择(分支)结构 D)重复(循环)结构9结构化程序设计主要强调的是 。A)程序的规模B)程序的易读性C)程序的执行效率D)程序的可移植性10对建立良好的程序设计风格，下列描述正确的是 。A)程序应简单、清晰、可读性好B)符号名的命名只要符合语法C)充分考虑程序的执行效率D)程序的注释可有可无11在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送 。A)调用语句B)命令C)口令D)消息12下列选项中，与信息隐蔽的概念直接相关的是_。A)软件结构定义B)模块独立性C)模块类型划分D)模块耦合度13下面对对象概念描述错误的是 。A)任何对象都必须有继承性B)对象是属性和方法的封装体C)对象间的通讯靠消息传递D)操作是对象的动态属性14. 下面描述中，符合结构化程序设计风格的是_。A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto 语句15.下面概念中，不属于面向对象方法的是_。A. 对象B. 继承C. 类D. 程序呼叫16. 面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是_。A. 模拟现实世界中不同事物之间的联系B. 强调模拟现实世界中的算法而不强调概念C. 使用现实世界的概念抽象地思考问题从而自然地解决问题D. 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考17.在设计程序时，应采纳的原则之一是_。A. 程序结构应有助于读者理解B. 不限制goto 语句的使用C. 减少或取消注解行D. 程序越短越好18.结构化程序设计的3 种结构是_。A）顺序结构、选择结构、转移结构B）分支结构、等价结构、循环结构C）多分支结构、赋值结构、等价结构D）顺序结构、选择结构、循环结构19在面向对象的方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技术叫做_。继承20对象的基本特点包括_、分类性、多态性、封装性和模块独立性等5个特点。标识惟一性21对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致完全不同的形为，这种现象称为_。多态性第三部分 软件工程基础考点1 软件工程基本概念1.软件定义与软件特点软件指的是计算机系统中与硬件相互依存的另一部分，是程序、数据和相关文文件的完整集合。程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文文件是与程序的开发、维护和使用有关的图文数据。根据应用目标的不同，软件可分应用软件（为解决特定领域的问题而开发的软件）、系统软件（计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件）和支撑软件（也称工具软件，是介于两者之间，协助用户开发软件的工具性软件)。软件的质量主要包括外部质量（软件中与用户和维护人员有关的，如正确性、健壮性、可扩充性、可复用性、可移植性等）和内部质量（与开发人员有关的，如可读性、可维护性等）。2.软件工程由于早期的程序设计方法是面向机器或面向过程的，使所设计的软件具有很大的局限性，这种落后的软件生产方式无法满足迅速增长的计算机软件需求，从而导致软件开发与维护过程中出现一系列严重问题的现象。例如，对程序的功能估计不准确、用户不满意、可维护性差、没有适当的文文件数据等，这就是所谓的软件危机。为了摆脱软件危机，提出了软件工程的概念。软件工程学是研究软件开发与维护的普遍原理与技术的一门工程学科。所谓软件工程是指：采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。软件工程包括3个要素：方法、工具和过程。方法：是完成软件工程项目的技术手段；工具：工具支持软件的开发、管理、文檔生成；过程：过程支持软件开发的各个环节的控制、管理。考点 2 软件生命周期1. 软件生命周期概念软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期分为3个时期8个阶段。(1)软件定义期：包括问题定义、可行性研究和需求分析3个阶段；(2)软件开发期：包括概要设计、详细设计、实现和测试4个阶段；(3)运行维护期：即运行维护阶段。软件生命周期各个阶段的活动可以有重复，执行时也可以有迭代，如图3-1所示。图3-1 软件生命周期2.软件生命周期各阶段的主要任务问题定义：确定要求解决的问题是什么。可行性研究与计划制定：决定该问题是否存在一个可行的解决办法，指定完成开发任务的实施计划。需求分析：对待开发软件提出需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。软件设计：通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块的划分、功能的 分配以及处理流程。这阶段提交评审的文檔有概要设计说明书、详细设计说明书和测试计划初稿。软件实现：在软件设计的基础上编写程序。这阶段完成的文文件有用户手册、操作手册等面向用户的文文件，以及为下一步作准备而编写的单元测试计划。软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。运行维护：将已交付的软件投入运行，并不断地维护，进行必要而且可行的扩充和删改。考点3 软件设计基本概念从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。（1）结构设计定义软件系统各主要部件之间的关系；（2）数据设计将分析时创建的模型转化为数据结构的定义；（3）接口设计是描述软件内部、软件和协作系统之间以及软件和人之间如何通信。（4）过程设计则是把系统结构部件转换为软件的过程性描述。从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。（1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；（2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法的数据结构的细节。典型题例1对软件的特点，下列描述正确的是 。A）软件是一种物理实体B）软件在运行使用期间不存在老化问题C）软件开发、运行对计算机没有依赖性，不受计算机系统的限制D）软件的生产有一个明显的制作过程2以下哪项是软件生命周期的主