第2章数据结构和算法.doc

《第2章数据结构和算法.doc》由会员分享，可在线阅读，更多相关《第2章数据结构和算法.doc（194页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第2章 数据结构和算法本章主要考察的内容是：1 .算法的基本概念(1) 算法的定义(2) 算法的特点(3) 算法的复杂度2数据结构的基本概念3. 线性结构与非线性结构(1) 线性表及其顺序存储结构(2) 栈及其基本运算(3) 队列及其基本运算(4) 线性链表4. 树的基本概念和特征(1) 二叉树的基本概念及其特性(2) 二叉树的遍历5. 查找技术(1) 顺序查找 (2) 二分法查找6. 排序技术(1)交换类排序法(2)插入类排序法(3)选择类排序法历年的全国计算机等级考试的笔试中，数据结构和算法部分的分值约占10-15%，本章历年的考题分布情况如表2-1所示：表2-1 程序设计基础部分历年考题

2、分数分布表考点内容2004.092005.042005.092006.042006.09小计算法的定义22算法的特点22算法复杂度242210栈、队列22 4210数据结构22228树的基本概念和特征22228查找技术424414排序技术2226合计101412101460由表2-1可知，在历年的笔试考试中，考试的关键点主要是算法、数据的存储结构、树和排序。2.1.1算法考点1:算法的基本概念所谓算法是指对解题方案准确而完整的描述。如果一个问题可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结构，则称这个算法是可解的。算法既不是程序，也不是解题方法。程序可以作为算法的一种

3、描述，由于在编写程序时要受到计算机系统运行环境的限制，因而，程序的编制一般不会优于算法的设计。算法的基本特征包括以下几点。可行性。确定性。算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。在2005年4月的考试中以选择题的形式考查了该考点内容。今年针对该考点出题的几率较高，题型可能是选择题也可能是填空题，考生应重点掌握该考点的相关概念。 有穷性。算法必须能在有限的时间内做完，能在执行有限个步骤后终止，这包括合理的执行时间的含义。 足够的情报。(2)以下两个基本要素。对数据的运算和操作。算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。一个

4、计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。在一般的计算机系统中，基本操作包括算术运算、逻辑运算、关系运算和数据传输。算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以及顺序、选择、循环3种基本控制结构组合而成。算法设计的基本方法包括列举法、归纳法、递推、递归、递推技术、回溯法。例2.1 (2005年4月填空题第5题)问题处理方案的正确而完整的描述称为_。【解析】 所谓算法是指对解题方案的准确而完整的描述。【答案】 算法例2.2 在

5、计算机中，算法是指_。（A）查询方法 （B）加工方法（C）对解题方案的准确而完整的描述（D）排序方法【解析】请参照配音“考点破解1” 说明。【答案】C例2.3 算法一般都可以用哪几种控制结构组合而成_。（A）循环、分支、递归 （B）顺序、循环、嵌套（C）循环、递归、选择 （D）顺序、选择、循环【解析】请参照本章“考点破解1”的说明。【答案】D例2.4 在下列选项中，哪个不是一个算法应该具有的酝酿特征_。（A）确定性 （B）可行性 （C）无穷性（D）拥有足够的情报【解析】算法的基本特性能般包括了确定性、可行性、有穷性和拥有足够的情报。【答案】C例2.5 下面关于递推和递推算法描述正确的是_。（A

6、）不会出现既可以归纳为递推算法，又可以归纳为递归算法的实际问题（B）递归算法和递推算法基本相同（C）递归算法执行效率比递推算法低（D）递推算法分为直接递推算法与间接递推算法【解析】从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法称为递推算法，递推算法实际上属于归纳法。人们为了降低问题的复杂度，一般总是将问题逐层分解，最后归纳为一些简单的问题，这个过程一直做下去，直到出现最简单的问题为止。有些实际问题，既可以归纳为递推算法，也可以归纳为递归算法，但递推和递归实现的方法大不一样。递推是从初始条件开始，逐次推出所要求的结果，而递归则是算法本身到达递归边界的。递归算法比递推简单，但递归

7、算法执行效率较低。【答案】C自测题可用“2.2过知精练”中的选择题第12题以及填空题12题进行自测。考点2 :算法复杂度算法的复杂度主要包括时间复杂度和窨复杂度。1. 算法的时间复杂该考点的命题重点是“算法复杂度”的概念，出题类型以填空题居多。在2004年9月、2005年4月和2005年9月的考点中都考核了本考点的相关知识。考生必须掌握该考点的相关概念。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来试题，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量= (n)其中n是问题的规模。在同一问题规模下，如果算法执行所需的基本运算次数取决于某

8、一特定输入时，可以用以下两面三刀种方法来分析算法的工作量。 平均性态分析（Average Behavior）这是指用各种特定输入的基本运算次数的带权平均值来度量算法的工作量。设是所有可能输入中的某个特定输入，p()是出现的概率（即输入为的概率），t()是算法在输入为时所所的酝酿运算次数则算法的平均性态定义为：A(N)=p()t()XDn其中，Dn表示当规模为n时，算法执行时所有可能输入的集合。其中，Dn表示当规模为n时，算法执行时所有可能输入的集合。 最坏情况复杂性（Worst-Case Complexity）。这是指在规模为n时，算法所执行的基本运算的最大次数。它定义为：W(n)=maxt(

9、)Dn显然，W（n）的计算要比A（n）的计算方便得多。由于W（n）实际上是给出了算法工作量后个上界，因此，它比A（n）更且有实用价值。2算法的空间复杂度一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所上的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序势利过和中的工作单元以及某种数结绝民需要的附加存储窨。如果客外空间量相寻于问题规模来说是常数，则称该算法是原地（In Place）工作的，在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。例题精解例2.6

10、（2005年9月填空题第2题）算法复杂度主要包括时间复杂度和复杂度。【解析】请详见“考点破解2。”【答案】空间例2.7（2004年9月填空题第1题）如果一个算法的额外空间量相对于问题规模来说是常娄，刚称该算法是工作的。【解析】请详见本章“考点破解2。”【答案】原地自测题可用“2.2过关精练”中的选择题第34题、填空题第34题进行自测。2.1.2数据结构的基本概念考点3:数据结构的基本概念数据结构是指相互有关联的数据据元素的集合。该考点的相关试题在2005年9月和2005年4月的考试中均有出现，考生需要重点掌握。数据结构是一门研究在非数值计算的程序设计问题中，计算机的数据元素以及它们之间的关系和

11、运算的学科。数据结构作为计算机的一门学科，主要研究以下3个方面的问题：1 数据的逻辑结构所谓数据的逻辑结构，是指所是非曲直数据元素之间逻辑关系的数据结构。它包括两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D 中各数据元素之间的前后 件关系，通常记为R。于是，一个数据结构可以表示成B=(D,R),其中B表示数据结构。数据的逻辑结构包含：表示数据元素的信息；表示各数据元素之间的前后件关系。2 数据的存储（数据的物理结构）所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式（也称数据的物理结构）。一般来说，一种数据的逻辑结构根据需要可以表示为多种存储结构，常用 的

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

13、2004年9月选择题第1题）下面叙述正确的是。(A) 算法的执行效率与数据的存储结构无关 (B) 算法的窨复杂度是指算法程序中指令（或语句）的条数据(C) 算法的有穷性是指算法必须能执行有限个步骤之后终止(D) 以上三种描述都不对【解析】采用不同的数据存储结构，数据昝的效率是不同的。【答案】C例2.11数据的逻辑结构包含了表示数据元素的信息和。【解析】请详见本章“考点破解3”【答案】表示各数据元素之间的前后关系例2.12数据的结构包数据的结构和数据的存储结构。【解析】请参照本章“考点破解2”相应说明解答本题。【答案】逻辑自测题可用“2.2过关精练”中的选择题第59题、填空题第57题进行自测。该

14、考点命题重点是线性结构和线性表的概念，试题类型以选择为主。在2005年9月和2004年9月的考试中都考查过该考点，因而考生应重点掌握该考点的相关概念。考点4 :线性结构与非线性结构根据数据结构中各元素之间前后件关第的复杂性程度，一般将数据结构分为线性表和非线性表。如果一非空的数据结构满足下列两个条件，则称该数据结构为线性结构（线性结构又称为线性表）。 有且只有一个根结点。 每一个结点最多有一个前件，也最多有一个后件。在一个线性结构中插入或删除任何一个结点后还就是线性结构。如果一个数据结构不是线性结构，刚称之为非线性结构。例题精解例2.13（2005年9月选择题第4题）下列叙述中正确的是。(A)

15、一个逻辑数据结构只能是一种存储结构(B)数据的逻辑结构属于线性结构，存储结构属于非线怀结构(C)一个逻辑数据结构可以有多个存储结构，且各种存储结构不影响数据处理的效率 (D)一个逻辑数据结构可以有多个存储结构，且各种存储结构影响数据昝的效率【解析】请详见本章“考点破解3” 和“考点破解4”【答案】D例2.14（2004年9月选择题第2题）以下数据结构中不属于线性数据结构的是。(A)队列 (B)线性表 (C)二叉树 (D)栈【解析】二叉树可以有多个后件，所以二叉树不是线性表。【答案】C自测题可用“2.2过关精练”中的选择题第10题进行自测。2.1.3 线性表及其顺序存储结构考点5 :线性表的基本

16、概念该考点的命题重点是线性表的基本结构特征，近几次考试中还没有考查过该考点。线性表由一组数据元素构成，数据元素在线性天中的位置只取决于它们自己的序与，即数据元素之间的相对位置是线性 的。非空线性表具有如下 一些结构特征：有且只有一个根结点a1 ,它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的数n称为线性表的长度。当n=0时，称为空表。例题精解例2.15下列关于线性表的叙述不正确的是。(A)矩形是一个线怀表(B)在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成(C)在线性表中，除了第一个元素外，其他元

17、素有且只有一个前件 (D)线性表中所有元素有且只有一个后件【解析】在线性表，终点是没有后件的，D选项叙述错误。【答案】D自测题可用“2.2过关精练”中的选择题第11题以及填空题第8题进行自测。考点6:线性表顺序存储的特点及远处在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。线性表的顺序存储结构具有以下两个基本特点：该考点至今没有考查过，但不排除针对此考题出题的可能。请着重掌握线性表顺序存储的两个基本特点。线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的线性存储结构下，可以对线性表进行插入、删除、查找 、排序、分解、合并、

18、复制和逆转等操作。例题精解例2.16 在下面关于线性表的叙述中，选出正确的一项。(A) 线性表的每个元素都有一个直接前趋和直接后继(B) 线性表中至少有一个元素(C) 线性表中的元素必须按递增或递减的顺序排列(D) 除第一个元素和最后的个元素外，每个元素都有一个直接前趋和直接后继【解析】线性表的头结点没有前趋结点，尾结点没有后继结点，所以选项A错误，选项D正确。没有元素的线性表称为空表，所以选项B错误。根据线性表的定义可在线性表中的元素不一定是有序排列的，所以先项C也错误。【答案】D例2.17 若某线性表中最常用的操作是取第n 个元素的前趋元素，则采用存储方式最节省时间。（A） 顺序表（B）单

19、链表 （C）双链表 (D)单环链表【解析】在线性表的顺序存储结构中，其前后件两个元素在存储空间中最紧邻的，且前件元素一定存储在后件元素的前面。在第I个元素的前趋元素定位上，采用顺序表的存储方式最节省时间。【答案】A自测题可用“2.2过关精练”中的选择题第12题以及填空题第9题进行自测。2.1.4 栈及其基本运算考点7 :栈该考点的命题重点是栈的概念与栈的基本运算，出题类型以选择题主为。在2005年的两次考试中都考核了该考点，考生需要重点掌握。栈（stack）是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，

20、也是最先能被删除的元素；栈底元素总是星先被插入的元素，也是最后能被删除的元素即栈是按照“先进后出”（FILO-First In Last Out）或“后进先出”（LIFO-Last In First Out）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。栈有以下3种基本运算。栈运算：插入元素。栈运算：删除元素。栈顶元素：将栈顶元素赋给一个指定的变量，些时指针无变化。例题精解例2.18（2005年9月选择题第3题）下列关于栈的描述正确的是。（A） 在栈中只能插入元素而不能删除元素（B） 在栈中只能删除元素而不能插入元素（C） 栈是特殊的线性表，只

21、能在一端插入或删除元素（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

22、（D）DCBEA【解析】栈（Stack）是限定在一端进行插入与删除的本性表，出栈操作只能是“先进后出”。本题中，如果没有E进栈，栈原来元素的出栈面序只能是D、C、B、A。这样包括第5个元素E在内的出栈顺序可以为EDCBA、DECBA、DCEBA、DCBEA、DCBAE共5种出栈序列。【答案】D自测题可用“2.2过关精练”中的选择题第1318题以及填空题第1214题进行自测。考点8 :队列该考点的命题重点是队列与循环队列的概念，以及队列的基本运算。出题类型以选择题或填空题。在2005年9月的考试中以填空题考核了该考点。队列（queue）是指允许在一端（队尾）进行插入，而在另一端（队头或排头）进行

23、删除的线性表。通常，指向队尾的指针称为队尾指针（rear），指向排头的指针称为排头指针（front）。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。在实际应用中，队列的顺序存储结构一般采用循环队列的形式，所谓盾环队列，就是将队列存储空间最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。循环队列运算有以下两类：人队运算：从队尾插入一个元素；退队运算：从队头删除一个元素。例题精解例2.21（2005年9月填空题第5题）数据结构分为逻辑结构和存储结构，循环队列属于结构。【解析】循环队列是从其存储结构上来说的。从其定义上可知，循环队列属于存储结构。【答案】存储 或

24、物理例2.22 下列关于队列的叙述中正确的是。（A）在队列中只能插入数据 (B)在队列中只能删除数据（C）队列是先进先出的线性表 （D）栈是先进先出的线性表【解析】队列是先进先出的线性表，栈是先进后出的线性表，栈和队列是两个不同的存储结构。【答案】C例2.23 栈和队列的共同点是。（A）都是先进后出 (B)都是无进先出（C）只允许在端点处插入和删除元素 （D）没有共同点【解析】栈为先进后出，队列为先进先出，因此选项A、B都错误。根据本章“考点破解7”和“考点破解8”关于栈和队列的定义可知，C选项正确。【答案】C例2.24 对于队列只能在分别插入和删除元素。【解析】队列（queue）是指允许在一

25、端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，。通常有一个称为队尾指针（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【解析】队列中允许在一端（队尾）进行插入，而在另一端（队头或排头）进行删除。在队列的这种结构中，最先插入的元素将最先能够疲删除，反之，最后插入的元素将最后 才能被删除。也就是说

26、在队列中要“先进先出”，所以本题中队列的输出序列是1，2，3，4。【答案】B自测题可用“2.2过关精练”中的选择题第1922题、填空题第1418题进行自测。2.1.5 线性链表考点破解9 线性链珍基本概念1 线性链表该考点的命题重点是线性链表的存储特点，在2005年4月的考试中考查了线性表的基本特点。该考点是本章重点，请掌握相关概念。线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一个小块占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系，需要将存储空间中的

27、每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点，称为指针域。一般来说在线性表的链式存储结构中，各数据结点的存储序号是不边续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。当线性链表每一个结点只有一个指针哉时，由这个指针只能找到后件结点，但不能找到前件结点。对应的线性链表中的每个结点都设置两个指针，一个称为左指针（Llink）用以指向其前件结点，另一个称国右指针（Rlink），用以指向后件结点。这样的线性表称为双向链表。2 带栈的队列与栈类似，队列也是线性表，也可以采用链式存储结构。例题精解例

28、2.26（2005年4月选择题第5题）下列对线性链表描述正确的是。（A） 存储空间不一定连续，且各元素的存储顺序是任意的（B） 存储空间不一定连续，且前件元素一定存储在后件元素的前面（C） 存储空间必须连续，且前件元素一定存储在后件元素的前面（D） 存储空间必须连续，且各元素的存储顺序是任意的【解析】一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系也不一致，各元素之间的前后关系是由各结点的指针来指示的。【答案】A例2.27 在下面关于线性表的叙述中，选取出正确的一项。（A） 采用链接存储的线性表，必须占用一片连续的存储单元（B） 采用顺序存储

29、的线性表，便于进行插入和删除操作（C） 采用链接存储的线性表，不必占用一片连续的存储单元（D） 链接和顺序存储线性表，都便于进行插入和删除操作【解析】一般来说在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，所以选项A叙述错误。采用顺序存储的线性表不便于进行插入和删除操作。这是链接与顺序存储器的不同，链接便于插入、删除。【答案】C自测题可用“2.2过关精练”中的选择题第2327题以及填空题第1922题进行自测。考点10: 线性链表基本运算线性链表的基本运算主要有：插入、删除、合并、分解、逆转、复制、排序和查找。该考点至今未考查过，其内

30、容难度较大，读者了解相关的概念即可。例题精解例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;pheadInfo oinfoinfoqinfo图2.2 例2.28图【解析】根据题意需要从指针p指向的结点的link 指针外断开，把p处的link指针指

31、向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中两个值已经相同，无法满足题意的要求。【答案】

32、C考点11: 循环链表及其基本计算该考点的命题重点是循环链表的概念，试题类型可能是选择题主为或者填空题，近几次考试中都没有考到该考点的相应内容。循环链表的结构具有以下两个特点：在循环链表中增加了一个表头结点，其数据域为任意或者可根据需要来设置，指针域指向线性表的第一个元素的结点，循环链表 头指针指向表头结点。循环链表中最后一个结点的指针域不为空，而是指向表头结点。即在循环链表中，所有结点的掼针构成了一个环状状链。例题精解例2.29循环链表的主要优点是。A） 不再需要头指针了（B） 已知某个结点的位置后，能够容易找到它的直接前趋（C） 在进行插入、删除运算时，能更好地保证链表不断开（D） 从表中

33、任一结点出发都能扫描到整个链表【解析】 循环链表中，所有结点的指针构成了一个环状链，这种结构的主要优点是从表中任一结点出发都能扫描到整个链表。【答案】D自测题可用“2.2过关精练”中的选择题第28题以及填空题第2324题进行自测。考点12: 树的基本概念和特征树(tree)是种简单的非线性结构,所有元素之间 具有明显的层次特性.在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件的结点称为叶子结点。该考点的命题重点在于树的基本概念和如何在计算机中使用树结构表示算术表达式。出题类型可以为选择题或

34、填空题，该考点还没有考核过。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树是一种层次结构，根结点在第1层，同一层上民有结点的子结点都有下一层。树的最大层次称为树的深度。在计算机中，可以用树结构来表示算术表达式。用树来表示算术表达式的原则如下：表达式中的每一个运算符在树中对应一个结点，称为运算符结点；运算符的每一个运算对象在树中为该运算符结点的子树（在树中的喘序为从左到右）；运算对象中的单变量均为叶子结点。例题精解例2.30树最适合用来表示。（A）有序数组元素 （B）无序数组元素（C）元素之间具有分支层次关系的数据 (D)元素之间无联第的数据【解析】树是一

35、种简单的非线性结构，在树的数据结构中，所有数据元素之间的关系具有明显的层次特性，是一种层模型。层次模型是最早发展起来的数据库模型。【答案】C自测题可用“2.2过关精练”中的选择题第29题以及填空题第2527题进行自测。该考点的命题重点是二叉树的结点计算。命题类型可为选择题或者填空题。在2005年的两次考试中以及2004年的考试中都考核了该考点，考生需要重点掌握。考点13 : 二叉树的基本概念及其特性二叉树的定义是一个递归的定义，其根的左子树和右子树又是二叉树。最简单的二叉树是空二叉树。二叉树有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树二叉

36、树有以下基本性质。在二叉树的第k 层上，最多有2k-1(k1)个结点；深度为m的二叉树最多有2m-1个结点；在任意一个二叉树中，度为0的结点（即叶子结点）总是比度为2的结点一个；具有n 个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。完全二叉树和满二叉树。完全二叉树是指除最后一层外，每一屋上的结点数均达到阳大值，在最后一层上只缺少右边的若干结点。完全二叉树还具有以下两个性质：具有n个结点的完全二叉树的深度为log2n+1；设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号（k=1,2n），有以下结论：l 若

37、k=1,则编号为根结点，它没有父结点；若k1，则该结点的父结点编号为INT（k/2）;l 若2kn则编号为k的结点的右子结点编号为2k；否则该结点无子结点（也无右子结点）；l 若2k+1n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。满二叉树是指除最后一层外，每一层上的所有结点有两个结点，则在第k层上有2k-1,深度为m满二叉树有2m-1个结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。例题精解例2.31（2005年9月填空题第4题）一棵二叉树第6层（根结点为第1层）的结点数最多为个。【解析】一棵二叉树的根结点为第1层，那么这棵二叉树第

38、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(k1)个结点”，在二叉树的第5层上的最多结点数为24=16【答案】B自测题可用“2.2过关精练”中的选择题第3035题以及填空题第28

39、34题进行自测。考点破解14 二叉树的遍历二叉树的遍历是指不重复地访问二叉树的所有结点。目前为止还没有针对该考点的试题材。请考生适当了解该考点的内容。二叉树的遍历分为下面三种：前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；中序遍历（LDR）,首先遍历左子树，然后访问根结点，最后遍历右子树；后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。例题精解例2.34 在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中，所有叶子结点的先后顺序。（A）都不相同 （B）完全相同（C）先序和中序相同，而与后序不同 （D）中序和后序相同，而与先序不同【解析】根据本章

40、“考点破解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。【答案】BFE CBHAHDHHHPHGH图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、

41、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的位置应

42、为新子村的根，B、D就为C的左右子树成员；同时在中序序列中以B、C、D顺序排我，则可判断出B为C的左子树，D为C的右子树。那么整个二叉树的结构应如图所示2.4所示。EHAHGHFHCHBHDH图2.4 例2.35图根据此图可得出该二叉树结点的后序序列为B、D、C、A、F、G、E。【答案】A自测题可用“2.2过关精练”中的选择题第3639题以及填空题第3536题进行自测。2.1.7 查找技术考点15: 顺序查找该考点的命题重点是顺序查找的技术指标，试题类型以填空题为主。在2005年4月曾对该考点进行了考查。顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的

43、第一个元素开始，集资将线性表中的元素与被查元素进行比较，相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。在最坏情况下，顺序查找需要比较n次。在下列情况下只能使用顺序查找：如果线性表为无序表（即表中元素的排列是无序的），则不管是顺充存储结构还是链式存储结构，都只能使用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。例题精解例2.36 (2005年4月选择题第4题)对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为。（A）log2n （B）n/2 （C）n （D）n+1【解析】对长度为n

44、的线性表，在最坏情况下，需要查找的元素不在线性表中或者是线性表的最后一个元素，些时需发的比较次数为n.【答案】C自测题可用“2.2过关精练”中的选择题第40题以及填空题第37题进行自测。该考点的命题重点是二分法的查找方法，出题类型可能是选择题也可能是填空题。在2005年9月的考试中有一道相关试题。考点 16 : 二分法查找二分法查找只适用于顺序存储的有序表。在些所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n 次，而顺序查找需要比较n次。例题精解例2.37 (2005年9月选择题第2题)下列数据结构中，能用二分法进行查找的是。（A）顺