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

应试策略（-）笔试应试策略考生在全面复习，掌握知识重点的基础上，运用一些答题技巧，可以提高答题速度，争取较好的成绩。1、选择题的应试策略选择题为四选一的单向选择题。在答题过程中对于不能马上得到正确答案的情况，可以用排除法先将明显错误（或正确）的选项排除，再对剩余的选项仔细推敲，逐步趋进。对某个题目一无所知时，也别放弃选择，在选项中随机选择一个，也有得分的机会。2、填空题的答题策略对于填空题，有时可能有不止一个正确答案，只要选择了其中一个作答，就认为是正确的。在答题时，对于知识掌握较清楚的题目要保证一次答对，不要依赖于反复验证，毕竟时间有限。切记不要在个别拿不准的题目上花费太多的时间，因为每空只占1、2 分，有时甚至要以放弃，以免影响整个考试的进度。在时间允许的情况下，再考虑做答这些题目。（二）机试应试策略匕机考试主要考查考生编写程序和调试程序等实际操作能力。因此在平时的学习中既要注意理论的学习，也要重视上机操作能力的培养。只要考生熟练掌握了 C 语言程序设计的基本技术、程序编辑、编译工具和程序调试技巧，要顺利通过上机考试并不是难事。1、程序填空题的应试策略上机考试的题目的难度是由浅入深，填空题主要考查考生对C 语言基础知识的掌握情况和阅读程序的能力。程序并不复杂，只要考生掌握了 C 语言的语法规则，理解了题目的要求，掌握了程序的算法，就可以较容易的将程序补充完整。在一些情况下，结合填空位置的上下语句来猜测需要补充的语句的功能，可以节省一些时间。2、改错题的应试策略改错题的难度就增加了一些，在没有提示的情况下，要求考生自己发现并改正错误。其实也是要求考生熟练掌握C 语言的语法规则，理解程序的思路和算法。对于一些简单的语法和逻辑错误可以通过仔细阅读程序找到。对于时不能发现的错误，还可以使用C 语言编译器的编译命令来帮助发现错误，根据它的错误提示信息找到错误所在。一些语法错误，是可以通过编译的，编译器不会提示错误，这就要求考生做题时认真细致并运用一些调试技巧来发现错误。3、编程题的应试策略编程题对考生能力的要求就更高了，考生应当注意：先仔细阅读题目，了解题目要求，以及已给出的函数对要编写的函数起了哪些作用，应避免在不明题意的情况下盲目答题。不要急于编程。要理清思路，可以先将复杂的任务逐层分解，要看题目用到了 C 语言中的哪些数据类型，还要看运用了哪些结构。在编写程序的过程中要严格遵守C 语言的语法规则，避免犯一些常见的语法错误。在程序编写完成后，要经过调试后再运行，避免一些隐性的逻辑错误导致计算机死机，影响考试。要顺利完成编程题，考生应注意在平时多学习和积累些典型的例子和算法。第一部分基础知识本部分是考试的基础，所占分值比例较大，而且该章的试题比较灵活，因此在学习本章时,，要以理解为主，切忌死记硬背，在学习过程中，要注意各个知识点之间的联系和区别，将盘根错节的知识点理顺成知识网络。具体知识点总结如下：一、算法该知识点在试卷中一般有12 道题，考生要了解算法的定义、特征、组成要素、常用算法和算法复杂度，其中算法复杂度是考试重点，与之有 密切联系的是：查找技术（第一章第 7 节）和排序技术（第一章第8 节），考生最后复习时，要牢记六种排序方法的时间复杂度和两种查找方法的特点及最好/最坏/平均查找次数。二、数据结构该知识点在试卷中一般有24 道题，是本章的重点和难点，考题中所涉及的考点一般并不是教材上的直接知识点，因此在学习过程中，要以是否提高了数据处理的效率（速度/空间）为主线，对每种逻辑结构和其对应的不同存储结构进行分析、比较和总结。三、线性结构：线性表、栈和队列、非线性结构：树该知识点是必考的知识点，在学习过程中，要深刻理解和掌握栈和队列的特点（包括逻辑结构特点和不同的存储结构的特点）以及进栈、退栈和入队、退队时指针的变化，对于二叉树的性质和遍历规则要牢记并灵活运用。四、程序设计基础考点包括：面向过程的程序设计方法和面向对象的程序设计方法。前者主要了解其设计原则，后者是本章重点，要理解并掌握一些基本概念和术语，例如对象（类的实例）及其特点、属性、方法、事件、消息、类（对象的抽象）、封装、继承、多态等。五、软件工程基础掌握软件工程中的一些基本概念，例如：软件的定义、特点和分类；软件危机的表现；软件工程的定义、要素、核心思想、原则和目标。然后以软件生命周期为主线，重点掌握每个 阶 段（需求分析、总体设计、详细设计、测试和调试）的主要任务、方法和常用工具，该知识点是本章的重点，建议以表格的形式进行归纳和总结，以明确各个知识点的联系，以有助于记忆。在归纳总结过程中，要注意以下知识点的区别，例如：测 试（发现错误；本阶段涵盖整个软件生命周期的过程）、调 试（诊断并改正程序中的错误，主要在开发阶段）的区别；白盒测试（内部的结构测试）和黑盒测试（外部接口的功能测试）的区别；每个阶段所用到的工具（DFD、DD、SC、PFD、N-S等）的区别。六、数据库设计基础主要知识点有数据库系统组成、发展、特点、内部体系结构；数据模型；实体联系模型；关系模型、关系运算和数据库设计与管理，其中数据库系统、关系模型和关系运算是考试重点。第一章数据结构与算法1.1 算法知识点1 算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。所以其四个基本特征包括：（1）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（2）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；（3）可行性，算法原则上能够精确地执行；（4）拥有足够的情报，算法要有一定的输入数据和必须要有的输出结果。算法的基本要素包括：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输；算法的三种基本控制结构：顺序结构、选择结构、循环结构。知识点2 算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。知识点3 算法效率的度量一算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。通常，一个算法所用的时间包括编译时间和运行时间。算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。知识点4 指令系统：一个计算机系统能执行的所有指令的集合。1.2 数据结构基础知识点1 数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。知识点2 数据结构：指相互有关联的数据元素的集合。数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。知识点3 数据的逻辑结构应包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系（指逻辑关系，与存储位置无关）。即一个数据结构可以表示成B=（D,R）其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据物理结构。数据的存储结构有顺序、链接、索引等。一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D 中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R 中的每一个二元组，用一条有向线段从前件结点指向后件结点。例如，一年四季的数据结构可以用如图1.1所示的图形来表示。又如，反映家庭成员间辈分关系的数据结构可以用如图1.2所示的图形表示。图 1.1 年四季数据结构的图形表示 图 1.2 家庭成员间辈分关系数据结构的图形表示根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构乂称线性表1.3线性表及顺序存储结构知识点1线性表是由n(n2O)个数据元素a”a 2,，a。组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(aa2,a j,a。)，其 中 ai(i=l,2,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。显然，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。知识点2非空线性表有如下一些结构特征：有且只有一个根结点a”它无前件；有且只有一个终端结点a ,它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n 称为线性表的长度。当 n=0时，称为空表。知识点3线性表由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。例如，一年中的四个季节(春，夏，秋，冬)是一个长度为4 的线性表，其中的每一个季节名就是一个数据元素。数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录；由多个记录构成的线性表称为文件。知识点4线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。元素ai的存储地址为：ADR(ai)=ADR(al)+(i-l)k,ADR(al)为第一个元素的地址，k 代表每个元素占的字节数。顺序表的运算：查找、插入、删除。1.4线性链表线性表的链式存储结构称为线性链表o为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点，称为指针域。由此可知，在线性链表中，存储空间的结构如 图 L 3 所示。存储扉号 数据域12m指斜域图 1.3 线性链表存储结构在线性链表中，用一个专门的指针H E A D 指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用 N U L L 或 0 表示），表示链表终止。线性链表的逻辑结构如图1.4 所示。存储序号 数也域 指针域I|V（1）|Z E X T iH图 1.4 链表的逻辑结构线性链表中存储结点的结构如图1.5 所示。HEAD|-数据 1|T-M。据 2|I 一 I 数据 n图 1.5 线性链表逻辑状态下面举一个例子来说明线性链表的存储结构。数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性单链表中，H E A D 称为头指针，H E A D=N U L L （或 0）称为空表。如果是双项链表的两指针：左 指 针（L l i n k）指向前件结点，右 指 针（R l i n k）指向后件结点。线性链表的基本运算：查找、插入、删除。1.5栈和队列栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈。栈(stack)是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出(FILO-FirstlnLastOut)或“后进先出(LIFOLast In First Out)的原则组织数据的，因此，栈也被称为“先进后出”表 或“后进先出”|入栈 出栈表。由此可以看出，栈具有记忆作用。I t通常用指针top来指示栈顶的位置，用指针bottom-指向栈底。栈 顶 3 一%往栈中插入一个元素称为入栈运算，从栈中删除一 P个元素(即删除栈顶元素)称为退栈运算。栈顶指针top动态反映了栈中元素的变化情况。图 1.6是栈的示意图。的栈的存储方式有顺序存储和链式存储。栈低bottom ai栈的基本运算：(1)入栈运算，在栈顶位置插入元素；(2)退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；图 1.6 栈示意图(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。队列(queue)是指允许在一端进行插入、而在另端进行删除的线性表。允许插入的一端称为队尾，通常用个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头(也称为队头)，通常也用一个排头指针(front)指向排头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出(FIFOFirst InFitOut)或“后进后出(LILO-Last In Last Out)的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。图 L7是具有6 个元素的队列示意图。退 对 一|A|B|C|D|E|F|：入对图 1.7 队列往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。队列是“先进先出(FIFO)或“后进后出(L IL O)的线性表。队列运算包括：(1)入队运算：从队尾插入一个元素；(2)退队运算：从队头删除一个元素。队列的顺序存储结构一般采用队列循环的形式。循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如 图 1.13所示。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。在循环队列中，用队尾指针real指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即 rear=front=m,如 图 1.13所示。循环队列主要有两种基本运算：入队运算与退队运算。卷进行一次入队运算，队尾指针就进一。当队尾指针rear=m+l时，则置reaul。每进行一次退队运算，排头指针就进一。当排头指针front=m+l时，则置front=l。1.6树与二叉树树是种简单的非线性结构，其所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树(binary tree)是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构很相似，并且，树结构的所有术语都可以用到二叉树这种数据结构上。二叉树具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树基本性质：(1)在二叉树的第k 层上，最多有2k-l(k，l)个结点；(2)深度为m 的二叉树最多有2m-l个结点；(3)度为0 的结点(即叶子结点)总是比度为2 的结点多一个：(4)具有n 个结点的二叉树，其深度至少为 log2n+l,其中 log2n 表示 取 log2n的整数部分(5)具有n 个结点的完全二叉树的深度为|log2n+l；(6)设完全二叉树共有n 个结点。如果从根结点开始，按层序(每一层从左到右)用自然数 1,2,n 给结点进行编号(k=l,2-.n),有 以 下 结 论：若k=l,则该结点为根结点，它没有父结点；若 k l,则该结点的父结点编号为INT(k/2)；若2 k W n,则 k 结点的左子结点编号为2k；否则该结点无左子结点(也无右子结点)；若2 k+l l,则该结点的父结点编号为I NT(W 2)若2 k W n,则编号为k的结点的左子结点编号为2k；否则该结点无左子结点(显然也没有右子结点)。若2k+l W n,则编号为k的结点的右子结点编号为2k+l；否则该结点无右子结点。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。补充：增加度为1的结点不会影响二叉树的叶子结点数，每增加一个度为2的结点便会增加一个叶子结点，没有度为2的结点时叶子结点数为k已知完全二叉树有x个结点，求其叶子结点数：确定层数为k；第k层的结点数y=x-(2k-l-l)；第k-1层的叶子结点数n=2(k-l)-l-y/2(若y/2有余，则要加1 ；最后y+n。二叉树通常采用链式存储结构各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件(即两个子结点)，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针 i域 图1.8为二叉树存储结点的示意图。其中：L(i)为结点i的左指针域，即L为结点i的左予结点的存储地址；R 为结点i的右指针域，即R为结点i的右子结点的存储地址；V 为数据域。由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。图1.9(a)、(b)分别表示了一棵二叉树、二叉链表的逻辑状态。其 中BT称为二叉链表的头指针，用于指向二叉树根结点(即存放二叉树根结点的存储地址)。Le h i I d V a l u e R c h i l dL(i)V(i)R(i)图1.8二叉树存储结点的结构(H)二叉利(b).义 表的漫辑状态图1.9二叉树和二叉链表二叉树的遍历是指不重复地访问二叉树中的所有结点。所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点,然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。如果对图1.9（a）中的二叉树进行前序遍历，则遍历的结果为F,C,A,D,B,E,G,H,P（称为该二叉树的前序序列）。所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树,然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。如果对图1.9（a）中的二叉树进行中序遍历，则遍历结果为A,C,B,D,F,E,H,G,P（称为该二叉树的中序序列）。所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，.并且，在遍历左、右子树时,仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。如果对图1.9（a）中的二叉树进行后序遍历，则遍历结果为A,B,D,C,H,P,G,E,F（称为该二叉树的后序序列）。1.7 查找查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，通常有二种不同的查找方法。顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。设有序线性表的长度为n,被查元素为x,则对分查找的方法如下：将 x 与线性表的中间项进行比较：若中间项的值等于x,则说明查到，查找结束；若 x 小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若 x 大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n 的有序线陛表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n 次。1.8 排序排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。一、交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。(1)冒泡排序法，首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了 一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。假设线性表的长度为n,则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-l)/2。需要比较的次数为n(n-l)/2；(2)快速排序法。快速排序法的基本思想如下：从线性表中选取一个元素，设为T,将线性表后面小于T 的元素移到前面，而前面大于T 的元素移到后面，结果就将线性表分成了两部分(称为两个子表)，T 插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就 以 T 为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T,而后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。由此可知，快速排序法的关键是对线性表进行分割，以及对各分割出的子表再进行分割，这个过程如图1.10所示。在对线性表或子表进行实际分割时，可以按如下步骤进行：首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P(k),并将P(k)赋给T,再将表中的第一个元素移到P(k)的位置上。然后设置两个指针i 和 j 分别指向表的起始与最后的位置。反复操作以下两步：(1)将 j 逐渐减小，并逐次比较P(j)与 T,直到发现一个P(j)T为止，将 P移到P的位置上。上述两个操作交替进行，直到指针i 与 j 指向同一个位置(即i=j)为止，此时将T 移到P的位置上。二、插入类排序法是指将无序序列中的各元素依次插入到已经有序的线性表中。(1)简单插入排序法从线性表的第2 个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。一般来说，假设线性表中前j-1 个元素已经有序，现在要将线性表中第j 个元素插入到前面的有序子表中，插入过程如下：首先将第j 个元素放到一个变量T 中，然后从有序子表的最后一个元素(即线性表中第j-1 个元素)开始，往前逐个与T 进行比较，将大于T 的元素均依次向后移动一个位置，直到发现一个元素不大于T 为止，此时就将T(即原线性表中的第j 个元素)插入到刚移出的空位置上，有序子表的长度就变为j 了。在简单插入排序法中，每 次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-l)/2次比较。(2)希尔排序法的基本思想如下：将整个无序序列分割成若干小的子序列分别进行插入排序。分割分 害!I 子序列的分割方法如下：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减 到1时，进行一次插入排序，排序就完成。增量序列一般取h kn/2 k(k=l,2,l o g2n ),其中n为待排序序列的长度。希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为OS”)。三、选择类排序法(1)选择排序法的基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-l遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。图1.4 0是这种排序法的示意图，图中有方框的元素是刚被选出来的最小元素。最坏情况需要n(n-l)/2次比较；(2)堆排序法堆的定义如下：具有n个元素的序列(hh 2,，hj,当且仅当满足%之 h2ihi 之 h2M%4 hn%+i(i=L 2,，n/2)时称之为堆。本节只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项。在实际处理中，可以用一维数组H(l：n)来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。例如,序列(9 1,8 5,5 3,3 6,4 7,3 0,2 4,1 2)是一个堆，它所对应的完全二叉树如图1.4 1所示。由图1.1 1可以看出，在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左、右子树的根结点值，因此，堆顶(完全二叉树的根结点)元素必为序列的n个元素中的最大项。在具体讨论堆排序法之前，先讨论这样一个问题：在一棵具有n个结点的完全二叉树 用一维数组H(l：n)表示 中，假设结点H(m)的左右子树均为堆，现要将以H(m)为根结点的子树也调整为堆。这是调整建堆的问题。图1.1 1堆顶元素为最大的堆例如，假设图1.1 2(a)是某完全二叉树的一棵子树。显然，在这棵子树中，根结点4 7的左、右子树均为堆。现在为了将整个子树调整为堆，首先将根结点4 7与其左、右子树的根结点值进行比较，此时由于左子树根结点9 1大于右子树根结点5 3,且它又大于根结点4 7,因此，根据堆的条件，应将元素4 7与9 1交换，如 图1.4 2(b)所示。经过这一次交换后，破坏了原来左子树的堆结构，需要对左子树再进行调整，将元素8 5与4 7进行交换，调整后的结果如图1.1 2(c)所示。由这个例子可以看出，在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。有了调整建堆的算法后，就可以将一个无序序列建成为堆。假设无序序列H（l：n）以完全二叉树表示。从完全二叉树的最后一个非叶子结点（即第n/2 个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆，最后就可以得到与该序列对应的堆。根据堆的定义，可以得到堆排序的方法如下：（1）首先将一个无序序列建成堆。（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1 个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第步，直到剩下的子序列为空为止。堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O（n l og 2 n）。相比以匕几种（除希尔排序法外），堆排序法的时间复杂度最小。1.9 练习题一、选择题：I .下列数据结构中，能用二分法进行查找的是（）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.对于长度为n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A）冒泡排序为n/2 B）冒泡排序为nC）快速排序为n D）快速排序为n（n-l）/27.对长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）A）log2n B）n/2 C）n D）n+18.下列对于线性链表的描述中正确的是（）A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的9.算法的时间复杂度是指（）A）执行算法程序所需要的时间 B）算法程序的长度C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数10.算法的空间复杂度是指（）A）算法程序的长度C）算法程序所占的存储空间11.下列叙述中正确的是（）B）算法程序中的指令条数D）算法执行过程中所需要的存储空间A）线性表是线性结构C）线性链表是非线性结构1 2.数据的存储结构是指（）A）数据所占的存储空间量B）栈与队列是非线性结构D）二叉树是线性结构B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据13.下列关于队列的叙述中正确的是（）A）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是先进后出的线性表14.下 列关于栈的叙述中正确的是（）A）在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是先进后出的线性表15.设有下列二叉树:对此二叉树中遍历的结果为（）A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA16.在深度为5 的满二叉树中，叶子结点的个数为（）A）32 B）31 C）16 D）1517.对长度为n 的线性表进行顺序查找，在最坏的情况下所需要的比较次数为（）A）n+1 B）n C）（n+1）/2 D）n/218.则 T 的度为4,其中度为1,2,3,4的结点个数分别为4,2,1。则 T 中的叶子结点数为（）A）8 B）7 C）6 D）519.下列叙述中，错误的是（）A）数据的存储结构与数据处理的效率密切相关。B）数据的存储结构与数据处理的效率无关。C）数据的存储结构在计算机中所占的空间不一定是连接的。D）一种数据的逻辑结构可以有多种存储结构。20.下列叙述中，正确的是（）A）线性链表中的各元素在存储空间中的位置必须是连续的。B）线性链表中的表头元素一定存储在其他元素的前面。C）线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面.D）线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的。21.设 栈 S 和队列Q 的初始状态为空，元素4%（1,9 依次通过栈5,并且一个元素出栈后即进入队列Q,若出队的顺序为b,d,c,f,e,a,贝 IJ栈 S 的容量至少应该为（）A）3 B）4 C）5 D）622.在下列数据结构中，不是线性结构的是（）A）线性链表 B）带链的栈 C）带链的队列 D）二叉链表23.在下列数据结构中按先进后出原则组织数据的是（）A）循环队列 B）栈 C）循环链表 D）顺序表24.下列数据结构具有记忆功能的是（）A）队列 B）循环队列 C）栈 D）顺序表25.设有下列二叉树对此二叉树前序遍历的结果为（）A）ZBTYCPXA B）ATBZXCYP C）ZBTACYXP D）ATBZXCPY26.设一棵二叉树中有3 个叶子结点，有 8 个度为1 的结点，则该二叉树中总的结点数为（）A）12 B）13 C）14 D）1527.在最坏的情况下，下列排序方法中时间复杂度最小的是（）A）冒泡排序 B）快速排序。插入排序 D）堆排序28.在长度为n 的有序线性表中进行二分查找，需要的比较次数为（）A）log2n B）nlog2n C）n/2 D）（n+l）/2二、填空题：1.算 法 复 杂 度 主 要 包 括 时 间 复 杂 度 和。2.一棵二叉树第六层（根节点为第一层）的节点数最多为 个。3.数据结构分为逻辑结构和存储结构，循环队列属于 结构。4.某二叉树中，度为2 的结点有18个，则该二叉树中有 个叶子结点。5.问 题 处 理 方 案 的 正 确 而 完 整 的 描 述 称 为 6.在长度为n 的有序线性表中进行二分查找，需要的比较次数为.7.设一-棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点.8.设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为9.在最坏的情况下，冒泡排序的时间复杂度为.10.在一个容量为1 5 的循环队列中，若头指针front=6,尾 指 针 rear=9,则该循环队列中共有个元素.11.数据结构分为逻辑结构与存储结构，线性链表属于。12.在个容量为25的循环队列中，若头指针front=16,尾指针rea匚9,则该循环队列中共有个元素。13.在长度为n 的线性表中查找一个表中不存在的元素，需要的比较次数为 o14.设一棵完全二叉树共有739个结点，则在该二叉树中有 个叶子结点。15.在深度为5 的完全二叉树中，度为2 的结点数最多为 o第 二 章 程序设计基础程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。除了好的程序设计方法和技术之外，程序设计风格也是很重要的，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。因此程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。2.1 程序设