欣赏第2章 数据结构和算法

第2章数据结构和算法本章主要考察的内容是：1.算法的基本概念算法的定义算法的特点算法的复杂度2．数据结构的基本概念3.线性结构与非线性结构(1)线性表及其顺序存储结构(2)栈及其基本运算(3)队列及其基本运算(4)线性链表4.树的基本概念和特征二叉树的基本概念及其特性二叉树的遍历5.查找技术(1)顺序查找(2)二分法查找6.排序技术(1)交换类排序法(2)插入类排序法(3)选择类排序法历年的全国计算机等级考试的笔试中，数据结构和算法部分的分值约占10-15%，本章历年的考题分布情况如表2-1所示：表2-1程序设计基础部分历年考题分数分布表考点内容2004.092005.042005.092006.042006.09小计算法的定义22算法的特点22算法复杂度242210栈、队列224210数据结构22228树的基本概念和特征22228查找技术424414排序技术2226合计101412101460由表2-1可知，在历年的笔试考试中，考试的关键点主要是算法、数据的存储结构、树和排序。2.1.1算法考点1:算法的基本概念所谓算法是指对解题方案准确而完整的描述。如果一个问题可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结构，则称这个算法是可解的。算法既不是程序，也不是解题方法。程序可以作为算法的一种描述，由于在编写程序时要受到计算机系统运行环境的限制，因而，程序的编制一般不会优于算法的设计。⑴算法的基本特征包括以下几点。①可行性。②确定性。算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。在2005年4月的考试中以选择题的形式考查了该考点内容。今年针对该考点出题的几率较高，题型可能是选择题也可能是填空题，考生应重点掌握该考点的相关概念。③

有穷性。算法必须能在有限的时间内做完，能在执行有限个步骤后终止，这包括合理的执行时间的含义。在2005年4月的考试中以选择题的形式考查了该考点内容。今年针对该考点出题的几率较高，题型可能是选择题也可能是填空题，考生应重点掌握该考点的相关概念。④

足够的情报。(2)以下两个基本要素。①对数据的运算和操作。算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。在一般的计算机系统中，基本操作包括算术运算、逻辑运算、关系运算和数据传输。②算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以及顺序、选择、循环3种基本控制结构组合而成。算法设计的基本方法包括列举法、归纳法、递推、递归、递推技术、回溯法。例2.1(2005年4月填空题第5题)问题处理方案的正确而完整的描述称为_______。【解析】所谓算法是指对解题方案的准确而完整的描述。【答案】算法例2.2在计算机中，算法是指_______。（A）查询方法（B）加工方法（C）对解题方案的准确而完整的描述（D）排序方法【解析】请参照配音“考点破解1”说明。【答案】C例2.3算法一般都可以用哪几种控制结构组合而成_______。（A）循环、分支、递归（B）顺序、循环、嵌套（C）循环、递归、选择（D）顺序、选择、循环【解析】请参照本章“考点破解1”的说明。【答案】D例2.4在下列选项中，哪个不是一个算法应该具有的酝酿特征_______。（A）确定性（B）可行性（C）无穷性（D）拥有足够的情报【解析】算法的基本特性能般包括了确定性、可行性、有穷性和拥有足够的情报。【答案】C例2.5下面关于递推和递推算法描述正确的是_______。（A）

不会出现既可以归纳为递推算法，又可以归纳为递归算法的实际问题（B）

递归算法和递推算法基本相同（C）

递归算法执行效率比递推算法低（D）

递推算法分为直接递推算法与间接递推算法【解析】从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法称为递推算法，递推算法实际上属于归纳法。人们为了降低问题的复杂度，一般总是将问题逐层分解，最后归纳为一些简单的问题，这个过程一直做下去，直到出现最简单的问题为止。有些实际问题，既可以归纳为递推算法，也可以归纳为递归算法，但递推和递归实现的方法大不一样。递推是从初始条件开始，逐次推出所要求的结果，而递归则是算法本身到达递归边界的。递归算法比递推简单，但递归算法执行效率较低。【答案】C自测题可用“2.2过知精练”中的选择题第1～2题以及填空题1～2题进行自测。考点2:算法复杂度算法的复杂度主要包括时间复杂度和窨复杂度。1.

算法的时间复杂该考点的命题重点是“算法复杂度该考点的命题重点是“算法复杂度”的概念，出题类型以填空题居多。在2004年9月、2005年4月和2005年9月的考点中都考核了本考点的相关知识。考生必须掌握该考点的相关概念。算法的工作量用算法所执行的基本运算次数来试题，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=ƒ(n)其中n是问题的规模。在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两面三刀种方法来分析算法的工作量。⑴平均性态分析（AverageBehavior）这是指用各种特定输入的基本运算次数的带权平均值来度量算法的工作量。设χ是所有可能输入中的某个特定输入，p(χ)是χ出现的概率（即输入为χ的概率），t(χ)是算法在输入为χ时所所的酝酿运算次数则算法的平均性态定义为：A(N)=∑p(χ)t(χ)X∈Dn其中，Dn表示当规模为n时，算法执行时所有可能输入的集合。其中，Dn表示当规模为n时，算法执行时所有可能输入的集合。⑵最坏情况复杂性（Worst-CaseComplexity）。这是指在规模为n时，算法所执行的基本运算的最大次数。它定义为：W(n)=max{t(χ)}χ∈Dn显然，W（n）的计算要比A（n）的计算方便得多。由于W（n）实际上是给出了算法工作量后个上界，因此，它比A（n）更且有实用价值。2．算法的空间复杂度一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所上的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序势利过和中的工作单元以及某种数结绝民需要的附加存储窨。如果客外空间量相寻于问题规模来说是常数，则称该算法是原地（InPlace）工作的，在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。例题精解例2.6（2005年9月填空题第2题）算法复杂度主要包括时间复杂度和＿＿＿复杂度。【解析】请详见“考点破解2。”【答案】空间例2.7（2004年9月填空题第1题）如果一个算法的额外空间量相对于问题规模来说是常娄，刚称该算法是＿＿＿工作的。【解析】请详见本章“考点破解2。”【答案】原地自测题可用“2.2过关精练”中的选择题第3～4题、填空题第3～4题进行自测。

2.1.2数据结构的基本概念考点3:数据结构的基本概念数据结构是指相互有关联的数据据元素的集合。‘该考点的相关试题在2005年9月和2005年4月的考试中均有出现，考生需要重点掌握。数据结构是一门研究在非数值计算的程序设计问题中，计算机的数据元素以及它们之间的关系和运算的学科。数据结构作为计算机的一门学科，主要研究以下3个方面的问题：该考点的相关试题在2005年9月和2005年4月的考试中均有出现，考生需要重点掌握。1．

数据的逻辑结构所谓数据的逻辑结构，是指所是非曲直数据元素之间逻辑关系的数据结构。它包括两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。于是，一个数据结构可以表示成B=(D,R),其中B表示数据结构。数据的逻辑结构包含：⑴表示数据元素的信息；⑵表示各数据元素之间的前后件关系。2．

数据的存储（数据的物理结构）所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式（也称数据的物理结构）。一般来说，一种数据的逻辑结构根据需要可以表示为多种存储结构，常用的存储结构有顺序、链接下来索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。3．

各种数据结构的运算对各种数据结构进行的运算有检索、排序、插入、删除等。例题精解例2.8（2005年4月选择题第1题）数据的存储结构是指＿＿＿。(A)存储在外存中的数据(B)数据所占的存储空间(C)数据在计算机中的顺序存储方式(D)数据的逻辑结构在计算机中的表示【解析】请详见本章“考点破解3”【答案】D例2.9（2004年9月填空题第2题）数据的逻辑结构在计算机存储控件中的存放形式称为数据的＿＿＿。【解析】请参照“考点破解2”中关于存储结构的定义解答本题。【答案】存储结构或物理结构或物理存储结构例2.10（2004年9月选择题第1题）下面叙述正确的是＿＿＿。(A)

算法的执行效率与数据的存储结构无关(B)

算法的窨复杂度是指算法程序中指令（或语句）的条数据(C)

算法的有穷性是指算法必须能执行有限个步骤之后终止(D)

以上三种描述都不对【解析】采用不同的数据存储结构，数据昝的效率是不同的。【答案】C例2.11数据的逻辑结构包含了表示数据元素的信息和＿＿＿。【解析】请详见本章“考点破解3”【答案】表示各数据元素之间的前后关系例2.12数据的结构包数据的＿＿＿结构和数据的存储结构。【解析】请参照本章“考点破解2”相应说明解答本题。【答案】逻辑自测题可用“2.2过关精练”中的选择题第5～9题、填空题第5～7题进行自测。该考点命题重点是线性结构和线性表的概念，试题类型以选择为主。在2005年9月和2004年9月的考试中都考查过该考点，因而考生应重点掌握该考点的相关概念。考点4:线性结构与非线性结构该考点命题重点是线性结构和线性表的概念，试题类型以选择为主。在2005年9月和2004年9月的考试中都考查过该考点，因而考生应重点掌握该考点的相关概念。根据数据结构中各元素之间前后件关第的复杂性程度，一般将数据结构分为线性表和非线性表。如果一非空的数据结构满足下列两个条件，则称该数据结构为线性结构（线性结构又称为线性表）。⑴有且只有一个根结点。⑵每一个结点最多有一个前件，也最多有一个后件。在一个线性结构中插入或删除任何一个结点后还就是线性结构。如果一个数据结构不是线性结构，刚称之为非线性结构。例题精解例2.13（2005年9月选择题第4题）下列叙述中正确的是＿＿＿。(A)一个逻辑数据结构只能是一种存储结构(B)数据的逻辑结构属于线性结构，存储结构属于非线怀结构(C)一个逻辑数据结构可以有多个存储结构，且各种存储结构不影响数据处理的效率(D)一个逻辑数据结构可以有多个存储结构，且各种存储结构影响数据昝的效率【解析】请详见本章“考点破解3”和“考点破解4”【答案】D例2.14（2004年9月选择题第2题）以下数据结构中不属于线性数据结构的是＿＿＿。(A)队列(B)线性表(C)二叉树(D)栈【解析】二叉树可以有多个后件，所以二叉树不是线性表。【答案】C自测题可用“2.2过关精练”中的选择题第10题进行自测。2.1.3线性表及其顺序存储结构考点5:线性表的基本概念该考点的命题重点是线性表的基本结构特征，近几次考试中还没有考查过该考点。线性表由一组数据元素构成，数据元素在线性天中的位置只取决于它们自己的序与，即数据元素之间的相对位置是线性的。该考点的命题重点是线性表的基本结构特征，近几次考试中还没有考查过该考点。①非空线性表具有如下一些结构特征：②有且只有一个根结点a1,它无前件；③有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的数n称为线性表的长度。当n=0时，称为空表。例题精解例2.15下列关于线性表的叙述不正确的是＿＿＿。(A)矩形是一个线怀表(B)在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成(C)在线性表中，除了第一个元素外，其他元素有且只有一个前件(D)线性表中所有元素有且只有一个后件【解析】在线性表，终点是没有后件的，D选项叙述错误。【答案】D自测题可用“2.2过关精练”中的选择题第11题以及填空题第8题进行自测。考点6:线性表顺序存储的特点及远处在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。线性表的顺序存储结构具有以下两个基本特点：该考点至今没有考查过，但不排除针对此考题出题的可能。请着重掌握线性表顺序存储的两个基本特点。⑴线性表中所有元素所占的存储空间是连续的；该考点至今没有考查过，但不排除针对此考题出题的可能。请着重掌握线性表顺序存储的两个基本特点。⑵线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的线性存储结构下，可以对线性表进行插入、删除、查找、排序、分解、合并、复制和逆转等操作。例题精解例2.16在下面关于线性表的叙述中，选出正确的一项＿＿＿。(A)

线性表的每个元素都有一个直接前趋和直接后继(B)

线性表中至少有一个元素(C)

线性表中的元素必须按递增或递减的顺序排列(D)

除第一个元素和最后的个元素外，每个元素都有一个直接前趋和直接后继【解析】线性表的头结点没有前趋结点，尾结点没有后继结点，所以选项A错误，选项D正确。没有元素的线性表称为空表，所以选项B错误。根据线性表的定义可在线性表中的元素不一定是有序排列的，所以先项C也错误。【答案】D例2.17若某线性表中最常用的操作是取第n个元素的前趋元素，则采用＿＿＿存储方式最节省时间。（A）

顺序表（B）单链表（C）双链表(D)单环链表【解析】在线性表的顺序存储结构中，其前后件两个元素在存储空间中最紧邻的，且前件元素一定存储在后件元素的前面。在第I个元素的前趋元素定位上，采用顺序表的存储方式最节省时间。【答案】A自测题可用“2.2过关精练”中的选择题第12题以及填空题第9题进行自测。2.1.4栈及其基本运算考点7:栈该考点的命题重点是栈的概念与栈的基本运算，出题类型以选择题主为。在2005年的两次考试中都考核了该考点，考生需要重点掌握。栈（stack）是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先能被删除的元素；栈底元素总是星先被插入的元素，也是最后能被删除的元素即栈是按照“先进后出”（FILO-FirstInLastOut）或“后进先出”（LIFO-LastInFirstOut）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。该考点的命题重点是栈的概念与栈的基本运算，出题类型以选择题主为。在2005年的两次考试中都考核了该考点，考生需要重点掌握。栈有以下3种基本运算。⑴栈运算：插入元素。⑵栈运算：删除元素。⑶栈顶元素：将栈顶元素赋给一个指定的变量，些时指针无变化。例题精解例2.18（2005年9月选择题第3题）下列关于栈的描述正确的是＿＿＿。（A）

在栈中只能插入元素而不能删除元素（B）

在栈中只能删除元素而不能插入元素（C）

栈是特殊的线性表，只能在一端插入或删除元素（D）

栈是特殊的线性表，只能在一端插入元素，而不能在另一端删除元素【解析】栈是限定在一端进行插入与删除的本性表，因此只有选项C的说法是正确的。【答案】C例2.19（2005年4月选择题第2题）下列关于栈的描述错误的是＿＿＿。（A）栈是先进后出的线性表（B）栈只能顺序存储（C）栈具有记忆作用 （D）对栈的持入与删除操作中，不需要改变栈底指针【解析】顺序存储是线性表的一种最简单的存储方法，并不是惟一的存储方法。【答案】B例2.20栈底至栈顶依次存放元素A、B、C、D，在第5个元素E入栈前，栈中元素可以出栈，刚出栈序列可能是＿＿＿。（A）ABCED（B）DBCEA（C）CDABE（D）DCBEA【解析】栈（Stack）是限定在一端进行插入与删除的本性表，出栈操作只能是“先进后出”。本题中，如果没有E进栈，栈原来元素的出栈面序只能是D、C、B、A。这样包括第5个元素E在内的出栈顺序可以为EDCBA、DECBA、DCEBA、DCBEA、DCBAE共5种出栈序列。【答案】D自测题可用“2.2过关精练”中的选择题第13～18题以及填空题第12～14题进行自测。考点8:队列该考点的命题重点是队列与循环队列的概念，以及队列的基本运算。出题类型以选择题或填空题。在2005年9月的考试中以填空题考核了该考点。队列（queue）是指允许在一端（队尾）进行插入，而在另一端（队头或排头）进行删除的线性表。通常，指向队尾的指针称为队尾指针（rear），指向排头的指针称为排头指针（front）。该考点的命题重点是队列与循环队列的概念，以及队列的基本运算。出题类型以选择题或填空题。在2005年9月的考试中以填空题考核了该考点。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。在实际应用中，队列的顺序存储结构一般采用循环队列的形式，所谓盾环队列，就是将队列存储空间最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。循环队列运算有以下两类：⑴人队运算：从队尾插入一个元素；⑵退队运算：从队头删除一个元素。例题精解例2.21（2005年9月填空题第5题）数据结构分为逻辑结构和存储结构，循环队列属于＿＿＿结构。【解析】循环队列是从其存储结构上来说的。从其定义上可知，循环队列属于存储结构。【答案】存储或物理例2.22下列关于队列的叙述中正确的是＿＿＿。（A）在队列中只能插入数据(B)在队列中只能删除数据（C）队列是先进先出的线性表（D）栈是先进先出的线性表【解析】队列是先进先出的线性表，栈是先进后出的线性表，栈和队列是两个不同的存储结构。【答案】C例2.23栈和队列的共同点是＿＿＿。（A）都是先进后出(B)都是无进先出（C）只允许在端点处插入和删除元素（D）没有共同点【解析】栈为先进后出，队列为先进先出，因此选项A、B都错误。根据本章“考点破解7”和“考点破解8”关于栈和队列的定义可知，C选项正确。【答案】C例2.24对于队列只能在＿＿＿分别插入和删除元素。【解析】队列（queue）是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，。通常有一个称为队尾指针（rear）的指针指向队尾元素即尾指针决是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。【答案】队尾和队尾例2.25一个队列的入列序列是1，2，3，4，则队列的输出系列是＿＿＿。（A）4，3，2，1（B）1，2，3，4（C）1，4，3，2（D）3，2，4，1【解析】队列中允许在一端（队尾）进行插入，而在另一端（队头或排头）进行删除。在队列的这种结构中，最先插入的元素将最先能够疲删除，反之，最后插入的元素将最后才能被删除。也就是说在队列中要“先进先出”，所以本题中队列的输出序列是1，2，3，4。【答案】B自测题可用“2.2过关精练”中的选择题第19～22题、填空题第14～18题进行自测。2.1.5线性链表考点破解9线性链珍基本概念1．线性链表该考点的命题重点是线性链表的存储特点，在2005年4月的考试中考查了线性表的基本特点。该考点是本章重点，请掌握相关概念。线性表的链式存储结构称为线性链表。该考点的命题重点是线性链表的存储特点，在2005年4月的考试中考查了线性表的基本特点。该考点是本章重点，请掌握相关概念。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一个小块占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系，需要将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点，称为指针域。一般来说在线性表的链式存储结构中，各数据结点的存储序号是不边续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。当线性链表每一个结点只有一个指针哉时，由这个指针只能找到后件结点，但不能找到前件结点。对应的线性链表中的每个结点都设置两个指针，一个称为左指针（Llink）用以指向其前件结点，另一个称国右指针（Rlink），用以指向后件结点。这样的线性表称为双向链表。2．带栈的队列与栈类似，队列也是线性表，也可以采用链式存储结构。例题精解例2.26（2005年4月选择题第5题）下列对线性链表描述正确的是＿＿＿。（A）

存储空间不一定连续，且各元素的存储顺序是任意的（B）

存储空间不一定连续，且前件元素一定存储在后件元素的前面（C）

存储空间必须连续，且前件元素一定存储在后件元素的前面（D）

存储空间必须连续，且各元素的存储顺序是任意的【解析】一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系也不一致，各元素之间的前后关系是由各结点的指针来指示的。【答案】A例2.27在下面关于线性表的叙述中，选取出正确的一项＿＿＿。（A）

采用链接存储的线性表，必须占用一片连续的存储单元（B）

采用顺序存储的线性表，便于进行插入和删除操作（C）

采用链接存储的线性表，不必占用一片连续的存储单元（D）

链接和顺序存储线性表，都便于进行插入和删除操作【解析】一般来说在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，所以选项A叙述错误。采用顺序存储的线性表不便于进行插入和删除操作。这是链接与顺序存储器的不同，链接便于插入、删除。【答案】C自测题可用“2.2过关精练”中的选择题第23～27题以及填空题第19～22题进行自测。考点10:线性链表基本运算线性链表的基本运算主要有：插入、删除、合并、分解、逆转、复制、排序和查找。该考点至今未考查过，其内容难度较大，读者了解相关的概念即可。例题精解该考点至今未考查过，其内容难度较大，读者了解相关的概念即可。例2.28单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将如图2.2所示的指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中正确的是＿＿＿。(A)q:=p^.link;p^.link=q^.link;(B)p^.link:=q^.link;q:=p^.link；（C）q^.link:=p^.link;p^.link:=q;(D)p^.link:=q;q^.link:=p^.link;pheadpheadInfooinfoinfoInfooinfoinfo…………qinfoqinfo图2.2例2.28图【解析】根据题意需要从指针p指向的结点的link指针外断开，把p处的link指针指向q指针指向的结点，而q指针指向的结眯的link指针指向的是原p指针指向的结点link指针指向的结点。在操作过程中要注意赋值的先后顺序，否则某些值会丢失。选项A，语句q:=p^.link错误，该语句导致q指针指向的结点数据丢失，并且使指针q指向了p指针指向结点的下一个结点，不符合题意。选项C，正确。选项D，语句p^.link：=q^.link将一空指针值赋值给了p指针指向的结点的link指针，错误。选项C，正确。选项D，语句p^.link:=q导致p指针指向结点的link指针中的值丢失，虽然使该结点指向了q,但在第2条语句q^.link:=p^.link中两个值已经相同，无法满足题意的要求。【答案】C考点11:循环链表及其基本计算该考点的命题重点是循环链表的概念，试题类型可能是选择题主为或者填空题，近几次考试中都没有考到该考点的相应内容。循环链表的结构具有以下两个特点：该考点的命题重点是循环链表的概念，试题类型可能是选择题主为或者填空题，近几次考试中都没有考到该考点的相应内容。⑴在循环链表中增加了一个表头结点，其数据域为任意或者可根据需要来设置，指针域指向线性表的第一个元素的结点，循环链表头指针指向表头结点。⑵循环链表中最后一个结点的指针域不为空，而是指向表头结点。即在循环链表中，所有结点的掼针构成了一个环状状链。例题精解例2.29循环链表的主要优点是＿＿＿。A）

不再需要头指针了（B）

已知某个结点的位置后，能够容易找到它的直接前趋（C）

在进行插入、删除运算时，能更好地保证链表不断开（D）

从表中任一结点出发都能扫描到整个链表【解析】循环链表中，所有结点的指针构成了一个环状链，这种结构的主要优点是从表中任一结点出发都能扫描到整个链表。【答案】D自测题可用“2.2过关精练”中的选择题第28题以及填空题第23～24题进行自测。考点12:树的基本概念和特征树(tree)是种简单的非线性结构,所有元素之间具有明显的层次特性.在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件的结点称为叶子结点。该考点的命题重点在于树的基本概念和如何在计算机中使用树结构表示算术表达式。出题类型可以为选择题或填空题，该考点还没有考核过。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树是一种层次结构，根结点在第1层，同一层上民有结点的子结点都有下一层。树的最大层次称为树的深度。该考点的命题重点在于树的基本概念和如何在计算机中使用树结构表示算术表达式。出题类型可以为选择题或填空题，该考点还没有考核过。在计算机中，可以用树结构来表示算术表达式。用树来表示算术表达式的原则如下：⑴表达式中的每一个运算符在树中对应一个结点，称为运算符结点；⑵运算符的每一个运算对象在树中为该运算符结点的子树（在树中的喘序为从左到右）；⑶运算对象中的单变量均为叶子结点。例题精解例2.30树最适合用来表示＿＿＿。（A）有序数组元素（B）无序数组元素（C）元素之间具有分支层次关系的数据(D)元素之间无联第的数据【解析】树是一种简单的非线性结构，在树的数据结构中，所有数据元素之间的关系具有明显的层次特性，是一种层模型。层次模型是最早发展起来的数据库模型。【答案】C自测题可用“2.2过关精练”中的选择题第29题以及填空题第25～27题进行自测。该考点的命题重点是二叉树的结点计算。命题类型可为选择题或者填空题。在2005年的两次考试中以及2004年的考试中都考核了该考点，考生需要重点掌握。考点13:二叉树的基本概念及其特性该考点的命题重点是二叉树的结点计算。命题类型可为选择题或者填空题。在2005年的两次考试中以及2004年的考试中都考核了该考点，考生需要重点掌握。二叉树的定义是一个递归的定义，其根的左子树和右子树又是二叉树。最简单的二叉树是空二叉树。⑴二叉树有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树⑵二叉树有以下基本性质。①在二叉树的第k层上，最多有2k-1(k≥1)个结点；②深度为m的二叉树最多有2m-1个结点；③在任意一个二叉树中，度为0的结点（即叶子结点）总是比度为2的结点一个；④具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。⑶完全二叉树和满二叉树。完全二叉树是指除最后一层外，每一屋上的结点数均达到阳大值，在最后一层上只缺少右边的若干结点。完全二叉树还具有以下两个性质：①具有n个结点的完全二叉树的深度为[log2n]+1；②设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，……n给结点进行编号（k=1,2……n），有以下结论：

若k=1,则编号为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k/2）;

若2k≤n则编号为k的结点的右子结点编号为2k；否则该结点无子结点（也无右子结点）；

若2k+1≤n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。满二叉树是指除最后一层外，每一层上的所有结点有两个结点，则在第k层上有2k-1,深度为m满二叉树有2m-1个结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。例题精解例2.31（2005年9月填空题第4题）一棵二叉树第6层（根结点为第1层）的结点数最多为＿＿＿个。【解析】一棵二叉树的根结点为第1层，那么这棵二叉树第n层上的结眯数最多为2n-1，也就是说它的第6层上的结点数量最多为25，即32。【答案】32例2.32（2005年4月填空题第1题）某二叉树中度为2的结点有18个，则该二叉树中有＿＿＿个叶子结点。【解析】任一棵二叉树中，度为0的结点（即地子结点）总是比度为2的结点多一个【答案】19例2.33（2005年9月选择题第3题）在一棵二叉树上第5层的结点数最多是＿＿＿。（A）8（B）16（C）32（D）15【解析】二叉树性质已经明确说明“在二叉树的第k层上，最多有2k-1(k≥1)个结点”，在二叉树的第5层上的最多结点数为24=16【答案】B自测题可用“2.2过关精练”中的选择题第30～35题以及填空题第28～34题进行自测。考点破解14二叉树的遍历二叉树的遍历是指不重复地访问二叉树的所有结点。目前为止还没有针对该考点的试题材。请考生适当了解该考点的内容。二叉树的遍历分为下面三种：目前为止还没有针对该考点的试题材。请考生适当了解该考点的内容。⑴前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；⑵中序遍历（LDR）,首先遍历左子树，然后访问根结点，最后遍历右子树；⑶后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。例题精解例2.34在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中，所有叶子结点的先后顺序＿＿＿。（A）都不相同（B）完全相同（C）先序和中序相同，而与后序不同（D）中序和后序相同，而与先序不同【解析】根据本章“考点破解14”关于三种遍历的定义可知，不管使用哪种遍历方法，所有叶子结点的遍历顺序相同。例如图2.3所示的二叉树木前序序列、中序序列和后序序列分别为：F，C，A，D，B，E，G，H，PA，C，B，D，F，E，H，G，PA，B，D，C，H，P，G，E，F通过3种遍历，叶子结点的顺序都是A，B，H，P。【答案】BFFEECCBHAHDHHHPHGHBHAHDHHHPHGH图2.3二叉树例2.35某二叉树结点的前序序列为E、A、C、B、D、G、F，中序序列为A、B、C、D、E、F、G。该二叉树的结点的后序序列为＿＿＿。（A）B、D、C、A、F、G、E（B）D、B、C、F、A、G、E（C）D、C、E、G、F、A、B（D）D、E、G、A、C、F、B【解析】前序序列中以E开始，则可以确定E为根结点，则参考中序序列中E的位置可以判断A、B、C、D属于E的左子树，F、G属于E的右子树。再根据前序序列中F、G的顺序与中序序列中F、G的顺序很容易判断出G为E的在子树，F为G的左子树。再来看A、B、C、D的关系，在前序序列中A、C、B、D属于新世界子树，在此前序序列中A排在第一个位置，则A的位置应为新子树的根，C、B、D就为工的左子树成员，同时在中序序列中A排在第一位，则可判断A没有左子树，只有右子树。于是，A为E的左子树。]再来看B、C、D的关第，在前序序列中C、B、D属于新的妇树，在些前序序列中C排在第一个位置，则C的位置应为新子村的根，B、D就为C的左右子树成员；同时在中序序列中以B、C、D顺序排我，则可判断出B为C的左子树，D为C的右子树。那么整个二叉树的结构应如图所示2.4所示。EHEHAHGHAHGHFHFHCHCHBHDHBHDH图2.4例2.35图根据此图可得出该二叉树结点的后序序列为B、D、C、A、F、G、E。【答案】A＠自测题可用“2.2过关精练”中的选择题第36～39题以及填空题第35～36题进行自测。2.1.7查找技术考点15:顺序查找该考点的命题重点是顺序查找的技术指标，试题类型以填空题为主。在2005年4月曾对该考点进行了考查。顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找该考点的命题重点是顺序查找的技术指标，试题类型以填空题为主。在2005年4月曾对该考点进行了考查。指定的元素，其基本方法如下：从线性表的第一个元素开始，集资将线性表中的元素与被查元素进行比较，相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。在最坏情况下，顺序查找需要比较n次。在下列情况下只能使用顺序查找：⑴如果线性表为无序表（即表中元素的排列是无序的），则不管是顺充存储结构还是链式存储结构，都只能使用顺序查找。⑵即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。例题精解例2.36(2005年4月选择题第4题)对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为＿＿＿。（A）log2n（B）n/2（C）n（D）n+1【解析】对长度为n的线性表，在最坏情况下，需要查找的元素不在线性表中或者是线性表的最后一个元素，些时需发的比较次数为n.【答案】C＠自测题可用“2.2过关精练”中的选择题第40题以及填空题第37题进行自测。该考点的命题重点是二分法的查找方法，出题类型可能是选择题也可能是填空题。在2005年9月的考试中有一道相关试题。考点16:二分法查找该考点的命题重点是二分法的查找方法，出题类型可能是选择题也可能是填空题。在2005年9月的考试中有一道相关试题。二分法查找只适用于顺序存储的有序表。在些所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。例题精解例2.37(2005年9月选择题第2题)下列数据结构中，能用二分法进行查找的是＿＿＿。（A）顺序存储的有序线性表（B）线性链表（C）二叉链表（D）有序性链表【解析】二分法查找只适用于顺序存储的有序表，这是二分法查找的一个局限性。【答案】A例2.38二分查找法适用于存储结构为＿＿＿且按关键字排好离的线性表。（A）顺序存储（B）链式存储（C）顺序存储或链式存储（D）索引存储【解析】二分法查找只适用于顺序存储的有序表。【答案】A自测题可用“2.2过关精练”中的选择题第41～43题以及填空题第38～39题进行自测。2.1.8排序技术考点17:交换类排序法该考点的命题重点在交换类排序的种类及其排序原理。该考点在2005年4月的考试中出现过，是本章必须掌握的内空。所谓交换类排序法是指借助数据元素之间岳母相交换进行排序的一种方法。冒泡排序和快速成排序都是交换类排序方法。该考点的命题重点在交换类排序的种类及其排序原理。该考点在2005年4月的考试中出现过，是本章必须掌握的内空。冒泡排序冒泡排序法是一种是简单的交换类排序方法。它是通过相邻数据元素交换逐步将线性表变成有序的。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往捕捞扫描和n/2遍的从后往前扫描，需要的比较次数为n(n-1)/2,其数量级为n2。交换类排序这是快速排序的基本方法。在待排序的序列中任取一个记录，以它为基准用交换的方法将所有的记录发成两个部分（关键码比它小的一个部分和关键码比它大的另一个部分），再分别对两个部分实施上述过程，一直重复到排序完成为止。例题精解例2.39（2005年4月选择题第3题）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_______。（A）冒泡排序为n/2（B）冒泡排序为n（C）快速排序为n（D）快速排序为n(n-1)/2【解析】对长度为n的线性表，在最坏情况下，冒泡排序法的比较次数为n(n-1)/2，快速排序的比较次数也是n(n-1)/2。【答案】D自测题可用“2.2过关精练”中的选择题第44～51题、填空题第40～42题进行自测。考点18:插入类排序法插入排序，就是指将无序序列中的各元素依次插入到已经有序的线性表中。目前还未针对该考点出过题，若出题，则命题重点是简单插入排序法和希尔排序法的使用，试题类型可能为选择题也可能是填空题。简单插入排序目前还未针对该考点出过题，若出题，则命题重点是简单插入排序法和希尔排序法的使用，试题类型可能为选择题也可能是填空题。在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。希尔排序希尔排序（ShellSort）虽然也是插入类排序，但它对简单插入排序任职较大的改进。希尔排序的基本思想如下：将整个无序序列分割成若干小的子序开分别进行插入排序。子序列的分割方法是：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐逐次减少这个增量，最后当h减到1时，进行一次插入排序，排序就完成。希尔排序的效率与所选取的增量序列有关。增量序列一般取ht=n/2k(k=1,2,…，[log2n])，其中n为排序序列的长度。例题精解例2.40希尔排序法属于哪一种类型的排序法_______。（A）交换类排序法（B）插入类排序法（C）选择类排序法（D）建堆排序法【解析】请详见本章“考点破解18”。【答案】B自测题可用“2.2过关精练”中的填空题第43～44题进行自测。考点19:选择类排序法简单选择排序法该考点至今未考查过，若针对此考点出题，命题重点是选择类排序法原理，或者要求考生判断哪些排序方法属于选择类排序法。选择排序法的基本思想为：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采取同平的方法，上到子表空为止。该考点至今未考查过，若针对此考点出题，命题重点是选择类排序法原理，或者要求考生判断哪些排序方法属于选择类排序法。简单选择排序法在最坏情况下需要比较n(n-1)/2次。堆排序堆排序：是选择排序的改进，其方法如下。将一个无序序列建成堆。将堆顶元素（序列中的最大项）与堆中最后一个无互交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左右子树仍为堆，可以将该子序列调整为堆。如此反复，直到剩下的子序列为空止。堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表却很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。常见排序方法的排序性能情况如表2.2所示。表2.2常用排序方法排序性能比较表方法平均时间最坏情况时间辅助存储冒泡排序、简单排序、插入排序（shell）O(n2)O(n2)O(1)快速排序O(nlog2n)O(n2)O(nlog2n)堆排序O(nlog2n)O(nlog2n)O(1)归并排序O(nlog2n)O(nlog2n)O(n)例题精解例2.41在最坏情况下，堆排序需要比较的次数为_______。【解析】请详见本章“考点破解19”。【答案】O(nlog2n)例2.42设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序和冒泡排序对其进行排序（按递增顺序），冒泡排序最省时间，_______最费时间。【解析】快速排序的基本方法：在待排序的序列中任取一个记录，以它为基准用交换的方法将所有的记录分成两个部分（关键码比它小的部分和关键码比它吕产部分），再分别对这两个部分实施上述过程，一直重复到排序完成为止。运用快速排离法进行排序时，最坏的情况指的是对已经排好序的记录进行完全相反的排序，所需进间为O(n2)（这称为大O表示法，也数量级衡量复杂度，是时间复杂度和空间复杂度衡量中常用的工具）。【答案】快速排序自测题可用“2.2过关精练”中的填空题第45～48题进行自测。

所谓算法是指对解题方案准确而完整的描述。如果一个问题可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结构，则称这个算法是可解的。算法既不是程序，也不是解题方法。程序可以作为算法的一种描述，由于在编写程序时要受到计算机系统运行环境的限制，因而，程序的编制一般不会优于算法的设计。⑴算法的基本特征包括以下几点。①可行性。②确定性。算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。③

有穷性。算法必须能在有限的时间内做完，能在执行有限个步骤后终止，这包括合理的执行时间的含义。④

足够的情报。(2)以下两个基本要素。①对数据的运算和操作。算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。在一般的计算机系统中，基本操作包括算术运算、逻辑运算、关系运算和数据传输。②算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以及顺序、选择、循环3种基本控制结构组合而成。算法设计的基本方法包括列举法、归纳法、递推、递归、递推技术、回溯法。2.2过关精2.2.1过关练习题选择题下列关于计算机算法设计方法的描述，错误的是_______。

（A）计算机算法和人工处理的方法相同，是人工算法的计算机解题过程（B）列举法的特点是算法比较简单，但是当列举的可能情况较多时，执行列举算法的工作量会很大工业（C）从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的强论（D）递归的基础是归纳关于算法，下列描述正确的是_______。（A）通常，程序的编写不可能优于计算机算法的设计（B）程序也可以作为算法的一种描述，所以程序等于算法（C）归纳法的基本思想是，通过列举所有可能的情况，经过分析，最后找出一般的关系（D）使用归纳法得到的是正确的结论算法的时间复杂度是指_______。（A）执行算法程序所需要的时间（B）算法程序的长度（C）算法执行过程中所需要的基本运算次数（D）算法程序中的指令条数算法的空间复杂度是指_______。（A）算法程序的长度（B）算法程序中的指令条数（C）算法程序所占用的存储空间（D）算法执行过程中所需要的存储空间数据结构_______。（A）用于描述系统的动态特性（B）描述系统的静态特性（C）是一组规则（D）描述数据之间的联系以下关于数据的存储结构的叙述中正确的是_______。（A）数据的存储结构是数据间关系的的抽象描述（B）数据的存储结构是逻辑结构在计算机存储器中的实现（C）数据的存储结构分为线性结构的非线性结构（D）数据的存储结构对数据运算的具体实现没有影响以下关于数据的逻辑结构的叙述中，不正确的是_______。（A）数据的逻辑结构是数据间关系的描述（B）数据的逻辑结构抽象地所映数据元素间的逻辑关系（C）数据的逻辑结构具体地反映数据在计算机中的存储方式（D）数据的逻辑结构分为线性结构和非线性结构与数据元素本身的形式、内容、相对位置、个数无知的是数据的_______。（A）存储结构（B）存储实现（C）逻辑结构（D）运算实现下列选项中叙述错误的是_______。（A）数据结构是指相互关联的数据元素的集合（B）数据结构就是指带有结构的数据元素的集合（C）数据的逻辑结构与它们的计算机中的存储位置无关（D）研究数据结构的主要目的是如何更好地对数据进行排序下列叙述中正确的是______。（A）线性表是线性结构（B）栈与队列是非线性结构（C）线性表是非线性结构（D）二叉树是线性结构下面不是非空线性表的结构特征的是______。（A）有且只有一个根结点，它无前件（B）有且只有一个终端结点，它无后件（C）除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件（D）线性表中结点的个数n称为线性表的度顺序存储结构______。（A）仅适合于静态查找表的存储（B）仅适合于动态查找表的存储（C）既适合于静态又适合于动态查找表的存储（D）既不适合于静态又不适合于动态查找表的存储13．下列关于栈的叙述中正确的是_____。（A）在栈中只能插入数据（B）在栈中只能删除数据（C）栈是先进先出的线性表（D）栈是先进后出的线性表14．若进栈序列为1，2，3，4，假定进栈和出栈可以穿插进地，则可能的出栈序列是______。（A）2，4，1，3（B）3，1，4，2（C）3，4，1，2（D）1，2，3，415．设计一个判断表达式中左右括号是否配对的算法，采用_____数据结构最佳。（A）队列（B）堆栈（C）二叉树（D）链一16．设在栈中，由顶向下已存放元素c,b,a,在第4个元素d入栈之前，栈中元素可以出栈，试问d入栈前后，不可能的出栈序列是______。（A）dcba（B）cbda（C）cadb（D）cdba17．如果进栈序列为e1、e2、e3、e4，则可能的出栈序列是______。（A）e3e1e4e2（B）e4e2e3e1（C）e3e2e1e4（D）e3e4e1e218．若进栈序列为3，5，7，9，进本过程中可以出栈，则______不可能是一个出栈序列。（A）7，5，3，9（B）9，5，7，3（C）9，7，5，3（D）7，5，9，319．数组Q[0…n-1]作为一个环形队列，f为当前队头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数总小于n，队列中元素的个数是______。（A）r-f（B）n+r-r（C）n+r-f（D）(n+r-f)modn20．设有栈S和队列Q，其状态为空，元素a1，a2，a3，a4，a5，a6依次入栈，出栈的元素则进入队列Q，若6个元素出列的顺序是a2，a3，a4，a6，a5，a1，则栈的容量到少是______。（A）6f（B）4（C）3（D）221．以下关于队列的叙述中______是不正确的？（A）队列的特点是先进先出（B）队列既能用顺离方式存储，也能用链接方式存储（C）队列适用于二叉数对称序周游算法的实现（D）队列适用于树的层次次周游算法的实现22．以下______不是队列的基本运算。（A）从队尾插入一个新元素（B）从队列中删除第I个元素（C）判断一个队列是否为空（D）读取队头元素的值23．用链表表示线怀表的优点是_____。（A）便于插入和删除操作（B）数据元素的物理顺序与逻辑顺序相同（C）花费的存储空间较顺序存储少（D）便于随机存取24．在单链表中，增加头结点的目的是_____。（A）方便运算的实现（B）使单链表至少有一个结点（C）标识表结点中首结点的位置（D）说明单链表是线性表的链式存储实现25．线性表若采用链表存储结构时，要求内存中可用存储单元的地址_____。（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续不连续都可以26．以下关于链式存储结构的叙述中，_____是不正确的。（A）结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构（B）逻辑上相邻的结点物理上不必相邻（C）可以通过计算直接确定第I个结点的存储地址（D）插入、删除运算操作方便，不移动结点27．线性表的顺序存储结构和线性表的链式存储结构分别是_____。（A）顺序存取的存储结构、顺序存取的存储结构（B）随机存取的存储结构、顺序存取的存储结构（C）随机存取的存储结构、随机存取的存储结构（D）任意存取的存储结构、任意存取的存储结构28．关于线性链表，下面描述错误的是_____。（A）为了克服线性链表中，空表和非空表的运算统一，可以采取循环链表的结构（B）循环链表从任意一个结点都能扫描到整个链表（C）在循规蹈矩环链表中最后一个结点的指针域不为空（D）循环链表订解决了线性链一的最后一个结点的指针域为空的问题。29．下列属于非线性表结构的是_____。（A）树（B）队列（C）栈（D）线性表30．二叉树属于_____结构。（A）非线性（B）线性表（C）线性（D）网状31．设二叉树根结点的层次为0，在深度为5的满二叉树中，叶子结点的个数为_____。（A）32（B）31（C）16（D）15p[32．设一棵二叉树中，度为1的结点数为9，则该二叉树木叶结点的数目为_____。（A）10（B）11（C）12（D）不确定33．在下列关于二叉树的叙述中，正确的是_____。（A）在二叉树中，任何一个结点的度都是2（B）二叉树的度为2（C）在二叉树中至少有一个结点的度是2（D）一棵二叉树的度可以小于234．设一棵完全二叉树共有500个结点，则在该二叉树中有_____个叶子结点。（A）248（B）249（C）250（D）25135．设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_____。（A）349（B）350（C）511（D）35136．二叉树的前序遍历和中序遍历如下。前序遍历：ABDFHCEGI中序遍历：BFHDAEIGC该二叉树根的右子树的根是_____。（A）N（B）F（C）E（D）C37．在先左后右的原则下，桶据访问桶结点的次序，二叉树的遍历可以分为三种：前序遍历、_____遍历和后序遍历。（A）左序（B）中序（C）右序（D）上序A38．下列二叉树的中序遍历结果为_____。ACCBBFEDFED（A）ABCDEF（B）DBEAFC（C）ABDECF（D）DEBFCA39．已知二叉树的后序遍历是dabec，中序遍历序列是debac,它的前序遍历序列是_____。（A）acbed（B）decab（C）deabc（D）cedba40.列不必使用顺序查找技术的是____。（A）无序线性表（B）顺序存储的有序线性表（C）采有了链式存储结构的有序线性表（D）二叉树41．设有100个结点的顺序存储有序线性表，有二分法查找时，最大比校次数是____。（A）25（B）50（C）10（D）742．已知一个有序表（13，20，25，37，48，58，61，78，83，90，101），当二分查找值为48的元素时，____次比较后查找成功。（A）1（B）2（C）3（D）443．设有一个已按各元素的值排好序的顺序表（长度大于2），现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是_____。s=b（B）s>b（C）s<b（D）s>=b44．设待排序关键码序列为（25，18，9，33，67，82，53，95，12，70），要按关键码值递增的顺序，采取以第一个关键码为分界元素的快素排序法，第一趟完成后关键码95被放到了第_____个位置。（A）7（B）8（C）9（D）1045．排序的重要目的是为了以后对已排离的数据元素进行_____。（A）打印输出（B）分类（C）查找（D）合并46．对以下序列{22，86，49，12，30，65，35，18}进行排序，排序过程如下：①{22，86，49，12，30，65，35，18}②{18，12，22，49，30，65，35，86}③{12，18，22，35，30，49，65，86}④{12，18，22，30，35，49，65，86}则可以认为使用了_____排序方法。（A）选择排序（B）冒泡排序（C）快速排序（D）插入排序47．在最坏的情况下，假设线性表的长度为n，则冒泡排序的时间复杂度为_____。（A）n（B）n/2（C）n(n+1)/2（D）n(n-1)/248．用冒泡排序算法对数据：2，37，42，19，27，35，56，44，10进行从小到大排序。在将最大的数“沉”到最后时，数的顺序是_____。（A）2，37，42，27，19，35，44，10，56（B）2，37，42，19，27，35，10，44，56（C）2，37，19，27，35，42，44，10，56（D）2，10，19，27，35，37，42，44，5649．用快速排序法对下列关键字序列进行排序，速度最慢的是_____。（A）{7，11，19，23，25，27，32}（B）{27，25，32，19，23，7，11，}（C）{3，11，19，32，27，25，7}（D）{123，27，7，19，11，25，32}50．对下面4个序列用快速排序的方法进排序，以序列的第一个元素为基础进行划分。在第一趟划分过程中，元素移动次数最多的序列是_____。（A）827，75，70，16，10，90，68，23（B）23，10，16，70，82，75，68，90（C）70，75，68，23，10，16，90，82（D）70，75，82，90，23，16，10，6851．快速排序方法在_____情况下最不利于发挥其长处。（A）被排序的数据量太大（B）被排序数据中含有多个相同值（C）被排序数据已基本有序（D）被排序数据的数目为奇数填空题算法基本特征是可行性、确定性、_____和拥有足够的情报。在工程中，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法就是通过对问题分析，找出解决问题的线索，然后沿着这个线索试探，如果不成功，就逐步回退，换别的路线再进行试探。这种方法称为________。算法的________是指执行算法所需要的计算工作量。算法的________是指执行这个算法所需要的内存空间。在算法的基本特征中，算法的________是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。数据结构是相互之间存在的一种或多种特定的关系的数据元素的集合，它包括3个方面的内容，分别是________、________和算法。数据结构是一门研究非数值计算的程序设计问题中计算机的________以及它们之间的关系和运算等的学科。线性表中结点的个数n称为线性表的________。线性表中所有元素的所占的存储空间是________的。10．字符a、b、c、d依次通过一个栈，按出栈的先后次序组成它符串，至多可以组成________个不同的字符串。11．组O[n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中有元素个数的公式为________。12．对于栈只能在________插入和删除元素。13．向栈中压入元素的操作是________。14．对栈进行退栈时操作是________。15．在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有________个元素。16．在一个循环队列中，队首指针指向队首元素的________。17．从特环队列中删除一个元素时，其操作是________。18．在具有n个单元的循环队列中，队满时共有________个元素。19．在线性表的顺序存储中，元素之间的逻辑关系是通过相邻位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过________决定的。20．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用顺序存储结构为宜；相反，当经常进行插入和删除操作时，则采用________存储结构为宜。21．用线性表表示线性表的优点是________。22．在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的________即可。23．循环链表的头指针指向________结点。24．循环链表中至少有________个结点存在。25．在计算机中使用树来表示臬术运算符时，运算对象中的单变量均为________结点。26．树最适保用来表示元素之间具有________关系的数据。27．在一棵二叉树中，只有度为0的结点和度为2的结点。度为0的结点的个数为n，度为2的结点的个数为m，则有n=________(用m表示)。28．设一棵完全二叉树共700个结点，则在该二叉树中________有个叶子结点。29．设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最少结点数为________。30．在完全二叉公款喘序存储中，若结点I有左子树，则其左子树是结点________。31．设树T的度为4，其中度为3和4的结点个数为1，则T中叶子结点的个数是________。32．高要结点的层数为1，深度为h的一棵二叉树上只有度为0的和度为2的结点，则此类二叉树中所包含的结点数至少为________。33．按照二叉树的定义，具有3个结点的二叉树有________种。34．深度为5的二叉树最多有________个结点。35．设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为________。36．如果一棵二叉树中任一结点的值都大于其左子树中所有结点的值，且小于其右子树中所有结点的值，那么这棵树叫做二叉排序树。在一棵二叉排序树中，按________周游得到的结点序列是一个有序序列。37．顺序查找法的平均查找长度为________。38．设一线形表中有a1，a2，……a500，500个元素按递增顺序排序列，则用二分法杳找给定值K，最多需要比较________次。39．设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较________次。40用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：25，84，21，47，15，27，68，35，2020，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，815，20，21，25，27，35，47，68，84则所采用的排序方法是________。41．在最坏情况下，冒泡排序的时间复杂度为________。42．对n个记录的文件进行快速排序，执行的时间复杂度为________。43．设有关键码序列（17，8，3，25，16，1，13，19，18，4，6，21），要按关键码值递增次序排序，用初始增量为4的希尔排序法，一趟扫描的结果是________。44．在排序方法中，从末排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入排序序列的正确位置的方法，称为________。45．在堆排序和快速排序中，若原始记录接近正序或反序，则选用________。46．在堆排序和快速排序中，若原始记录无序，则选用________。47．在插入和选择排序中，若初始数据基本正序，则选用________。48．排序方法中，人未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为________。2.2.2过关练习题解析与答案选择题1．【解析】计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法，计算机算法不同于人工处理的方法。例如对数值进行计算时，计算机就受到运算精度的限制，又例如在解快实际问题时的数学公式是正确的，而按照此数学公式设计的计算过程在计算系统上不一定能执行。【答案】A2．【解析】程序可能作为算法的一种描述，但算法不等于程序，也不是计算方法，所以选项B描述错误。归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般关系，但由于在归纳的过程中不可能对的有的情况进行例举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明人，所以选项C、D描述都错误。【答案】A3．【解析】请详见本章“考点破解2”。【答案】C4．【解析】请详见本章“考点破解2”。【答案】D5．【解析】数据结构设计了数据元素的逻辑结构和与之相应的存储结构，它描述系统的静态特性。【答案】B6．【解析】数据的存储结构的定