A

[解析] 在《玩转Office轻松过二级(第3版)》的第16章中，形象地介绍了二分查找的过程，并通过一个“小游戏”记住二分查找的最坏情况下的时间复杂度为O(log₂n)。顺序查找为O(n)，快速排序和堆排序都为O(nlog₂n)。

B

[解析] 解决一个问题可以有不同的算法。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。一般用时间复杂度和空间复杂度衡量算法的优劣。

A

[解析] 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。所需基本运算的执行次数与语句条数没有关系，而一般与循环结构的循环次数有关。然而算法所执行的基本运算次数与问题的规模有关，例如两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算(即两个数的乘法)次数显然是不同的。在顺序查找法中，基本运算(即比较)的次数也与被查值有关，如要查找的数据恰好是第一个元素，只需比较一次；如要查找的数据是最后一个元素，则n个数据需要比较n次。算法空间复杂度指执行这个算法所需要的内存空间。包括算法程序所占的空间、输入的初始数据所占的空间、算法执行过程中所需的额外空间(而与输出结果无关)。算法的时间复杂度与空间复杂度没有必然的联系。

C

[解析] 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。所需基本运算的执行次数与语句条数没有关系，而一般与循环结构的循环次数有关。然而算法所执行的基本运算次数与问题的规模有关，例如两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算(即两个数的乘法)次数显然是不同的。在顺序查找法中，基本运算(即比较)的次数也与被查值有关，如要查找的数据恰好是第一个元素，只需比较一次；如要查找的数据是最后一个元素，则n个数据需要比较n次。算法空间复杂度指执行这个算法所需要的内存空间。包括算法程序所占的空间、输入的初始数据所占的空间、算法执行过程中所需的额外空间(而与输出结果无关)。算法的时间复杂度与空间复杂度没有必然的联系。

D

[解析] 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。所需基本运算的执行次数与语句条数没有关系，而一般与循环结构的循环次数有关。然而算法所执行的基本运算次数与问题的规模有关，例如两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算(即两个数的乘法)次数显然是不同的。在顺序查找法中，基本运算(即比较)的次数也与被查值有关，如要查找的数据恰好是第一个元素，只需比较一次；如要查找的数据是最后一个元素，则n个数据需要比较n次。算法空间复杂度指执行这个算法所需要的内存空间。包括算法程序所占的空间、输入的初始数据所占的空间、算法执行过程中所需的额外空间(而与输出结果无关)。算法的时间复杂度与空间复杂度没有必然的联系。

A

[解析] 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。所需基本运算的执行次数与语句条数没有关系，而一般与循环结构的循环次数有关。然而算法所执行的基本运算次数与问题的规模有关，例如两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算(即两个数的乘法)次数显然是不同的。在顺序查找法中，基本运算(即比较)的次数也与被查值有关，如要查找的数据恰好是第一个元素，只需比较一次；如要查找的数据是最后一个元素，则n个数据需要比较n次。算法空间复杂度指执行这个算法所需要的内存空间。包括算法程序所占的空间、输入的初始数据所占的空间、算法执行过程中所需的额外空间(而与输出结果无关)。算法的时间复杂度与空间复杂度没有必然的联系。

C

[解析] 由后序遍历序列为CBADE知，根结点为E。再由中序遍历序列为CBADE知，序列CBAD中的结点均位于E的左子树。再由后序遍历序列为CBADE知，序列CBAD中的根结点为D……继续在中序中找局部的左右分支、在后序中找局部根结点，一层一层画出二叉树，然后再求前序遍历序列。这类题需要画图进行分析，详细分析方法可参考《玩转Office轻松过二级(第3版)》的第16章。

B

[解析] 完全二叉树除最后一层外，各层结点均达到最大，可据层次输出序列由上到下、由左到右画出此二叉树。然后再按照根结点、左子树、右子树的顺序求其前序序列。

C

C

A

[解析] 在前序遍历或后序遍历序列中找到根结点，再在中序遍历序列中找到左右分支结点。对左右分支不是一个结点的，对左右分支做同样的分析过程，一层一层进行。最终画出二叉树后，再求题目要求的遍历序列。这类题需要画图进行分析，详细分析方法可参考《玩转Office轻松过二级(第3版)》的第16章。题目解析仅为知识的简要点拨，仅供参考，而非系统学习的手段。请掌握正确的学习方法：系统学习知识原理，然后才能做题练习，否则很难读懂学会。

D

[解析] 在前序遍历或后序遍历序列中找到根结点，再在中序遍历序列中找到左右分支结点。对左右分支不是一个结点的，对左右分支做同样的分析过程，一层一层进行。最终画出二叉树后，再求题目要求的遍历序列。这类题需要画图进行分析，详细分析方法可参考《玩转Office轻松过二级(第3版)》的第16章。题目解析仅为知识的简要点拨，仅供参考，而非系统学习的手段。请掌握正确的学习方法：系统学习知识原理，然后才能做题练习，否则很难读懂学会。

A

[解析] 在前序遍历或后序遍历序列中找到根结点，再在中序遍历序列中找到左右分支结点。对左右分支不是一个结点的，对左右分支做同样的分析过程，一层一层进行。最终画出二叉树后，再求题目要求的遍历序列。这类题需要画图进行分析，详细分析方法可参考《玩转Office轻松过二级(第3版)》的第16章。题目解析仅为知识的简要点拨，仅供参考，而非系统学习的手段。请掌握正确的学习方法：系统学习知识原理，然后才能做题练习，否则很难读懂学会。

A

[解析] 可自行画一棵简单的排序二叉树，如根结点为3，一个左结点为1，一个右结点为5，显然其中序遍历序列1，3，5为有序序列。

A

[解析] 叶子结点比度为2的结点多一个，因此，叶子结点为188个。375-187-188=0。

A

[解析] 叶子结点比度为2的结点多一个，设叶子结点为x个，则度为2的结点为x-1个，完全二叉树中度为1的结点为1个或0个，则分两种情况：①x+x-1+1=2n；②x+x-1+0=2n。解方程第①种情况得x=n，第②种情况不能得到整数解舍去。

A

[解析] 树中的结点数=所有结点的度数+1。设度为3的结点为x个，则所有结点的度数表示为2×3+1×1+6×0+3x。可列方程得3+1+6+x=2×3+1×1+6×0+3x+1。解方程得x=1。

B

[解析] 度为3的树的结点度分为3、2、1、0四种，则27-4-1-10=12。

D

[解析] 树中的结点数=所有结点的度数+1。设度为3的结点为x个，度为1的结点为y个，则树中的结点数表示为0+6+x+y，所有结点的度数表示为：0×2+6×0+x×3+y×1。可列方程得：0+6+x+y=0×2+6×0+x×3+y×1+1，左右两边的未知数y可以约去，解方程得x=2.5，不能得到整数解。

C

[解析] 二叉树的叶子结点数比度为2的结点数多一个，所以叶子结点数为199+1=200个。

C

[解析] 二叉树的叶子结点数比度为2的结点数多一个，所以度为2的结点个数是250-1=249个。

B

[解析] 度为4的树包含度为4、3、2、1、0的五种结点，叶子结点是度为0的结点。树中的结点数=所有结点的度数+1。设叶子结点为x个，则2+3+3+0+x=4×2+3×3+2×3+1×0+0×x+1，解方程得x=16。

A

[解析] 度为3的树包含度为3、2、1、0的四种结点，叶子结点是度为0的结点。树中的结点数=所有结点的度数+1。设叶子结点为x个，则4+1+3+x=3×4+2×1+1×3+0×x+1，解方程得x=10。

B

[解析] 度为3的树包含度为3、2、1、0的四种结点，叶子结点是度为0的结点。树中的结点数=所有结点的度数+1。设度为3的结点为x个，度为1的结点为y个，则x+0+y+5=3x+2×0+1×y+0×5+1，两边y可约去，解方程得x=2。

B

[解析] 最坏情况下比较次数：堆排序为nlog₂n，其他三种比较次数都是n(n-1)/2。

B

[解析] 最坏情况下比较次数：堆排序为nlog₂n，寻找最大项为n-1，顺序查找法为n，快速排序为n(n-1)/2。在《玩转Office轻松过二级(第3版)》的第16章中介绍了“折纸小游戏”，轻松记住二分查找的比较次数log₂n。

C

[解析] 最坏情况下比较次数：堆排序为nlog₂n，寻找最大项为n-1，顺序查找法为n，快速排序为n(n-1)/2。在《玩转Office轻松过二级(第3版)》的第16章中介绍了“折纸小游戏”，轻松记住二分查找的比较次数log₂n。

A

[解析] 最坏情况下比较次数：堆排序为nlog₂n，寻找最大项为n-1，顺序查找法为n，快速排序为n(n-1)/2。在《玩转Office轻松过二级(第3版)》的第16章中介绍了“折纸小游戏”，轻松记住二分查找的比较次数log₂n。

A

[解析] 最坏情况下时间复杂度：堆排序为O(nlog₂n)，希尔排序为O(n^r)(1＜r＜2)，快速排序和冒泡排序均为O(n(n-1)/2)。

B

[解析] 给定包含n个不同元素的数组A[1..n]，如果存在i＜j且A[i]＞A[j]，则(i，j)称为数组A的一个逆序。快速排序法的基本思想是任取序列中某个元素为基准元素，将序列划分为左右两个子序列，左侧子序列都小于或等于基准元素，右侧子序列都大于基准元素，接下来分别对两个子序列重复上述过程。冒泡排序法只对相邻的两个元素进行比较，因此，在互换两个相邻元素时只能消除一个逆序，而快速排序法不是对两个相邻元素进行比较，可以实现通过一次交换而消除多个逆序，但由于均与基准元素比较，会产生新的逆序。

C

[解析] 在最坏情况下比较次数：有序表的二分查找为log₂n，顺序查找为n，寻找最大项和寻找最小项均为n-1。

B

[解析] 在最坏情况下时间复杂度：堆排序为nlog₂n，希尔排序为n^r(1＜r＜2)，快速排序和冒泡排序均为n(n-1)/2。

B

[解析] 在最坏情况下时间复杂度：堆排序为nlog₂n，希尔排序为n^r(1＜r＜2)，快速排序和冒泡排序均为n(n-1)/2。

A

[解析] 如果要找的数据恰好位于0号元素，则只需比较1次就可以了；如果要找的数据在a[1]，则需比较2次……，最坏情况是要找的数据在最后一个位置a[n-1]，所有的元素都要比较，需比较n次。因此，平均需要比较(1+2+…+n)/n=(n+1)/2次。

A

[解析] 如果要找的数据恰好位于0号元素，则只需比较1次就可以了；如果要找的数据在a[1]，则需比较2次……，最坏情况是要找的数据在最后一个位置a[n-1]，所有的元素都要比较，需比较n次。这是找到元素的情况。如没有找到元素，都要比较n次。因此，平均需要比较(找到元素的情况×1/2+未找到元素的情况×1/2):(1+2+…n)/n×1/2+n×1/2=(3n+1)/4次，大约为3n/4次。

A

[解析] 最坏情况下，快速排序所需要的比较次数为n(n-1)/2=15×14/2=105。

D

[解析] 堆栈既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的栈。带链的栈空的条件是top=bottom=NULL。

D

[解析] 队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的队列。带链的队列空的条件是front=rear=NULL。

D

[解析] 循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。本题数组总容量为200，故本题元素个数为0或200。

A

[解析] 循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。本题数组总容量为100，故本题元素个数为0或100。