第11章自学辅助讲义

1、2012年3月全国二级 公共基础 内部教程(2012年 3 月打印版) 当前版本：2012-03-01- 4 -第1章 算法与数据结构 算法的基本概念 1、算法：是指解题方案的准确而完整的描述。 (1) 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述，但程序通常还要考虑程序运行时的环境限制等。 (2) 算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。 2、算法的基本特征： (1) 可行性，例如 10 +1-10 的问题 (2) 确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不

2、允许有多义性；例在特殊情况时，数学公式是正确的，但计算机就是无法操作。 (3) 有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。例如 1/3 的无理数问题。 (4) 拥有足够的情报。所有的各种可能情况都要考虑到。 3、一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 (1) 算法的时间复杂度是指执行算法所需要的计算工作量，可以执行算法的过程中所需要的基本运算的执行次数来度量。分析算法工作量的方法有：平均性态分析、最坏情况分析。 (2) 算法的空间复杂度是指执行这个算

3、法所需要的内存空间。主要包括：算法程序所占的空间；输入的初始数据所占的空间；算法执行过程中所需要的额外空间。 真题分析 【真题 1】 算法的有穷性是指_。 A)算法程序的长度是有限的 B)算法只能被有限的用户使用 C)算法程序的运行时间是有限的 D)算法程序所处理的数据量是有限的 解析： 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。答案：C 【真题 2】 问题处理方案的正确而完整的描述称为_【5】_。 （2005 年 4 月）解析： 算法是问题处理方案正确而完整的描述。- 5 -答案：算法【真题 3】 算法的空间复杂度是指_。 （2009 年 9 月）

4、A)算法程序中的语句或指令条数 B)算法在执行过程中所需要的临时工作单元数 C)算法在执行过程中所需要的计算机内部存储空间 D)算法所处理的数据量 解析： 算法的空间复杂度是指执行这个算法所需要的计算机内部存储空间（简称内存空间）。答案：C【真题 4】 下列叙述中正确的是_。 （2007 年 3 月）A) 数据的逻辑结构与存储结构是一一对应的 B)算法的时间复杂度与空间复杂度一定相关 C)算法的效率只与问题的规模有关，而与数据的存储结构无关 D)算法的时间复杂度是指执行算法所需要的计算工作量 解析： 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，

5、而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。答案：D 【真题 5】 下列叙述中正确的是_。 （2006 年 9 月）A)一个算法的时间复杂度大，则其空间复杂度必定小 B)三种说法都不对 C)一个算法的空间复杂度大，则其时间复杂度也必定大 D)一个算法的空间复杂度大，

6、则其时间复杂度必定小 解析： 1、时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。 2、人们都希望选择一个既省存储空间、又节省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不适用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾，但是二者不存在必然的联系。答案：B 【真题 6】 算法复杂度主要包括时间复杂度和_【2】_复杂度。 （2005 年 9 月）- 6 -解析： 算法的复杂度主要包括时间复杂度

7、和空间复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间规模。答案：空间 【真题 7】 算法的时间复杂度是指_。 （2010 年 3 月）A) 算法程序中的语句或指令条数 B)算法在执行过程中所需要的基本运算次数 C)算法的执行时间 D)算法所处理的数据量 解析： 算法复杂度包括时间复杂度和空间复杂度，是衡量一个算法好坏的度量。算法的时间复杂度主要是基本运算次数。答案：B Point2：数据结构的定义 出题趋势 考试日期07-909-9出题次数111、数据结构：是指相互有关联的数据元素的集合。 (1) 数据结构研究以下三个方

8、面的问题： 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； 对各种数据结构进行的运算。 研究以上问题的主要目的是为了提高数据处理的效率（一是提高数据处理的速度，二是节省数据处理过程所占的空间。） (2) 数据的逻辑结构反映数据元素之间的逻辑关系，即前、后件关系，分为线性结构（线性表、栈和队列）和非线性结构（树和图）。包含： 表示数据元素的信息； 表示各数据元素之间的前后件关系。 (3) 数据的存储结构，是指数据逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一般来说，一种数据逻辑结构根据需要可以表示

9、成多种存储结构，常用的数据的存储结构有顺序、链接、索引等。 2、数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有顺序、链接、索引等。采用不同的存储结构，数据处理的效率是不相同的。 真题分析 【真题 1】 下列数据结构中，属于非线性结构的是_。 （2009 年 9 月）A)二叉树 - 7 -B)带链栈 C)循环队列 D)带链队列 解析： 线性结构，是最简单最常用的一种数据结构。线性结构的特点是结构中的元素之间满足线性关系，按这个关系可以把所有元素排成一个线性序列，如：线性表、串、栈和队列都属于线性结构。而非线性结构是指在该类结

10、构中至少存在一个数据元素，它具有两个或者两个以上的前件或后件，如树和二叉树等。答案：A 【真题 2】 下列叙述正确的是_。 （2007 年 9 月）A)程序执行的效率只取决于所处理的数据量 B)以上三种说法都不对 C)程序执行的效率与数据的存储结构密切相关 D)程序执行的效率只取决于程序的控制结构 解析： 影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别，其中，链式存储结构的效率要高一些。答案：CPoint3：线性表、线性链表和循环链表 出题趋势 考试日期06-406-909-310-9出题次数11

11、111、如果在一个数据结构中一个数据元素都没有，则称为空的数据结构。根据数据结构中各数据元素之间的前后件关系的复杂程度，分为线性结构与非线性结构。 2、如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性表是一个典型的线性结构。常见的有：线性表，栈，队列，循环队列和线性链表等。 3、不满足线性结构条件的数据结构，就是非线性结构。常见的有：数组、广义表、树、二叉树和图都是非线性结构。 4、在计算机内，线性表的存储结构有两种：顺序存储（称为线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于

12、顺序存储结构。 真题分析 【真题 1】 下列叙述中正确的是_。 （2009 年 3 月）A)循环队列是非线性结构 B)有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 - 8 -C)栈是“先进先出”的线性表 D)队列是“先进后出”的线性表 解析： 主要考查了栈、队列、循环队列的概念，栈是“先进后出”的线性表，队列是“先进先出”的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。循环队列也是线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。答案：B 【真题 2】 数据结构分为线性结构和非线性结构，带链的队列属于

13、 _【5】_结构。 （2006 年 9 月）解析： 数据结构分为线性结构和非线性结构，其中队列属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为带链队列。题目中所说的带链的队列就是指带链队列。无论队列采取哪种存储结构，其本质还是队列，仍属于一种线性结构。因此，本题的正确答案是线性结构。答案：线性【真题 3】 下列叙述中正确的是_。 （2006 年 4 月）A)双向链表是非线性结构 B)只有根结点的二叉树是线性结构 C)线性链表是线性表的链式存储结构 D)栈与队列是非线性结构 解析： 线性链表是线性表的链式存储结构。栈与队列是特殊的线性表，它们也是线性

14、结构；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构；二叉树是非线性结构，而不是线性结构。一个非空的数据结构如果满足下列两个条件： (1)有且只有一个根结点； (2)每一个结点最多有一个前件，也最多有一个后件，则称之为线性结构。答案：C 【真题 4】 下列叙述中正确的是_。 （2010 年 9 月）A)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 B)上述三种说法都不对 C)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 D)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 解析： 可以从存储密度的角度，比较链式存储结构和顺序

15、存储结构的存储空间，所谓存储密度是指结点数据本身所占的存储量除以结点结构所占的存储总量所得的值。这个值越大，存储空间利用率越高。顺序表是静态分配的，其存储密度为 1；而链式存储是动态分配的，其存储密度小于 1。答案：D - 9 -Point4：栈、队列和循环队列 出题趋势 考试日期05-405-906-406-907-307-908-408-909-309-910-310-9出题次数1111112222221、栈（Stack）又称堆栈。 (1) 栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向

16、一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。 (2) 由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（Last In First Out，简称 LIFO）；先进栈的元素必定后出栈，所以又把栈称为先进后出表（First In Last Out，简称 FILO）。 2、队列（Queue）简称队。 (1) 队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作

17、队尾（rear），允许删除的一端称作队首（front）。 (2) 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。 (3) 由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（First In First Out，简称 FIFO）。 3、循环队列。就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。 真题分析 【真题 1】 对于循环队列，下列叙述中正确的是_。 （2009 年 9 月

18、）A)队头指针一定小于队尾指针 B)队头指针可以大于队尾指针，也可以小于队尾指针 C)队头指针是固定不变的 D)队头指针一定大于队尾指针 解析： 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。所以队头指针可以大于队尾指针，也可以小于队尾指针。答案：B 【真题 2】 下列叙述中正确的是_。 （2008 年 9 月）A)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 - 10 -B)循环队列中元素的个数是由队头指针和队尾指针共同决定 C)循环队列有队头和队尾两个指针，因此循环队列是非线性结构 D)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

19、解析： 循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。答案：B【真题 3】 设某循环队列的容量为 50，头指针 front=5(指向队头元素)，尾指针rear=29(指向队尾元素)，则该循环队列中共有_【3】_个元素。 （2008 年 4月）解析： 在循环队列中因为头指针指向的是队头元素的前一个位置，所以是从第6 个位置开始有数据元素，即计算从 6 到 29 之间有多少个元素，所以队列中的数据元素的个数为：29-6+1 = 29-5 = 24。答案：24 【真题 4】 线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的

20、线性表，循环队列是队列的 _【3】_ 存储结构。 （2007 年 9 月）解析： 队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。答案：顺序 【真题 5】 下列对队列的叙述正确的是_。 （2007 年 3 月）A)队列在队尾删除数据 B)队列按“先进先出”原则组织数据 C)队列属于非线性表 D)队列按“先进后出”原则组织数据 解析： 队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数据结构中，最先插

21、入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。答案：B 【真题 6】 一个队列的初始状态为空。现将元素 A,B, C,D, E,F,5,4,3,2,1 依次入队，然后再依次退队，则元素退队的顺序为_【1】_。 （2010 年 3 月）解析： 对于队列来讲，是先进先出。答案：A,B,C,D,E,F,5,4,3,2,1 - 11 -【真题 7】 设某循环队列的容量为 50，如果头指针 front=45(指向队头元素的前一位置)，尾指针 rear=10(指向队尾元素)，则该循环队列中共有_【2】_个元素。 （2010 年 3 月）解

22、析： 这次头指针在尾指针之后，因为是循环队列，所以应该是从 46 到 50，再从 1 到 10 构成了这个队列。答案：15 【真题 8】 下列数据结构中，能够按照“先进后出”原则存取数据的是_。 （2009 年 9 月）A)队列 B)二叉树 C)循环队列 D)栈 解析： 由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以栈被称为后进先出表(Last In First Out,简称 LIFO)；先进栈的元素必定后出栈，所以又把栈称为先进后出表(First In Last Out,简称 FILO)。答案：D 【真题 9】 假设用一个长度为 50 的数组(数组元素的下标从 0 到

23、49 作为栈的存储空间，栈底指针 bottom 指向栈底元素，栈顶指针 top 指向栈顶元素，如果bottom=49，top=30(数组下标),则栈中具有_【1】_个元素。 （2009 年 3 月）解析： 栈底指针到栈顶指针就是当前栈中的所有元素的个数。(注意，此处最容易错误的算成 19)答案：20 【真题 10】 支持子程序调用的数据结构是_。 （2009 年 3 月）A)队列 B)二叉树 C)栈 D)树 解析： 这个部分的知识超过了教材的范围，但考试也考到过。下面的解析很多同学反应不能理解，建议大家记住答案就可以了。 栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保

24、存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。答案：C 【真题 11】 一个栈的初始状态为空，现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是_。 （2008 年 9 月）- 12 -A) ABCDE12345 B) 54321EDCBA C) 12345ABCDE D) EDCBA54321 解析： 栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是EDCBA54321。答案：D 【真题 12】 下列关于栈的叙述正确的

25、是_。 （2008 年 4 月）A) 只能在栈底插入数据 B)不能删除数据 C)栈按“先进先出”组织数据 D)栈按“先进后出”组织数据 解析： 栈是限定在顶端进行数据插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。答案：D 【真题 13】 按“先进后出”原则组织数据的数据结构是 _【4】_ 。 （2006 年 9月）解析： 栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行组织。答案：栈 【真题 14】 按照“后进先出”原则组织数据的

26、数据结构是_。 （2006 年 4月）A)双向链表 B)二叉树 C)队列 D)栈 解析： “后进先出”表示最后被插入的元素最先能被删除。“后进先出”表示最后被插入的元素最先能被删除。 1、队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则； 2、栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先进先出”和“后进先出

27、”的数据组织方式。 3、双向链表使用链式存储方式，二叉树也通常采用链式存储方式，它们的存储- 13 -数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。答案：D【真题 15】 下列关于栈的描述正确的是_。 （2005 年 9 月）A)栈是特殊的线性表，只能在一端插入或删除元素 B)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 C)在栈中只能插入元素而不能删除元素 D)在栈中只能删除元素而不能插入元素 解析： 栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。答案：A 【真题 16】 下列关于栈的描述中错误的是_。 （2005 年 4 月

28、）A) 栈具有记忆作用 B)对栈的插入与删除操作中，不需要改变栈底指针 C)栈是先进后出的线性表 D)栈只能顺序存储 解析： 本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。 1、栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素。 2、栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用。 3、对栈进行插入和删除操作时，栈顶位置是动态变化的，栈底指针不变。答案：D 【真题 17】 下列叙述中正确的是_。 （2010 年 9 月）A)在栈中，栈底指针不变，栈中元

29、素随栈顶指针的变化而动态变化 B)上述三种说法都不对 C)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 D)在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 解析： 栈是限定仅在一端进行插入和删除操作的线性表。允许插入和删除的一端叫做栈顶，另一端叫做栈底，因此栈中元素随栈顶指针的变化而动态变化，而栈底指针不变。答案：A 【真题 18】 一个栈的初始状态为空。首先将元素 5，4，3，2，1 依次入栈，然后退栈一次，再将元素 A,B,C,D 依次入栈，之后将所有元素全部退栈，则所有元素退栈(包括中间退栈的元素)的顺序为_【1】_。 （2010 年 9 月）解析： 本题主要考查栈的出

30、入操作。栈是一种先进后出的数据结构。题目告诉我们将 5，4，3，2，1 依次入栈，然后退栈一次，很显然这时退栈的是 1，接- 14 -着将 A，B，C，D 入栈，然后全部退栈，其栈中各元素的退栈顺序是DCBA2345。所以最后出栈的顺序应该是 1DCBA2345。答案：1DCBA2345 Point5：线性链表、双向链表与循环链表 出题趋势 考试日期05-405-907-908-9出题次数22111、数据结构中，每个数据存储在一个存储单元中，这个存储单元称为结点。在链式存储方式中，要求每个结点由两部分组成：部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该

31、结点的前一个或后一个结点(即前件或后件)。 2、线性链表：线性表的链式存储结构，称为线性链表。 (1) 对于大的线性表，特别是元素变化频繁的线性表不宜采用顺序存储结构，而要用链式存储结构。 (2) 数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。 (3) 结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。 (4) 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 (5) 链式存储方式既可用于表示线

32、性结构，也可用于表示非线性结构。 (6) 线性链表，HEAD 称为头指针，HEAD=NULL(或 0)称为空表。 线性链表的基本运算：查找、插入、删除。 3、双向链表：两指针：左指针(Llink)指向前件结点，右指针(Rlink)指向后件结点。 4、循环链表的两个特点： (1) 增加了一个表头结点。 (2) 最后一个结点的指针域不是空，而是指向表头结点。 真题分析 【真题 1】 下列叙述中正确的是_。 （2008 年 9 月）A)顺序存储结构能存储有序表，链式存储结构不能存储有序表 B)链式存储结构比顺序存储结构节省存储空间 C)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连

33、续的D)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 解析： 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体- 15 -现。而链式存储结构的存储空间不一定是连续的。 链式结构的结点由两部分组成，一部分是数据信息，另一部分是地址域，因此在存储空间上要多于顺序存储所占用的空间。答案：C 【真题 2】 下列叙述中正确的是_。 （2007 年 9 月）A) 程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构B)三种说法都不对 C)数据的逻辑结构与存储结构必定是一一对应的 D)由于计算机存储

34、空间是向量式的存储结构，因此，数据的存储结构一定是线性结构解析： 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。答案：B 【真题 3】 下列叙述中正确的是_。 （2005 年 9 月）A)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率B)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率C)一个逻辑数据结构只能有一种存储结构 D)数据的逻辑结构属于线性结构，存储结构属

35、于非线性结构 解析： 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。答案：B 【真题 4】 数据结构分为逻辑结构和存储结构，循环队列属于_【5】_结构。 （2005 年 9 月）解析： 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当是存储结构。答案：存储 【真题 5】 数据的存储结构是指_。 （2005 年 4 月）A)数据在计算机中的

36、顺序存储方式 B)数据的逻辑结构在计算机中的表示 - 16 -C)存储在外存中的数据 D)数据所占的存储空间量 解析： 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。答案：B【真题 6】 下列对于线性链表的描述中正确的是_。 （2005 年 4 月）A)存储空间必须连续，且前件元素一定存储在后件元素的前面 B)存储空间必须连续，且各元素的存储顺序是任意的 C) 存储空间不一定是连续，且各元素的存储顺序是任意的 D)存储空间不一定是连续，且前件元素一定存储在后件元素的前面 解析： 在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之

37、间的逻辑关系可以不一致，数据元素之间的逻辑关系，是由指针域来确定的。答案：C Point6：二叉树 出题趋势 考试日期05-405-906-406-907-307-908-408-909-309-910-310-9出题次数112132111111i-1h-11、树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称

38、为树的深度。 2、二叉树：度为 2 的树就是二叉树。 (1) 二叉树的特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 3、二叉树的性质 (1) 在二叉树中，第 i 层的结点总数不超过 2 (i 1)。 (2) 深度为 h 的二叉树总计最多有 2 个结点(h1)，最少有 h 个结点。 (3) 对于任意一棵二叉树，如果其叶子结点数为 N0，而度数为 2 的结点总数为 N2，则N0=N2+1，即叶子数总比度为 2 的节点数多 1。 (4) 具有 n 个结点的完全二叉树的深度为 int(log2n)+1。 (5) 有 N 个结点的完全二叉树各结点如果用顺序

39、方式存储，则结点之间有如下关系： - 17 -若 k 为结点编号，则如果 k 1，则其父结点的编号为 k/2； 如果 2 x k N，则无左孩子; 如果 2 x k + 1 N，则无右孩子。 3、完全二叉树和满二叉树 (1) 完全二叉树：只有最下面的两层结点度小于 2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2) 满二叉树：除了叶子结点外每一个结点都有左右子女且叶子结点都处在最低层的二叉树。 4、遍历是对树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上

40、是将二叉树的各个结点转换成为一个线性序列来表示。设 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR(称为先根次序遍历，简称前序遍历)，LDR(称为中根次序遍历，简称中序遍历)，LRD(称为后根次序遍历，简称后序遍历)。 (1) 前序遍历：访问根；按先序遍历左子树；按先序遍历右子树。 (2) 中序遍历：按中序遍历左予树；访问根；按中序遍历右子树。 (3) 后序遍历：按后序遍历左予树；按后序遍历右子树；访问根。 真题分析 【真题 1】 某二叉树有 5 个度为 2 的结点，则该二叉树中的叶子结点数是_。 （2009 年 3 月）A) 6 B) 4 C

41、) 10 D) 8 解析： 根据二叉树的性质，在任意二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。答案：A (N-1)【真题 2】 深度为 5 的满二叉树有_【2】_个叶子节点。 （2008 年 4 月）解析： 在二叉树中，深度为 N 的满二叉树的叶子结点数目为：2 。答案：16 【真题 3】 一棵二叉树中共有 70 个叶子节点与 80 个度为 1 的结点，则该二叉树总结点数为_。 （2007 年 9 月）A) 229 B) 231 - 18 -C) 219 D) 221 解析： 在二叉树中，叶子结点个数为 n0，则度为 2 的结点数 n2 = n0-1。本题中叶子结点

42、的个数为 70，所以度为 2 的结点个数为 69，因而总结点数=叶子结点数+度为 1 的结点数+度为 2 的结点数=70+80+69=219。答案：C 【真题 4】 某二叉树中有 n 个度为 2 的结点，则该二叉树中的叶子结点数为_。 （2007 年 3 月）A) 2n B) n/2 C) n+l D) n-1 解析： 在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。所以该二叉树的叶子结点数等于 n+1。答案：C 7【真题 5】 在深度为 7 的满二叉树中，度为 2 的结点个数为_【1】_。 （2007年 3 月）解析： 一棵深度为 7 的满二叉树，其结点个数为

43、 2 -1=127，又因为叶子结点个数 N0 和度为 2 的结点个数 N2 的关系是 N0 = N2+1，所以总结点数是N0+N2 = 2N2+1=127，所以度为 2 的结点个数等于 63。答案：63 (k-1)(k-1)(k-1) (7-1) 6【真题 6】 在深度为 7 的满二叉树中，叶子结点的个数为_。 （2006 年 4月）A) 64 B) 63 C) 32 D) 31 解析： 在二叉树的第 k 层上，最多有 2 (k1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第 k 层上有 2 个结点。因此，在深度为 7 的满二叉树中，所有叶子结点在第 7 层上，即其

44、结点数为 2 = 2 = 2 = 64。答案：A (k-1)(6-1) 5【真题 7】 一棵二叉树第六层（根结点为第一层）的结点数最多为_【4】_个。 （2005 年 9 月）解析： 二叉树的一个性质是，在二叉树的第 k 层上，最多有 2 (k=1)个节点。由此，2 = 2 = 32。所以答案为 32。- 19 -答案：32 【真题 8】 某二叉树中度为 2 的结点有 18 个，则该二叉树中有_【1】_个叶子结点。 （2005 年 4 月）解析： 二叉树具有如下性质：在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。根据题意，度为 2 的节点为 18 个，那么，叶

45、子结点就是 19 个。答案：19 【真题 9】 下列二叉树进行中序遍历的结果是_【1】_。 （2008 年 9 月）解析： 中序遍历是指先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。所以中序遍历的结果是 DBXEAYFZC。答案：DBXEAYFZC 【真题 10】 对下列二叉树进行中序遍历的结果是_【4】_。 （2007 年 9 月）- 20 -解析： 二叉树的中序遍历是指首先按中序遍历根结点的左子树，然后访问根结点，最后按中序遍历根结点的右子树，中序遍历二叉树的过程是一个递归的过程。答案：ACBDFEHGP 【真题

46、11】 对下列二叉树进行前序遍历的结果为_。 （2007 年 3 月）A) ABDYECFXZ B) ABCDEFXYZ C) DYBEAFCZX D) YDEBFZXCA 解析： 二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：访问根结点；前序遍历左子树；前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。答案：A 【真题 12】 对下列二叉树进行中序遍历的结果是_。 （2006 年 9 月）- 21 -A) ABDCGEF B) FCADBEG C) ACBDFEG D) ACBDFGE 解析： 二叉树

47、的中序遍历递归算法为：如果根不空，则(1)按中序次访问左子树，(2)访问跟结点，(3)按中序次序访问右子树；否则返回。二叉树的中序遍历递归算法为：如果根不空，则(1)按中序次访问左子树，(2)访问跟结点，(3)按中序次序访问右子树；否则返回。 本题中，根据中序遍历算法，应首先按照中序次序访问以 C 为根结点的左子树，然后再访问根结点 F 最后才访问以 E 为根结点的右子树。遍历以 C 为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为 ACBD；然后遍历根结点 F；遍历以 E 为根结点的右子树，同样要遵循中序遍历算法，因此中序遍历结果为 EG。最后把这三部分的遍历结果按顺序连接起来，中

48、序遍历结果为ACBDFEG。答案：C【真题 13】 对如下二叉树进行后序遍历的结果为_。 （2006 年 4 月）A) ABDECF B) DEBFCA C) ABCDEF D) DBEAFC 解析： 二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。 也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为 DEBFCA。答案：B 【真题 14】 设

49、二叉树如下： - 22 -对该二叉树进行后序遍历的结果为_【3】_ 。 （2010 年 3 月）解析： 本题为二叉树遍历题，LRD 的结果为：EDBGHFCA答案：EDBGHFCA 【真题 15】 某二叉树有 5 个度为 2 的结点以及 3 个度为 1 的结点，则该二叉树中共有_【1】_个结点。 （2009 年 9 月）解析： 假设：度为 0 的节点用 N0 表示，度为 1 的节点用 N1 表示，度为 2 的节点用 N2 表示。其中度为 0 的结点数比度为 2 的结点数多 1 个，即 N0= N2 + 1。所以 N = N0 + N1 + N2 = (N2 + 1) + N1 + N2= N1

50、 + 2N2 + 1 = 3 + 25 + 1 = 14。答案：14 【真题 16】 一棵二叉树有 10 个度为 1 的结点，7 个度为 2 的结点，则该二叉树有_【3】_个结点。 （2010 年 9 月）解析： 计算一棵二叉树结点个数的公式为：度为 2 的结点数*2+度为 1 的结点数*1+1。根据这个公式我们可以知道题目中描述的二叉树结点数为 25 个。答案：25 Point7：基本排序与查找的算法 出题趋势 考试日期05-405-906-406-907-908-408-909-310-310-9出题次数21111111111、查找 (1) 顺序查找是一种最基本和最简单的查找方法。它的思路

51、是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于长度为 n 的有序线性表，在最坏情况下，顺序查找需要比较 n 次。 - 23 -1.5(2) 对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找： 无序的线性表； 即使是有序的线性表，如果采用链式存储结构，也只能顺序查找。 (3) 二分查找是针对有序表进行查找的简单、有效而又较常用的方法。其基本思想是：首先选择有序表中间位置的记录，将其关键字与给定关键字 k 进行比较，若相等，则查找成功；否则

52、，若 k 值比该关键字值大，则要找的元素一定在表的后半部分(或称右子表)，则继续对右子表进行二分查找；若 k 值比该关键字值小，则要找的元素一定在表的前半部分(左子表)，同样应继续对左子表进行二分查找。每进行一次比较，要么找到要查找的元素，要么将查找的范围缩小一半。如此递推，直到查找成功或把要查找的范围缩小为空(查找失败)。 (4) 显然，仅当有序线性表为顺序存储时才能用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log2n 次，而顺序查找需要比较 n 次。 2、排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常用的排序方法 (1) 交换类排序法： 冒泡排序法，需要比较的次数为 n(n-1)/2； 快速排序法，最坏情况需要