第1章数据结构与算法笔试题考点分析

1算法 考试的内容：

1.1 算法的基本概念

1．算法的概念(必记) ：

是指解题方案的准确而完整的描述。

分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化) ，但在程序实现时，必须受到具体环境的约束(现实不同于理想) 。

结论：

2．算法的基本特征(必记) ：

由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。

b. 确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 算法有相应的初始数据。

3．算法的基本要素：

一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。 基本运算和操作分为四类：

a. 算术运算: (加、减、乘、除等运算)

b. 逻辑运算: (与、或、非等运算)

c. 关系运算: (大于、小于、等于、不等于等运算)

d. 数据传输: (赋值、输入、输出等操作) 算法的控制结构：

算法中各操作之间的执行顺序称之为算法的控制结构。循环三种基本控制结构组合而成。

注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的

4．算法设计基本方法：

列举法、归纳法、递推、递归、减半递推技术、回溯法。

1.2 算法的复杂度 (必记)

算法的复杂度

1．算法的时间复杂度：

是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。

可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。

2．算法的空间复杂度：

一个算法的空间复杂度，包含有三部分所组成：算法程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。 历届的考题：

1、算法具有五个特性，以下选项中不属于算法特性的是(______) [2005.4]

A) 有穷性 B)简洁性 C)可行性 D)确定性

2、问题处理方案的正确而完整的描述称为______。 [2005.4]

3、下列叙述中正确的是________。[2006.9]

A ）一个算法的空间复杂度大，则其时间复杂度也必定大

B ）一个算法的空间复杂度大，则其时间复杂度必定小 C ）一个算法的时间复杂度大，则其空间可复杂度必定小

D ）上述三种说法都不对

4、算法复杂度主要包括时间复杂度和[_____]复杂度。[2006.9]

1.2数据结构与算法

考试的内容： 数据结构作为计算机的一门学科，主要研究以下三个方面的问题：

a

b c ．对各种数据结构进行的运算。

注意：讨论以上问题主要目的是为了。提高效率包括两个方面：高数据处理的速度，二是节省在数据处理过程中所占用的计算机存储空间。

2.1 什么是数据结构

简单地说，数据结构是指相互有关联的数据元素的集合。 而数据元素之间的关联通常是指其前后件关系(即先后顺序关系) ，如春、夏、秋、冬之间的先后顺序关系。

因此，一个数据结构应包含以下两方面的信息：之间的前后件关系。

1．数据的逻辑结构

所谓数据的逻辑结构，注意：这种逻辑关系仅指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。

2．数据的存储结构

数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式 (也称数据的物理结构) 。

注意：

a 、 b 、数据的存储结构有顺序、链接、索引等。

c 、数据元素采用不同的存储结构，其数据处理的效率是不同的。

2.2 数据结构的图形表示 一般用一个中间标有元素值的方框表示一个数据元素，用一条有向线段从前件结点指向后件结点。

在数据结构中，没有前件的结点成为根结点(如上图中的春与父亲) ；没有后件的结点称为终端结点 (也称为叶子结点，如上图中的冬与儿子和女儿) 。

注意：这种变化可能是元素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。

2.3线性结构与非线性结构

空的数据结构是：一个数据元素都没有的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，构和非线性结构。

一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。 a. 有且只有一个根结点； b. 每一个结点最多有一个前件，也最多有一个后件。

在上图中，左边的是线性结构，而右边的是非线性结构。

注意：还是属于非线性结构，要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

历届的考题：

1、数据的存储结构是指(_____)[2005.4]

A) 存储在外存中的数据 B)数据所占的存储空间量

C) 数据在计算机中的顺序存储方式 D)数据的逻辑结构中计算机中的表示

2、下列叙述中正确的是(______)[2005.9]

A) 一个逻辑数据结构只能有一种存储结构

B)

数据的逻辑结构属于线性结构，存储结构属于非线性结构

C) 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D) 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

1.3线性表及其顺序存储结构

考试的内容：

3.1线性表的基本概念

非空线性表的结构特征如下：

a. 有且只有一个根结点，它无前件； b. 有且只有一个终端结点，它无后件； c. 除根结点与

线性表中结点的个数 n 称为线性表的长度。当n=0时，称为空表。

3.2 线性表的顺序存储结构

线性表的顺序存储结构具有以下两个基本特点：

b. 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

注意：在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定在后件元素的前面。

在线性表的顺序存储结构中，如第一个元素的地址为ADR(a1)，每个元素占用的存储空间大小为k 个字节，则线性表中第i 个元素的存储地址为：ADR(a1)+(i-1)*k。

3.3 顺序表的插入运算

在线性表的顺序存储结构中，当插入元素时，插入点后的元素都要向后移动一位，以让出一个存储空间。

在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。

3.4 顺序表的删除运算

在线性表的顺序存储结构中，当删除元素时，删除点后的元素都要向前移动一位，以保证元素都是相邻存储的。

在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率是很低的。

1.4栈和队列

注意的考点：

4.1 栈及其基本运算

1．什么是栈

栈是一种特殊的线性表。栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。

栈按照" 先进后出" (FILO)或" 后进先出" (LIFO)组织数据，栈具有记忆作用。用top 表示栈顶位置，用botton 表示栈底。

2．栈的顺序存储及其运算

栈的基本运算有三种：. 入栈运算、退栈运算和. 读栈顶元素。

4.2 队列及其基本运算

1．什么是队列

队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。允许插入的一端称为队尾，允许删除的一端称为排头(或队头) 。

队列又称为" 先进先出"(FIFO)或" 后进后出"(LILO)的线性表，它体现了" 先来先服务" 的原则。 往队列的队尾插入一个元素称为，从队列的排头删除一个元素称为。

2．循环队列及其运算

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空

队列空和队列满的条件如下：

队列空的条件为 s=0 ;

队列满的条件为 s=1且front=rear.

循环队列主要有两种基本运算：入队运算和退队运算。

a. 入队运算：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即rear=rear+1)，并当rear=m+1时置rear=1；然后将新元素插入到队尾指针指向的位置。

注意：当循环队列非空 (s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为" 上溢" 。

b. 退队运算：指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进一(即front=front+1)，并当front=m+1时置front=1;然后将排头指针指向的元素赋给指定的变量。 注意：当循环队列为空 (s=0)时，不能进行退队运算，这种情况称为" 下溢" 。

历届的考题：

1、下列关于栈的描述中错误的是(_______)[2005.4]

A ）栈是先进后出的线性表 B）栈只能顺序存储

C ）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针

2、按照" 后进先出" 原则组织数据的数据结构是(______)[2006.4]

A) 队列 B)栈 C)双向链表 D)二叉树

3、列关于栈的描述正确的是(______)[2005.9]

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

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

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

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

4、数据结构分为逻辑结构和存储结构，循环队列属于____结构。[2005.9]

5、按“先进后出”原则组织数据的数据结构是_____。[2006.9]

1.5线性链表

注意的考点：

5.1线性链表的基本概念

1. 链式存储

在顺序存储方式中所有的数据元素在内存中是相邻存放的，从而造成了在插入与删除数据元素时，需要大量移动相应的数据元素。为了解决这种问题，可以将每个数据元素存储在内存中不相邻的不同位置，并利用上一个数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点) ，以便查找。这就是链式存储方式。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；

另一部分用于存放地址，

称为指针域。其中指针用于指向该结点的前一个或后一个结点 (即前件或后件) 。

注意：a 、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 b 、链式存储方式既可以用于表示线性结构，也可以用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。

2．线性链表

线性表的链式存储结构称为。 如果结点中有两个指针，一个用于指向前一个结点，而另一上用于指向后一个结点，则称之为双向链表。

3．带链的栈：栈的链式存储结构称为。

4．带链的队列：队列的链式存储结构称为。

5.2 线性链表的基本运算 ：查找、插入、删除。

历届的考题：

1、下列对于线性链表的描述中正确的是(____)[2005.4]

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

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

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

D ）存储空间必须连续，且各元素的存储顺序是任意的

2、下列叙述中正确的是(_____)[2006.4]

A) 线性链表是线性表的链式存储结构 B)栈与队列是非线性结构

C) 双向链表是非线性结构 D)只有根结点的二叉树是线性结构

3、数据结构分为线性结构和非线性结构，带链的队列属于____。[2006.9]

1.6树与二叉树

注意的考点：

6.1 树的基本概念

树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

a. 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。

b. 在树结构中，一个结点所拥有的后件个数称为该结点的度；在树中，所有结点中的最大的度称为树的度。

c. 树具有明显的层次关系，即树是一种层次结构。

d. 数的最大层次称为树的深度。

f. 在树中，叶子结点没有子树。

6.2二叉树及其基本性质

1．什么是二叉树：

二叉树是一种很有用的非线性结构。

二叉树具有以下两个特点：

a. 非空二叉树只有一个根结点；

b. 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

由以上特点可以看出，在二叉树中，每一个结点的度最大为2。

2．二叉树的基本性质：(重要)

a. 在二叉树的第k 层上，最多有2(k>=1)个结点。

m b. 深度为m 的二叉树最多有2-1个结点。深度为m 的二叉树是指二叉树共有m 层。

c. 在任意一棵二叉树中，度为0的结点(即叶子结点) 总是比深度为2的结点多一个。

n n n d. 具有n 个结点的二叉树，其深度至少为[log 2]+1，其中[log 2]表示取log 2的整数部分。

3．满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

a. 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k 层上有2k-1个结点，且深度为m 的满二叉树有2m-1个结点。

b. 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

完全二叉树还具有以下性质：

n a. 具有n 个结点的完全二叉树的深度为log

2] +1。

6.3 二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。

6.4 二叉树的遍历：(重要)

在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。

a. 前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。

k-1

b. 中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。

c. 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。

前序：FCADBEGHP 中序：ACBDFEHGP 后序：ABDCHPGEF 注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾，而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。 历届的考题：

1、在深度为7的满二叉树中，叶子结点的个数为()[2006.4]

A)32 B)31 C)64 D)63

2、对下图1所示二叉树

进行中序遍历的结果是________。[2006.9]

A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG

3、对如下图2所示二叉树，进行后序遍历的结果为()[2006.4]

A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA

4、某二叉树中，度为2的结点有18个，则该二叉树中有___个叶子结点。[2005.4]

5、一棵二叉树第六层（根结点为第一层）的结点数最多为____个。[2005.9]

1.7查找技术

注意的考点：

7.1 顺序查找：

顺序查找的方法是：用被查元素与线性表中的元素逐一比较，直到找出相等的元素，则查找成功；或者找遍所有元素都不相等，则查找失败。

顺序查找的优点：对线性表的元素的逻辑次序无要求（不必对元素进行排序），对线性表的存储结构无要求(顺序存储、链接存储皆可) 。

顺序查找的效率很低，但在以下情况下，只能采用顺序查找：

a. 如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 b. 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 7.2二分法查找： 二分法查找是一种效率较高的线性表查找方法。要进行二分法查找，则线性表结点必须是排好序的，且线性表以顺序方式存储。

二分法查找的方法：首先用要查找的元素值与线性表中间位置的元素值相比较，这个中间结点把线性表分成了两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应在哪一个子表中进行，如此进行下去，直到找到满足条件的结点，或者确定表中没有这样的结点。 对于二分法查找的缺点是线性表排序需花费时间，顺序方式存储的插入、删除不便。 注意：对于长度为 n 的有序线性表，在最坏的情况下，二分查找只需要比较比较[log而顺序查找需要比较n 次。二分查找的效率要比顺序查找高得多。

历届的考题：

1、在长度为64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为(____)[2006.9]

A)63 B)64 C)6 D)7

2、下列数据结构中，能用二分法进行查找的是(_____)[2005.9]

A) 顺序存储的有序线性表 B)线性链表

C) 二叉链表 D)有序线性链表

3、对长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为(____)[2005.4]

A)log 2n B) n/2 C) n D) n+1

1.8排序技术(记住每种排序的比较次数) 注意的考点：

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

8.1交换类排序法

交换类排序的基本思想:两两比较待排序线性表的元素值, 并对不满足顺序要求的元素进行位置交换, 直到全部满足为止.

1、冒泡排序法

将相邻的元素进行两两比较，若为逆序则进行交换。将线性表照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将元素值最大的记录交换到了最后的位置，即该线性表的最终位置。若某一趟起泡过程中没有发生任何交换，则排序过程结束。

2、快速排序法

快速排序又称分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序线性表中任取一个元素，以它为基准用交换的方法将所

有的元素分成两部分，元素值比它小的在一个部分，元素值比它大的在另一个部分。再分别对两个部分实施上述过程，一直重复到排序完成。

在最坏的情况下与冒泡排序相当，然而快速排序的平均执行时间为O(nlog2n)。

8.2 插入类排序法 插入排序的基本思想是：每步将一个待排序元素按其元素值的大小插入到前面已排序的元素中的适当位置上，直到全部记录插入完为止。

1、简单插入排序

它是指将无序序列中的各元素依次插入到已经有序的线性表中。

2、希尔排序法

希尔排序的基本思想是把元素按下标的一定增量分组，对每组元素使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成一组，构成一组有序元素，故其属于插入排序方法。

8.3 选择类排序法

选择排序的基本思想是：每次从待排序的元素中选出元素值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。

1、简单选择排序

对线性表进行n-1趟扫描，第i 趟扫描从剩下的n-i+1个记录中选出元素值最小的记录，与第i 个记录交换。

2、堆排序

堆排序的基本思想是：对待排序的线性表，首先把它们按堆的定义排成一个序列（称为建堆），这就找到了最小的元素，然后将最小的元素取出，用剩下的元素再建堆，便得到次最小的的元素，如此反复进行，直到将全部元素排好序为止。

n

8.4总结

假设线性表的长度为n ，在最坏的情况下进行比较的次数：

历届的考题：

1、对于长度为n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(_)[2005.4]

A ）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2

2、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_____。[2006.4] 总复习图：

定义：是指解题方案的准确而完整的描述 算 特征：是可行性、确定性、有穷性和拥有足够法

复杂度：包括时间复杂度和空间复杂度 数 据 线性结构 顺序存储：栈与队列 结数据的逻辑结构 构链式存储：链表、双向 非线性结构 与数链表、带链的栈、带链 算据的队列 法 结 数据的存储结构 构

交换类、插入类和选择类 数据的运算 顺序查找、二分查找

1.9精典模拟题

一．选择题

1. 算法的时间复杂度是指______。

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. 算法分析的目的是______。(D)

A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系

C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进

7. 下列列关于算法的叙述中，正确的是______。

A. 算法是解决问题的实现程序 B. 算法是解决问题的计算方法

C. 程序的实现可以优于算法的设计

D. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。

8．下列叙述中正确的是______。

A) 线性表是线性结构 B)栈与队列是非线性结构

C) 线性链表是非线性结构 D)二叉树是线性结构

9. 数据的存储结构是指______。

A) 数据所占的存储空间量 B)数据的逻辑结构在计算机中的表示

C) 数据在计算机中的顺序存储方式 D)存储在外存中的数据

10．下列关于队列的叙述中正确的是______。

A) 在队列中只能插入数据 B)在队列中只能删除数据

C) 队列是先进先出的线性表 D)队列是先进后出的线性表

11．下列关于栈的叙述中正确的是______。

A) 在栈中只能插入数据 B)在栈中只能删除数据

C) 栈是先进先出的线性表 D)栈是先进后出的线性表

12. 以下数据结构中不属于线性数据结构的是______。

A. 队列 B. 线性表 C. 二叉树 D. 栈

13. 数据的存储结构是指______。

A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示

C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据

14. 栈和队列的共同点是______。

A. 都是先进后出 B. 都是先进先出

C. 只允许在端点处插入和删除元素 D. 没有共同点

15. 用链表表示线性表的优点是______。

A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同

C. 花费的存储空间较顺序存储少 D. 便于随机存取

16. 链表不具有的特点是______。

A ）不必事先估计存储空间 B ）可随机访问任一元素

C ）插入删除不需要移动元素 D ）所需空间与线性表长度成正比

17. 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是______。

A ）e3,e1,e4,e2 B ）e2,e4,e3,e1 C）e3,e4,e1,e2 D ）任意顺序

18．设有下列二叉树：

对此二叉树中序遍历的结果为______。

A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA

19．在深度为5的满二叉树中，叶子结点的个数为______。

A)32 B)31 C)16 D)15

20. 设树T 的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则 T树中叶子结点数为______。

A)8 B)7 C)6 D)5

21. 在一棵二叉树上第5层的结点数最多是______。

A. 8 B. 16 C. 32 D. 15

22. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。

A. 349 B. 350 C. 255 D. 351

23. 在深度为5的满二叉树中，结点的个数为______。

A. 32 B. 31 C. 16 D. 15

24. 已知二叉树后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是______。

A. cedba B. acbed C. decab D. deabc

25. 已知二叉树前序遍历序列deabc ，是后序遍历序列是dabec ，中序遍历序列是 ______。

A ）debac B ）decab C ）deabc D ）cedba

26. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和DBGEACHF ，则该二叉树的后序遍历为______。

A ）GEDHFBCA B ）DGEBHFCA C ）ABCDEFGH D ）ACBFEDHG

27. 树是结点的集合，它的根结点数目是______。

A ）有且只有1 B ）1或多于1 C ）0或1 D ）至少2

28. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址______。

A ）必须是连续的 B ）部分地址必须是连续的

C ）一定是不连续的 D ）连续不连续都可以

29. 下列叙述中，错误的是______。

A ）数据的存储结构与数据处理的效率密切相关

B ）数据的存储结构与数据处理的效率无关

C ）数据的存储结构在计算机中所占的空间不一定是连续的

D ）一种数据的逻辑结构可以有多种存储结构

30. 对于长度为n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。

A ）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 正确答案：

1- 5：C 、D 、C 、C 、D 6-10：D 、D 、A 、B 、C 11-15：D 、C 、B 、C 、A

16-20：B 、B 、B 、C 、A 21-25：B 、B 、B 、D 、A 26-30：B 、A 、D 、B 、D

二．填空题 1.

2. 3. 算法的空间复杂度是指执行过程中所需要的存储空间

4.

5. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。

6. 算法的复杂度主要包括时间复杂度和空间复杂度。

7. 一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

8. 栈的基本运算有三种：入栈、退栈和读栈顶元素。 9. 队列主要有两种基本运算：入队运算与退队运算。

10. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。

11. 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构或物理结构。

12. 顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。

13．在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有________个元素。

14．设一棵完全二叉树共有700个结点，则在该二叉树中有________个叶子结点。

15．设一棵二叉树的中序遍历结果为DBEAFC ，前序遍历结果为ABDECF ，则后序遍历结果为_________

16． 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。

17．在最坏的情况下，冒泡排序的时间复杂度为_______

18．在最坏情况下，堆排序需要比较的次数为________。

19．在长度为n 的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为________ 。

20．对于输入为N 个数进行快速排序算法的平均时间复杂度是_________。