国家计算机二级应试策略.docx

《国家计算机二级应试策略.docx》由会员分享，可在线阅读，更多相关《国家计算机二级应试策略.docx（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、应试策略（-）笔试应试策略考生在全面复习，掌握知识重点的基础上，运用一些答题技巧，可以提高答题速度， 争取较好的成绩。I、选择题的应试策略选择题为四选一的单向选择题。在答题过程中对于不能马上得到正确答案的情况，可以 用排除法先将明显错误（或正确）的选项排除，再对剩余的选项仔细推敲，逐步趋进。对某 个题目一无所知时，也别放弃选择，在选项中随机选择一个，也有得分的机会。2、填空题的答题策略对于填空题，有时可能有不止一个正确答案，只要选择了其中一个作答，就认为是正确 的。在答题时，对于知识掌握较清楚的题目要保证一次答对，不要依赖于反复验证，毕竟时 间有限。切记不要在个别拿不准的题目上花费太多的时间，

2、因为每空只占1、2分，有时甚 至要以放弃，以免影响整个考试的进度。在时间允许的情况下，再考虑做答这些题目。（二）机试应试策略上机考试主要考查考生编写程序和调试程序等实际操作能力。因此在平时的学习中既要注意 理论的学习，也要重视上机操作能力的培养。只要考生熟练掌握了 C语言程序设计的基本 技术、程序编辑、编译工具和程序调试技巧，要顺利通过上机考试并不是难事。1、程序填空题的应试策略上机考试的题目的难度是由浅入深，填空题主要考查考生对C语言基础知识的掌握情况 和阅读程序的能力。程序并不复杂，只要考生掌握了 C语言的语法规则，理解了题目的要 求，掌握了程序的算法，就可以较容易的将程序补充完整。在一些

3、情况下，结合填空位置的 上下语句来猜测需要补充的语句的功能，可以节省一些时间。2、改错题的应试策略改错题的难度就增加了一些，在没有提示的情况下，要求考生自己发现并改正错误。其 实也是要求考生熟练掌握C语言的语法规则，理解程序的思路和算法。对于一些简单的语法和逻辑错误可以通过仔细阅读程序找到。对于一时不能发现的错误，还可以使用C语言编译器的编译命令来帮助发现错误，根据它 的错误提示信息找到错误所在。一些语法错误，是可以通过编译的，编译器不会提示错误，这就要求考生做题时认真细致并 运用一些调试技巧来发现错误。3、编程题的应试策略编程题对考生能力的要求就更高了，考生应当注意：先仔细阅读题目，了解题目

4、要求，以及已给出的函数对要编写的函数起了哪些作用，应避免 在不明题意的情况下盲目答题。不要急于编程。要理清思路，可以先将复杂的任务逐层分解，要看题目用到了 C语言中的 哪些数据类型，还要看运用了哪些结构。在编写程序的过程中要严格遵守C语言的语法规 则，避免犯一些常见的语法错误。在程序编写完成后，要经过调试后再运行，避免一些隐性的逻辑错误导致计算机死机，影 响考试。要顺利完成编程题，考生应注意在平时多学习和积累些典型的例子和算法。第一部分基础知识本部分是考试的基础，所占分值比例较大，而且该章的试题比较灵活，因此在学习本章 时，要以理解为主，切忌死记硬背，在学习过程中，要注意各个知识点之间的联系和

5、区别， 将盘根错节的知识点理顺成知识网络。具体知识点总结如下： 一、算法该知识点在试卷中一般有12道题，考生要了解算法的定义、特征、组成要素、常用 算法和算法更杂度，其中算法更杂度是考试重点，与之有密切联系的是：查找技术（第一章 第7节）和排序技术（第一章第8节），考生最后复习时，要牢记六种排序方法的时间复杂 度和两种查找方法的特点及最好/最坏/平均查找次数。二、数据结构该知识点在试卷中一般有24道题，是本章的重点和难点，考题中所涉及的考点一般 并不是教材上的直接知识点，因此在学习过程中，要以是否提高了数据处理的效率（速度/ 空间）为主线，对每种逻辑结构和其对应的不同存储结构进行分析、比较和总

6、结。三、线性结构：线性表、栈和队列、非线性结构：树该知识点是必考的知识点，在学习过程中，要深刻理解和掌握栈和队列的特点（包括逻 辑结构特点和不同的存储结构的特点）以及进栈、退栈和入队、退队时指针的变化，对于二 叉树的性质和遍历规则要牢记并灵活运用。 四、程序设计基础考点包括：面向过程的程序设计方法和面向对象的程序设计方法。前者主要了解其设计 原则，后者是本章重点，要理解并掌握一些基本概念和术语，例如时象（类的实例）及其特 点、属性、方法、事件、消息、类（对象的抽象）、封装、继承、多态等。五、软件工程基础掌握软件工程中的一些基本概念，例如：软件的定义、特点和分类；软件危机的表现； 软件工程的定义

7、、要素、核心思想、原则和目标。然后以软件生命周期为主线，重点掌握每 个阶段（需求分析、总体设计、详细设计、测试和调试）的主要任务、方法和常用工具，该 知识点是本章的重点，建议以表格的形式进行归纳和总结，以明确各个知识点的联系，以有 助于记忆。在归纳总结过程中，要注意以下知识点的区别，例如：测试（发现错误；本阶段 涵盖整个软件生命周期的过程）、调试（诊断并改正程序中的错误，主要在开发阶段）的区 别；白盒测试（内部的结构测试）和黑盒测试（外部接口的功能测试）的区别；每个阶段所 用到的工具（DFD、DD、SC、PFD、N-S等）的区别。六、数据库设计基础主要知识点有数据库系统组成、发展、特点、内部体

8、系结构；数据模型；实体联系模型; 关系模型、关系运算和数据库设计与管理，其中数据库系统、关系模型和关系运算是考试重 点。第一章数据结构与算法1.1算法知识点1算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就 是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的 设计。算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序 将在有限的次数下终止。所以其四个基本特征包括：(1)确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多 义性；(2)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止

9、；(3)可行性，算法原则上能够精确地执行；(4)拥有足够的情报，算法要有一定的输入数据和必须要仃的输出结果。算法的基本要素包括：一是对数据对象的运算和操作；二是算法的控制结构。基本运 算和操作包括：算术运算、逻辑运算、关系运算、数据传输；算法的三种基本控制结构：顺 序结构、选择结构、循环结构。知识点2算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。知识点3算法效率的度量一算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复 杂度：指执行算法所需耍的计算工作量。即算法执行过程中所需要的基本运算次数。通常， 一个算法所用的时间包括编译时间和运行时间。算法空间复杂度：指执行这个

10、算法所需要的 内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的 额外空间。知识点4指令系统：一个计算机系统能执行的所有指令的集合。1.2数据结构基础知识点1数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查 找、更改等运算，也包括对数据元素进行分析。知识点2数据结构：指相互有关联的数据元素的集合。数据结构研究的三个方面：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构：(2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(3)对各种数据结构进行的运算。知识点3数据的逻辑结构应包含：(1)表示数据元素的信

11、息；(2)表示各数据元素之间的前后件关系(指逻辑关系，与存储位置无关)。即一个数据结构 可以表示成B=(D, R)其中B表示数据结构。为了反映D中各数据元素之间的前后件关系， 一般用二元组来表示。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据物理结 构。数据的存储结构有顺序、链接、索引等。一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表 示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数 据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的 每一个二元组，用一条有向线段从前件结点指向后件结

12、点。例如，一年四季的数据结构可以 用如图1.1所示的图形来表示。又如，反映家庭成员间辈分关系的数据结构可以用如图1.2 所示的图形表示。图1一年四季数据结构的图形表示图1.2家庭成员间辈分关系数据结构的图形表示根据数据结构中各数据元素之间前后件关系的夏杂程度，一般将数据结构分为两大类型：线 性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表1.3线性表及顺序存储结构知识点1线性表是由n(n，O)个数据元素a” a?,，a。组成的一个有限序列，表中的每一 个数据元素，除了第一个外

13、，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(a”a2,a,a.，其中aj(i=k 2, , n)是属于数据时象的元素，通常也称其为线性表中的一个结点。显然，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号， 即数据元素之间的相对位置是线性的。知识点2非空线性表有如下一些结构特征：有且只有一个根结点a“它无前件；有且只有一个终端结点an,它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线 性表中结点的个数n称为线性表的长度。当n=0时，称为空表。知识点3线性表由一组数据元素构成。数据元素的含义很广

14、泛，在不同的具体情况下，它 可以有不同的含义。例如，一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表， 其中的每一个季节名就是一个数据元素。数据元素的位置只取决于自己的序号，元素之间的 相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录：由多个 记录构成的线性表称为文件。知识点4线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。元素ai的存储地址为： ADR(ai)=ADR(al)+(i-l)k, ADR(al)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运

15、算：查找、插入、删除。1.4线性链表线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占 若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据 元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用 于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储 结点的地址），即指向后件结点，称为指针域。由此可知，在线性链表中，存储空间的结构 如图1.3所示。存储序号数据域指斜域图1.3线性链表存储结构在线性链表中，用一个专门的指针H

16、EAD指向线性链表中第一个数据元素的结点（即存 放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此， 线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。线性链表的逻 辑结构如图1.4所示。存储序号 数-域,指计域.i Vl,则该结点的父结点编号为INT(k/2)： 若2kn,则k结点的左子结点编号为2k；否则该结点无左子结点(也无右子结点)； 若2k+lWn,则编号为k的结点的右子结点编号为2k+l；否则该结点无右子结点。满二叉树与完全二叉树是两种特殊形态的二叉树。(1)满二叉树所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点

17、都有两个子 结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k 层上有21个结点，且深度为m的满二叉树有2m-l个结点。(2)完全二叉树所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值； 在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用臼然数进行连续 编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-l个结点 深度为m的满二叉树有2m-l个

18、结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边 的若干结点。由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一 般不是满二叉树。完全二叉树还具有以下两个性质：性质5具有n个结点的完全二叉树的深度为10g2n+l。性质6设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自 然数1, 2,，n给结点进行编号，则对于编号为k(k=l, 2,n)的结点有以下结论：若k=l,则该结点为根结点，它没有父结点；若kl,则该结点的父结点编号为INT(k/2)。若2kWn,则编号为k的结点的左子结点编号为2k；否则该结点无左子

19、结点(显然也 没有右子结点)。若2k+lWn,则编号为k的结点的右子结点编号为2k+l：否则该结点无右子结点。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点， 则很容易确定每一个结点的父结点、左子结点和右子结点的位置。补充：增加度为1的结点不会影响二叉树的叶子结点数，每增加一个度为2的结点便会增加 一个叶子结点，没有度为2的结点时叶子结点数为1。已知完全二叉树有x个结点，求其叶子结点数：确定层数为k； 第k层的结点数y=x-(2k-l-l)；第k-1层的叶子结点数n=2(k-l)-l-y/2(若y/2有余，则要加1；最后y+n。L(i)V(i)R(i)Lehi I

20、dValue Rchild图1.8二叉树存储结点的结构二叉树通常采用链式存储结构各元素的存储结点由两部分组成：数据域与指针域。但在 二叉树中，由于每一个元素可以有两个后件(即两个子结点)，因此，用于存储二叉树的存储 结点的指针域有两个：一个用于指向该结点的左 子结点的存储地址，称为左指针域；另一个用于 指向该结点的右子结点的存储地址，称为右指针 i 域 图1.8为二叉树存储结点的示意图。其中：L(i) 为结点i的左指针域，即L(i)为结点i的左予结点的存储地址；R为结点i的右指针域，即R(i)为结点i的右子结点的存储地址；V为数据 域。由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二

21、叉树的链式存储结构 也称为二叉链表。图1.9(a)、(b)分别表示了一棵二叉树、二叉链表的逻辑状态。其中BT 称为二叉链表的头指针，用于指向二叉树根结点(即存放二叉树根结点的存储地址)。(a)二又利(b).义里表的浅辑状态图1.9二叉树和二叉链表二叉树的遍历是指不重复地访问二叉树中的所有结点。所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，苜先访问根结点， 然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后 遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。如果对图1.9（a）中的二叉树进行前序遍历，则遍历的结果为F, C, A

22、, D, B, E, G, H, P（称为该二叉树的前序序列）。所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树, 然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后 访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。如果对图1.9（a）中的二叉树进行中序遍历，则遍历结果为A, C, B, D, F, E, H, G, P（称为该二叉树的中序序列）。所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然 后遍历右子树，最后访问根结点，.并且，在遍历左、右子树时，仍然先遍历左子树，然后 遍

23、历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。如果对图1.9（a）中的二叉树进行后序遍历，则遍历结果为A, B, D, C, H, P, G, E, F（称为该二叉树的后序序列）。1.7 查找查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构， 通常有二种不同的查找方法。顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如 下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表 示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示 线性表中没有要找的元素（即查找失败

24、）。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非 递减排列（即从小到大，但允许相邻元素值相等）。设有序线性表的长度为n,被查元素为x,则对分查找的方法如下：将x与线性表的中间项进行比较：若中间项的值等于x,则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行 查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行 查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序 查找高得多。可以

25、证明，对于长度为n的有序线陛表，在最坏情况下，二分查找只需要比较 log2n次，而顺序查找需要比较n次。1.8 排序排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。一、交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快 速排序法都属于交换类的排序方法。(1)冒泡排序法，首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两 个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消 去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线 性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。然后，

26、从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。 若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。 显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最 小者换到了表的最前面，这也是线性表中最小元素应有的位置。假设线性表的长度为n,则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和 n/2遍的从后往前的扫描，需要的比较次数为n(n-l)/2。需要比较的次数为n(n-l)/2；(2)快速排序法。快速排序法的基本思想如下：从线性表中选取一个元素，设为T,将线性表后面小于T的元素移到前面，而前面大于 T的元

27、素移到后面，结果就将线性表分成了两部分(称为两个子表)，T插入到其分界线的位 置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性 表分成了前后两个子表，且前面子表中的所有元素均不大于T,而后面子表中的所有元素均 不小于T。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去， 直到所有子表为空为止，则此时的线性表就变成了有序表。由此可知，快速排序法的关键是对线性表进行分割，以及对各分割出的子表再进行分割， 这个过程如图1.10所示。在对线性表或子表进行实际分割时，可以按如下步骤进行：分割分割首先，在表的第一个、中间一个与最后一个元素中选取中项，

28、设为P(k),并将P(k)赋给 T,再将表中的第一个元素移到P(k)的位置上。然后设置两个指针i和j分别指向表的起始与 最后的位置。反复操作以下两步：(1)将j逐渐减小，并逐次比较P(j)与T,直到 发现一个P(j)T为止，将P移到P(j)的位置I二。上述两个操作交替进行，直到指针i与j指向同一个位置(即i=j)为止，此时将T移到P的位置上。二、插入类排序法是指将无序序列中的各元素依次插入到已经有序的线性表中。(1)简单插入排序法从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个 元素插入到前面已经有序的子表中。一般来说，假设线性表中前j-1个元素已经有序，现在 要将线性表中第j个元

29、素插入到前面的有序子表中，插入过程如下：首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素(即线性表中第 j-1个元素)开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到 发现一个元素不大于T为止，此时就将T(即原线性表中的第j个元素)插入到刚移出的空位 置上，有序子表的长度就变为j 了。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与 冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-l)/2次比较。(2)希尔排序法的基本思想如下：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量h的元素构

30、成一个子序列。在排序过程中，逐次减小这个增量，最后当 h减到1时，进行一次插入排序，排序就完成。增量序列一般取h,=n/2k(k=l, 2,log2n).其中n为待排序序列的长度。希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下， 希尔排序所需要的比较次数为OS”)。三、选择类排序法(1)选择排序法的基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)； 然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最 小的元素，然后将该最小的元素与子表中的第一个元素进

31、行交换。图1.40是这种排序法的 示意图，图中有方框的元素是刚被选出来的最小元素。最坏情况需要n(n-l)/2次比较； (2)堆排序法堆的定义如下：具有n个元素的序列(hi，th，hj,当且仅当满足% 2 % hi 2 h2M% = h2i% 4 h2i(i=l, 2,，n/2)时称之为堆。本节只讨论满足前者条件的堆。图1.11堆顶元素为最大的堆由堆的定义可以看出，堆顶元素(即第一个元素)必 为最大项。在实际处理中，可以用一维数组H(l： n)来存储堆 序列中的元素，也可以用完全二叉树来宜观地表示堆的 结构。例如，序列(91, 85, 53, 36, 47, 30, 24, 12) 是一个堆，

32、它所对应的完全二叉树如图1.41所示。由图 1.11可以看出，在用完全二叉树表示堆时，树中所有非 叶子结点值均不小于其左、右子树的根结点值，因此， 堆顶(完全二叉树的根结点)元素必为序列的n个元素中 的最大项。在具体讨论堆排序法之前，先讨论这样一个问题： 在一棵具有n个结点的完全二叉树用一维数组H(l： n) 表示中，假设结点H(m)的左右子树均为堆，现要将以 H(m)为根结点的子树也调整为堆。这是调整建堆的问 题。例如，假设图1.12(a)是某完全二叉树的一棵子树。显然，在这棵子树中，根结点47的 左、右子树均为堆。现在为了将整个子树调整为堆，首先将根结点47与其左、右子树的根 结点值进行比

33、较，此时由于左子树根结点91大于右子树根结点53,且它又大于根结点47, 因此，根据堆的条件，应将元素47与91交换，如图1.42(b)所示。经过这一次交换后，破 坏了原来左子树的堆结构，需要对左子树再进行调整，将元素85与47进行交换，调整后的 结果如图1.12(c)所示。由这个例子可以看出，在调整建堆的过程中，总是将根结点值与左、右子树的根结点值 进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这 个调整过程一直做到所有子树均为堆为止。有了调整建堆的算法后，就可以将一个无序序列建成为堆。假设无序序列H（l： n）以完全二叉树表示。从完全二叉树的最后一个非叶子结

34、点（即第 n/2个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆，最后就可 以得到与该序列对应的堆。根据堆的定义，可以得到堆排序的方法如下：（1）首先将一个无序序列建成堆。（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最 后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序 列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（2）步，直到剩下 的子序列为空为止。堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效 的。在最坏情况下，堆排序需要比较的次数为O（nlog2n）

35、。相比以上儿种（除希尔排序法外），堆排序法的时间复杂度最小。1.9 练习题一、选择题：1 .下列数据结构中，能用二分法进行查找的是（）A）顺序存储的有序线性表B）线性链表 C）二叉链表 D）有序线性链表2 .下列关于栈的描述正确的是（）A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表,只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素,而在另一端删除元素3 .下列叙述中正确的是（）A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C） 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据

36、处理的效率D） 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率4 .数据的存储结构是指（）A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构中计算机中的表示5 .下列关于栈的描述中错误的是（）A）栈是先进后出的线性表 B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针6 .对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为n（n-l）/27 .对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数

37、为（）A） log2nB） n/2C） nD） n+18 .下列对于线性链表的描述中正确的是（）A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的9 .算法的时间复杂度是指（）A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数10 .算法的空间复杂度是指（）A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）算法执行过程中所需要的存储空间11 .下列叙述

38、中正确的是（）A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D）二叉树是线性结构12 .数据的存储结构是指（）A）数据所占的存储空间量B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据13 .下列关于队列的叙述中正确的是（）A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表14 .下列关于栈的叙述中正确的是（）A）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是先进后出的线性表ABC15 .设有下列二叉树：对此二叉树中遍历的结果为（）A）ABCDEF B）DBE

39、AFC C）ABDECF D）DEBFCA16 .在深度为5的满二叉树中，叶子结点的个数为（）A）32B）31C）16D）1517 .对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数为（）A）n+1 B）n C） （n+1 ）/2 D） n/218 .喇 T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点数为（）A）8B）7C）6D）519 .下列叙述中，错误的是（）A）数据的存储结构与数据处理的效率密切相关。B）数据的存储结构数据处理的效率无关。C）数据的存储结构在计算机中所占的空间不一定是连接的。D）一种数据的逻辑结构可以有多种存储结构。20 .下列叙述中，正确的是（）A）线性链表中的各元素在存储空间中的位