计算机等级考试二级笔试的公共基础知识部分.doc

1、本章内容主要是计算机等级考试二级笔试的公共基础知识部分，其分值占总分的 。本章主要介绍一些关于程序设计的基础知识和面向对象的程序设计基础。主要分为 节内容，包括数据结构与算法、程序设计基础、软件工程基础和数据库设计基础。word文档 可自由复制I编辑算法考查知识点考核概率难易程度数据结构的基本概念线性表及其顺序存储结构栈和队列线性链表树与二叉树查找技术排序技术程序设计方法与风格结构化程序设计面向对象的程序设计软件工程基本概念结构化分析方法结构化设计方法软件测试程序的调试数据库系统的基本概念数据模型关系代数数据库设计与管理考点 算法算法的基本概念数据结构与算法算法是指对解题方案准确而完整的描述。

2、（）算法的基本特征。可行性：针对实际问题而设计的算法，执行后能够得到满意的结果，即必须有一个或多个输出。注意，对于某一算法，即使在数学理论上是正确的，但如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。确定性：指算法中每一步骤都必须是有明确定义的。有穷性：指算法必须能在有限的时间内做完。拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。（）算法的基本要素。算法一般由两种基本要素构成：对数据对象的运算和操作；算法的控制结构，即运算和操作时间的顺序。考核概率为 。该知识点属于熟记 内 容，考 生 要 熟 记 算 法 的 概念，以及时间复杂度和空间复杂度的概念。算法中对

3、数据的运算和操作：算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，其指令系统是有差异的，但一般的计算机系统中都包括的运算和操作有 类，即算术运算、逻辑运算、关系运算和数据传输。算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作，还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。（）算法设计的基本方法。算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度。（）算法的时间

4、复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一般情况下，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量 （）。其中 是问题的规模。这个表达式表示随着问题规模 的增大，算法执行时间的增长率和 （）的增长率相同。在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用两种方法来分析算法的工作量：平均性态分析和最坏情况分析。（）算法的空间复杂度。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括 个部分：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行

5、过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。算法复杂度主要包括时间复杂度和复杂度。【答案】空间【解析】算法的复杂度主要包括时间复杂度和空间复杂度两个方面。所谓算法的时间复杂度，是指执行算法所需要的计算工作量；算法的空间复杂度，是指执行该算法所需要的内存空间的规模。考点 数据结构的基本概念数据结构的定义数据结构是指相互有关联的数据元素的集合，即数据的组织形式。（）数据的逻辑结构。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前、后件关系）的数据结构。它包括数据元素的集合和数据元素之间的关系。（）数据的存储结构。数据的逻辑结构在计算机存储空间中

6、的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的存储方式有顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。数据结构研究的内容主要包括 个方面：数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；在笔 试 中，考 核 概 率 。该知识点属于熟记内容，熟记数据结构的定义、分类，能区分线性结构与非线性结构。在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。数据结构的图形表示数据元素之间最基本的关系是前、后件关系。前、后件关系，即

7、每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据结点，简称为结点。对于每一个二元组，用一条有向线段从前件指向后件。用图形表示数据结构具有直观易懂的特点，在不引起歧义的情况下，前件结点到后件结点连线上的箭头可以省去。例如，树形结构中，通常是用无向线段来表示前、后件关系的。线性结构与非线性结构根据数据结构中各数据元素之间前、后关系的复杂程度，一般将数据结构分为两大类型，即线性结构和非线性结构。如果一个非空的数据结构满足有且只有一个根结点，并且每个结点最多有一个直接前驱或直接后继，则称该数据结构为线性结构，又称线性表。不满足上述条件的数据结构称为非线性结构。小提示

8、需要注意的是，在一个线性结构中插入或删除任何一个结点后还应该是线性结构；否则，不能称之为线性结构。【例 】下列叙述中正确的是（）。程序执行的效率与数据的存储结构密切相关程序执行的效率只取决于程序的控制结构程序执行的效率只取决于所处理的数据量以上 种说法都不对【答案】【解析】在计算机中，数据的存储结构对数据的执行效率有较大影响，如在有序存储的表中查找某个数值比在无序存储的表中查找的效率高很多。【例 】数据结构分为线性结构和非线性结构，带链的队列属于结构。【答案】线性【解析】与栈类似，队列也是线性表，可以采用链式存储结构，所以带链的队列属于线性结构。考点 线性表及其顺序存储结构线性表的基本概念在数

9、据结构中，线性结构也被称为线性表，线性表是最简单也是最常用的一种数据结构。线性表是由 （）个数据元素 ，组成的一个有限序列，除表中的第一个元素外，其他元素有且只有一个前件，除了最后一个元素外，其他元素有且只有一个后件。线性表要么是个空表，要么可以表示为（，）其中 （，）是线性表的数据元素，也称为线性表的一个结点。考核概率为 。该知识点属于了解性内容，考生需要了解线性表的基本概念。每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个字符，也可以是一个具体的事物，甚至其他更复杂的信息。但是需要注意的是，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。小提示非空线性表具有

10、以下一些结构特征：有且只有一个根结点，即头结点，它无前件；有且只有一个终结点，即尾结点，它无后件；除头结点与尾结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数 称为线性表的长度，当 时，称为空表。线性表的顺序存储结构将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序表示的线性表也称为顺序表。线性表的顺序存储结构具有以下两个基本特点：元素所占的存储空间必须是连续的；元素在存储空间的位置是按逻辑顺序存放的。从这两个特点也可以看出，线性表是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。

11、线性表的插入运算在线性表的插入运算中，在第 个元素之前插入一个新元素，完成插入操作主要有以下 个步骤：（）把原来第 个结点至第 个结点依次往后移一个元素位置；（）把新结点放在第 个位置上；（）修正线性表的结点个数。小提示一般会为线性表开辟一个大于线性表长度的存储空间，经过多次插入运算，可能出现存储空间已满的情况，如果此时仍继续做插入运算，将会产生错误，此类错误称为“上溢”。如果需要在线性表末尾进行插入运算，则只需要在表的末尾增加一个元素即可，不需要移动线性表中的元素。如果在第一个位置插入新的元素，则需要移动表中的所有数据。线性表的删除运算在线性表的删除运算中，删除第 个位置的元素，则要从第 个

12、元素开始直到第 个元素之间，共 个元素依次向前移一个位置。完成删除运算主要有以下几个步骤：（）把第 个元素之后（不包括第 个元素）的 个元素依次前移一个位置；（）修正线性表的结点个数。显然，如果删除运算在线性表的末尾进行，即删除第 个元素，则不需要移动线性表中的元素。如果要删除第 个元素，则需要移动表中的所有数据。小提示由线性表的以上性质可以看出，线性表的顺序存储结构适合用于小线性表或者建立之后其中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。【例 】下列有关顺序存储结构的叙述，不正确的是（）。存储密度大逻辑上相邻的结点物理上不必邻接可以通过计算机直接

13、确定第 个结点的存储地址插入、删除操作不方便【答案】【解析】顺序存储结构要求逻辑上相邻的元素物理上也相邻，所以只有选项 叙述错误。【例 】在一个长度为 的顺序表中，向第 个元素（）位置插入一个新元素时，需要从后向前依次移动（）个元素。【答案】【解析】根据顺序表的插入运算的定义知道，在第 个位置上插入 ，从 到 都要向后移动一个位置，共需要移动个元素。考点 栈和队列栈及其基本运算（）栈的基本概念。栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。在栈中，允许插入与删除的一端称为栈顶（），另一端称为栈底（）。当栈中没有元素时称为空栈，栈也被

14、称为“先进后出”表，或“后进先出”表。（）栈的特点。根据栈的上述定义，可知栈具有以下特点：栈顶元素总是最后被插入的元素，也是最早被删除的元素；栈底元素总是最早被插入的元素，也是最晚才能被删除的元素；栈具有记忆功能；在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他数据元素；栈顶指针 动态反映了栈中元素的变化情况。（）栈的顺序存储及其运算。栈的状态如图 所示。top考核概率为 ，属于必考知识点，该知识点较为基础，考生要理解栈和队列的概念和特点，掌握栈和队列的运算。FEDCtopbotom栈空topbotomA正常botomBA栈满根据栈的状态，可以得知栈的基本运算有 种。入栈运算：在栈顶位

15、置插入一个新元素。图 栈的状态退栈运算：取出栈顶元素并赋给一个指定的变量。读栈顶元素：将栈顶元素赋给一个指定的变量。队列及其基本运算（）队列的基本概念。队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（）的指针指向队尾元素；允许删除的一端称为队头，通常用一个头指针（）指向头元素的前一个位置。因此，队列又称为“先进先出”（，）的线性表。插入元素称为入队运算，删除元素称为退队运算。队列的基本结构如图 所示。图 队列（）循环队列及其运算。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中

16、，用尾指针指向队列的尾元素，用头指针指向头元素的前一个位置，因此，从头指针指向的后一个位置直到尾指针指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即 。循环队列的基本运算主要有两种：入队运算与退队运算。入队运算是指在循环队列的队尾加入一个新的元素。退队运算是指在循环队列的队头位置退出一个元素，并赋给指定的变量。小提示栈是按照“先进后出”或“后进先出”的原则组织数据，而队列是按照“先进先出”或“后进后出”的原则组织数据。这就是栈和队列的不同点。【例 】下列对队列的叙述，正确的是（）。队列属于非线性表队列在队尾删除数据【答案】队列按“先进后出”原则组织数据队列按“先进先出”原则

17、组织数据【解析】队列是一种特殊的线性表，它只能在一端进行插入，在另一端进行删除。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为“先进先出”或“后进后出”的线性表，体现了“先到先服务”的原则。【例 】下列关于栈的描述，正确的是（）。在栈中只能插入元素而不能删除元素在栈中只能删除元素而不能插入元素栈是特殊的线性表，只能在一端插入或删除元素栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素【答案】【解析】栈是一种特殊的线性表。在这种特殊的线性表中，其插入和删除操作只在线性表的一端进行。考点 线性链表线性链表的基本概念线性表的链式存储结构称为线性链表。为了存储线链性表中的每一个元素，

18、一方面要存储数据元素的值；另一方面要存储各数据元素之间的前、后件关系。为此，在链式存储结构中，每个结点由两部分组成：一部分称为数据域，用于存放数据元素值；另一部分称为指针域，用于存放下一个数据元素的存储序号，即指向后件结点。链式存储结构既可以表示线性结构，也可以表示非线性结构。考核概 率 为 ，该 知 识 点 属于熟记性内容，考生主要熟记线性链表的概 念 和 特 点、顺 序 表 和 链 表 的优、缺点等。线性表链式存储结构的特点是：用一组不连续的存储单元存储线性表中的各个元素。因为存储单元不连续，数据元素之间的逻辑关系，就不能依靠数据元素的存储单元之间的物理关系来表示。线性链表的基本运算线性链

19、表主要包括以下几种运算：在线性链表中包含指定元素的结点之前插入一个新元素；在线性链表中删除包含指定元素的结点；将两个线性链表按要求合并成一个线性链表；将一个线性链表按要求进行分解；逆转线性链表；复制线性链表；线性链表的排序；线性链表的查找。循环链表及其基本运算（）循环链表的定义。在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，在最后一个结点的指针域的值由 改为指向表头结点，这样的链表称为循环链表。在循环链表中，所有结点的指针构成了一个环状链。（）循环链表与单链表的比较。对单链表的访问是一种顺序访问，从其中某一个结点出发，只能找到它的直接后继，但无法找到它的直接前驱，而且对于空表和

20、第一个结点的处理必须单独考虑，空表与非空表的操作不统一。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。并且，由于表头结点是循环链表所固有的结点，因此，即使在表中没有数据元素的情况下，表中也至少有一个结点存在，从而使空表和非空表的运算统一。下列叙述中，正确的是（）。线性链表是线性表的链式存储结构双向链表是非线性结构【答案】栈与队列是非线性结构只有根结点的二叉树是线性结构【解析】根据数据结构中各数据元素之间前后关系的复杂程度，可将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每个结点最多有一个前驱，也

21、最多有一个后继。则称该数据结构为线性结构，也叫做线性表。若不满足上述条件，则称之为非线性结构。线性表、栈、队列和线性链表都是线性结构，而二叉树是非线性结构。考点 树和二叉树树的基本概念树是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。树是由 （）个结点构成的有限集合，的树称为空树；当 时，树中的结点应该满足以下两个条件：有且仅有一个没有前驱的结点称之为根；其余结点分成 （）个互不相交的有限集合 ，其中每一个集合又都是一棵树，称 ，为根结点的子树。在树的结构中主要涉及下面几个概念：每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根；每一个结点

22、可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点；一个结点所拥有的后继个数称为该结点的度；所有结点最大的度称为树的度；考核概率为 ，本节属于必考知识 点，特 别 是 关 于 二 叉 树 的 遍历，该知 识 点 属 于 熟 记 和 掌 握 性 内容，考生要熟记二叉树的概念及其相关术语，掌握二叉树的性质以及二叉树的 种遍历方法，本知识点是数据结构的重要组成部分。树的最大层次称为树的深度。二叉树及其基本性质（）二叉树的定义。二叉树是一种非线性结构，是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。当集合为空时，称该二叉树为空二叉树。二叉树具有

23、以下特点：二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。（）满二叉树和完全二叉树。满二叉树：除最后一层外，每一层上的所有结点都有两个子结点，即在满二叉树的第 层上有 个结点，且深度为 的满二叉树中有 个结点。完全二叉树：除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。满二叉树与完全二叉树的关系：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。（）二叉树的主要性质。一棵非空二叉树的第 层上最多有 个结点（）。深度为 的满二叉树中有 个结点。对任何一棵二叉树，度为 的结点（即叶子结

24、点）总是比度为 的结点多一个。具有 个结点的完全二叉树的深度 为。二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由数据域和指针域组成。由于每一个元素可以有两个后件（即两个子结点），所以用于存储二叉树的存储结点的指针域有两个：一个指向该结点的左子结点的存储地址，称为左指针域；另一个指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。对于满二叉树与完全二叉树可以按层次进行顺序存储。二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历主要是针对非空二叉树的，对于空二叉树，则结束遍历并返回。二叉树的遍历有

25、前序遍历、中序遍历和后序遍历。（）前序遍序（）。首先访问根结点，然后遍历左子树，最后遍历右子树。（）中序遍历（）。首先遍历左子树，然后访问根结点，最后遍历右子树。（）后序遍历（）。首先遍历左子树，然后遍历右子树，最后访问根结点。小提示已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一地确定这棵二叉树。已知一棵二叉树的后序遍历序列和中序遍历序列，也可以唯一地确定这棵二叉树。已知一棵二叉树的前序遍历序列和后序遍历序列，不能唯一地确定这棵二叉树。【例 】对如右图所示二叉树进行后序遍历的结果为（）。【答案】【解析】执行后序遍历，依次执行以下操作：首先按照后序遍历的顺序遍历根结点的左子树；然后按照后序

26、遍历的顺序遍历根结点的右子树；最后访问根结点。DBEAFC【例 】在深度为 的满二叉树中，度为 的结点个数为。【答案】【解析】第 层的叶子结点数为 。由二叉树的性质可知，在任意一棵二叉树中，度为 的结点（即叶子结点）总是比度为 的结点多一个，可得本题中度为 的结点数为 个。考点 查找技术顺序查找顺序查找一般是指在线性表中查找指定的元素。其基本思路是：从表中的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，直到两者相符，查到所要找的元素为止；否则，表中没有要找的元素，查找不成功。在最好的情况下，第一个元素就是要查找的元素，则比较次数为 次。在最坏的情况下，顺序查找需要比较 次。在平均情

27、况下，需要比较 次。因此，查找算法的时间复杂度为 （）。在下列两种情况下只能够采取顺序查找：如果线性表中元素的排列是无序的，则无论是顺序存储结构还是链式存储结构，都只能采用顺序查找；即便是有序线性表，若采用链式存储结构，则只能进行顺序查找。二分查找使用二分查找的线性表必须满足两个条件：顺序存储结构；线性表是有序表。考核概 率 为 ，该 知 识 点 属于理解性内容，考生要理解顺序查找与二分查找的概念以及一些查找的方法。所谓有序表，是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。对于长度为 的有序线性表，利用二分查找元素 的过程如下：（）将 与线性表的中间项进行比较；（）若中

28、间项的值等于 ，则查找成功，结束查找；（）若 小于中间项的值，则在线性表的前半部分以二分法继续查找；（）若 大于中间项的值，则在线性表的后半部分以二分法继续查找。这样反复进行查找，直到查找成功或子表长度为 （说明线性表中没有这个元素）为止。当有序线性表为顺序存储时采用二分查找的效率要比顺序查找高得多。对于长度为 的有序线性表，在最坏的情况下，二分查找只需要比较 次，而顺序查找需要比较 次。下列数据结构中，能用二分法进行查找的是（）。顺序存储的有序线性表二叉链表【答案】线性链表有序线性链表【解析】二分查找只适用于顺序存储的有序表。所谓有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻

29、元素值相等）。考点 排序技术交换类排序法交换类排序法是指借助数据元素的“交换”来进行排序的一种方法。这里介绍的冒泡排序法和快速排序法就属于交换类排序法。（）冒泡排序法。冒泡排序的思想如下：在线性表中依次查找相邻的数据元素，将表中最大的元素不断往后移动，反复操作直到消除所有逆序，此时，该表已经排序结束。!*考核概 率 为 ，该 知 识 点 属于掌握性内容，考生要掌握各种排序方法的概念、基本思想及其复杂度。冒泡排序法的基本过程如下：从表头开始往后查找线性表，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，前面的元素大于后面的元素，则将它们交换。从后向前查找剩下的线性表（除去最后一个元素

30、），同样，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，后面的元素小于前面的元素，则将它们交换。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，线性表排序完成。假设线性表的长度为 ，则在最坏的情况下，冒泡排序需要经过 遍的从前往后的扫描和 遍的从后往前扫描，需要比较 （）次，其数量级为 。（）快速排序法。快速排序法的基本思想如下：在线性表中逐个选取元素，将线性表进行分割，直到所有元素全部选取完毕，此时线性表已经排序结束。快速排序法的基本过程如下：从线性表中选取一个元素，设为 ，将线性表后面小于 的元素移动到前面，而将大于 的元素移到后面，这样就将线性表分成了两部分（称为两个

31、子表），就是处于分界线的位置，将线性表分成了前、后两个子表，且前面子表中的所有元素均不大于 ，而后面的子表中的所有元素均不小于 ，此过程称为线性表的分割。对分割后的子表再按上述原则进行反复分割，直到所有子表为空为止，则此时的线性表就变成有序表。插入类排序法插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。这里主要介绍简单插入排序法和希尔排序法。（）简单插入排序法。简单插入排序是把 个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含 个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其

32、后的记录依次向后移动。最后有序表的长度为 ，而无序表为空，此时排序完成。在简单插入排序中，每一次比较后最多移掉一个逆序，因此，该排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插入排序需要 （）次比较。（）希尔排序法。希尔排序法的基本思路为：将整个无序序列分割成若干个小的子序列并分别进行插入排序。分割方法如下：将相隔某个增量 的元素构成一个子序列；在排序过程中，逐次减少这个增量，直到 减少到 时，进行一次插入排序，排序即可完成。希尔排序的效率与所选取的增量序列有关。选择类排序法选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素，按顺序放在已排好序的有序子表的后面，直到全部序列满足

33、排序要求为止。下面就介绍选择类排序法中的简单选择排序法和堆排序法。（）简单选择排序法。简单选择排序的基本思想是：首先从所有 个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的 个元素中选出最小的元素与第二个元素交换。重复这样的操作直到所有的元素有序为止。简单选择排序在最坏情况下需要比较 （）次。（）堆排序法。堆排序的方法如下：将一个无序序列建成堆；将堆顶元素与堆中最后一个元素交换。忽略已经交换到最后的那个元素，考虑前 个元素构成的子序列，只有左、右子树是堆，可以将该子树调整为堆。这样反复下去做第二步，直到剩下的子序列为空时止。在最坏的情况下，堆排序需要比较的次数为 （）。

34、对于长度为 的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是（）。冒泡排序为 快速排序为 【答案】冒泡排序为 快速排序为 （）【解析】假设线性表的长度为 ，则在最坏的情况下，冒泡排序需要经过 遍的从前往后扫描和 遍的从后往前扫描，需要比较次数为 （）。快速排序法在最坏的情况下，比较次数也是 （）为什么只有二叉树的前序遍历和后序遍历不能唯一确定一棵二叉树？在二叉树遍历中前序和后序中都可以确定根结点，但中序是由左至根及右的顺序，所以知道前序（或后序）和中序肯定能唯一确定二叉树；在前序和后序中只能确定根结点而对于左、右子树的结点元素没办法正确选取，所以很难确定一棵二叉树。由此可见，需

35、要确定一棵二叉树的基础是必须得知道中序遍历。程序设计基础考点 程序设计方法与风格程序设计方法程序设计是指设计、编制、调试程序的方法和过程。程序设计方法是研究问题求解如何进行系统构造的软件方法学。常用的程序设计方法有结构化程序设计方法、软件工程方法和面向对象方法。程序设计风格程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。良好的程序设计风格可以使程序结构清晰合理，程序代码便于维护，因此，程序设计风格深深地影响着软件的质量和维护。要形成良好的程序设计风格，主要应注重和考虑的因素有以下几点：源程序文档化；数据说明方法；语句的结构；输入和输出。【例 】下列叙述中，不属于良好程序设计风格要求的

36、是（）。程序的效率第一，清晰第二程序的可读性好考核概 率 为 ，该 知 识 点 属于熟记性内容，考生要熟记程序设计的 种规范及注释的相关概念。程序中要有必要的注释【答案】输入数据前要有提示信息【解析】著名的“清晰第一，效率第二”的论点已经成为主导的程序设计风格，所以选项 是错误的，其余选项都是良好程序设计风格的要求。【例 】下列选项中不符合良好程序设计风格的是（）。源程序要文档化避免滥用 语句【答案】数据说明的次序要规范化模块设计要保证高耦合、高内聚【解析】良好的程序设计风格使程序结构清晰合理，使程序代码便于维护。主要应注意和考虑的因素有：源程序要文档化；数据说明的次序要规范化；语句的结构应简

37、单直接，不应该为提高效率而把语句复杂化，避免滥用 语句；模块设计要保证低耦合、高内聚。考点 结构化程序设计结构化程序设计的原则结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用 语句。（）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑具体问题。（）逐步求精：将复杂问题细化，细分为逐个小问题再依次求解。（）模块化：是把程序要解决的总目标分解为若干目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。（）限制使用 语句。结构化程序设计的基本结构考核概 率 为 ，该 知 识 点 属于熟记性内容，考生要熟记结构化程序设计的 个原则以及结构化程序的基

38、本结构的 种类型。结构化程序设计有 种基本结构，即顺序结构、选择结构和循环结构，其基本形式如图 所示。假真假真AAB(a)顺序结构AB(b)选择结构A(c)当型循环结构真假(d)直到型循环结构图 结构化程序设计的基本结构结构化程序设计的原则和方法的应用结构化程序设计是一种面向过程的程序设计方法。在结构化程序设计的具体实施中，需要注意以下问题：使用程序设计语言的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；选用的控制结构只准许有一个入口和一个出口；程序语句组成容易识别的块，每块只有一个入口和一个出口；复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现；语言中所没有的控制结构，应该采用前后

39、一致的方法来模拟；严格控制 语句的使用。下列选项中不属于结构化程序设计方法的是（）。自顶向下【答案】逐步求精模块化可复用【解析】世纪 年代以来，提出了许多软件设计方法，主要包括：逐步求精，对复杂的问题，应设计一些子目标作过渡，逐步细化。自顶向下，程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。一开始不要过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。模块化，一个复杂问题，肯定是由若干相对简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。而可复用是面向对象程序设计的一个优点，不是结构化程序设计方法。考点

40、 面向对象的程序设计面向对象方法的本质面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。面向对象方法的优点与人类习惯的思维方法一致。稳定性好。可重用性好。易于开发大型软件产品。可维护性好。面向对象方法的基本概念（）对象。考核概 率 为 ，该 知 识 点 属于熟记性内容，考生要熟记对象、类、实例、消息、继承、多态性的概念。对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中任何实体，它既可以是具体的物理实体的抽象，也可以是人为概念，或者是任何有明确边界和意义的东西。（）类。类是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象