1、二级 MS+Office 高级应用-66 及答案解析(总分：100.00，做题时间：90 分钟)一、选择题(总题数：50，分数：100.00)1.某二叉树共有 13 个结点，其中有 4 个度为 1 的结点，则叶子结点数为（分数：2.00）A.5B.4C.3D.22.设栈的顺序存储空间为 S(1:50)，初始状态为 top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00）A.30B.29C.20D.193.下列叙述中正确的是（分数：2.00）A.栈与队列都只能顺序存储B.循环队列是队列的顺序存储结构C.循环链表是循环队列的链式存储结构D.以上三项均错误4.
2、设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为（分数：2.00）A.BCAB.CBAC.ABCD.CAB5.下列排序方法中，最坏情况下时间复杂度最小的是（分数：2.00）A.冒泡排序B.快速排序C.堆排序D.直接插入排序6.为了对有序表进行对分查找，则要求有序表（分数：2.00）A.只能顺序存储B.只能链式存储C.可以顺序存储也可以链式存储D.任何存储方式7.设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为（分数：2.00）A.BCAB.CBAC.ABCD.CAB8.下列叙述中正确的是（分数：2.00）A.存储空间不连续的所有链表一定是非线
3、性结构B.结点中有多个指针域的所有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构9.算法时间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.执行算法所需要的基本运算次数C.执行算法所需要的所有运算次数D.执行算法所需要的时间10.设循环队列为 Q(1:m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（分数：2.00）A.1B.2C.m-1D.0 或 m11.在最坏情况下（分数：2.00）A.快速排序的时间复杂度比冒泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔
4、排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的12.在深度为 7 的满二叉树中，度为 2 的结点个数为（分数：2.00）A.64B.63C.32D.3113.设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00）A.30B.20C.m-19D.m-2014.算法空间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间15.设循环队列为 Q(1
5、:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4B.6C.m-5D.m-616.下列叙述中正确的是（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构17.某二叉树中有 n 个叶子结点，则该二叉树中度为 2 的结点数为（分数：2.00）A.n+1B.n-1C.2nD.n/218.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所
6、处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系D.算法的时间复杂度与空间复杂度没有必然的联系19.设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈顶指针 top=30(指向栈项元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20D.1920.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.2B.3C.4D.521.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空
7、间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构22.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D.以上三项都错误23.设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（分数：2.00）A.5B.6C
8、.m-5D.m-624.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA25.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构26.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都
9、是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上三项都错误27.设数据元素的集合 D=1，2，3，4，5，则满足下列关系 R 的数据结构中为线性结构的是（分数：2.00）A.R=(1，2)，(3，4)，(5，1)B.R=(1，3)，(4，1)，(3，2)，(5，4)C.R=(1，2)，(2，3)，(4，5)D.R=(1，3)，(2，4)，(3，5)28.下列叙述中正确的是（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B.线性表的链式存储结构中，每个结点必须有指向前件和指
10、向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空29.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDCD.CDE30.某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.5B.4C.3D.231.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的
11、一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间32.下列各序列中不是堆的是（分数：2.00）A.(91，85，53，36，47，30，24，12)B.(91，85，53，47，36，30，24，12)C.(47，91，53，85，30，12，24，36)D.(91，85，53，47，30，12，24，36)33.深度为 5 的完全二叉树的结点数不可能是（分数：2.00）A.15B.16C.17D.1834.有二叉树如下图所示，则前序序列为 （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH35.下列叙述中正确的是（
12、分数：2.00）A.循环队列是顺序存储结构B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象36.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构37.下列关于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境38.设有二叉树如下图所示，则中序序
13、列为 （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH39.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高C.便于查找D.排序时减少元素的比较次数40.深度为 7 的完全二叉树中共有 125 个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63C.64D.6541.下列叙述中正确的是（分数：2.00）A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链按存储方式存储在不连续的存储空间内D.任何存储
14、方式的有序表均能采用二分法进行查找42.设有二叉树如下图所示，则后序序列为 （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH43.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构44.设某二叉树中共有 140 个结点，其中有 40 个度为 1 的结点。则（分数：2.00）A.该二叉树中有 51 个叶子结点B.该二叉树中有 50 个叶子结点C.该二叉树中有 51 个度为 2 的结点D.不可能有这样的
15、二叉树45.带链的栈与顺序存储的栈相比，其优点是（分数：2.00）A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出D.所占存储空间相同46.某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为（分数：2.00）A.BADCB.DCBAC.CDABD.ABCD47.下列叙述中正确的是（分数：2.00）A.算法的时间复杂度与运行算法时特定的输入有关B.算法的时间复杂度与计算机的运行速度有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关48.下列各排序法中，最坏情况下的时间复杂度最低的是（分数：2.
16、00）A.堆排序B.快速排序C.希尔排序D.冒泡排序49.设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为（分数：2.00）A.1B.0C.50D.4950.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200C.198D.199二级 MS+Office 高级应用-66 答案解析(总分：100.00，做题时间：90 分钟)一、选择题(总题数：50，分数：100.00)1.某二叉树共有 13 个结点，其中有 4 个度为 1 的结
17、点，则叶子结点数为（分数：2.00）A.5 B.4C.3D.2解析：解析 根据二叉树的性质 3，在任意一颗二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个，即有 n 0 =n 2 +1。本题总结点数：13=n 0 +n 1 +n 2 =n 2 +1+4+n 2 =2n 2 +5，n 2 =4，所以叶子结点数等于 4+1=5。2.设栈的顺序存储空间为 S(1:50)，初始状态为 top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00）A.30B.29C.20 D.19解析：解析 栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入
18、与删除。通常用指针top 来指示栈项的位置，用指针 bottom 指向栈底。对栈的操作有入栈和退栈两种。入栈运算：首先将栈顶指针进一(即 top 加 1)，然后将新元素插入到栈顶指针指向的位置。退栈运算：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即 top 减 1)。因为初始状态为 top=0，经过入栈和退栈操作后栈中的元素个数就是 top 指针指向的位置。选项 C 正确。3.下列叙述中正确的是（分数：2.00）A.栈与队列都只能顺序存储B.循环队列是队列的顺序存储结构 C.循环链表是循环队列的链式存储结构D.以上三项均错误解析：解析 栈和队列是按数据的逻辑结
19、构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。线性结构的数据可以按顺序存储结构存储，也可以按链式存储结构存储，而循环队列是队列的顺序存储结构。选项 B 正确。4.设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为（分数：2.00）A.BCAB.CBA C.ABCD.CAB解析：解析 二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边
20、和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定 A 为根，A 在中序中的位置，可以确定 CB 为 A 的左子树上的结点，没有右子树。确定 A 之后，再看中序第二个值为 B，查看 B 在中序中的位置，C 在 B 左边，确定 C 为 B 的左子树。本题的具体二叉树如下，因此后序是CBA。 5.下列排序方法中，最坏情况下时间复杂度最小的是（分数：2.00）A.冒泡排序B.快速排序C.堆排序 D.直接插入排序解析：解析 排序方法中最坏情况下时间复杂度的大小如下表，根据下表可知选项 C 正确。 排序方法 最坏时间复杂度 最好时间复杂度 平均时间复杂度 直接插入 O(
21、n 2 ) O(n) O(n 2 ) 简单选择 O(n 2 ) O(n 2 ) O(n 2 ) 冒泡排序 O(n 2 ) O(n) O(n 2 ) 快速排序 O(n 2 ) O(nlog 2 n) O(nlog 2 n) 堆排序 O(nlog 2 n) O(nlog 2 n) O(nlog 2 n) 归并排序 O(nlog 2 n) O(nlog 2 n) O(nlog 2 n) 6.为了对有序表进行对分查找，则要求有序表（分数：2.00）A.只能顺序存储 B.只能链式存储C.可以顺序存储也可以链式存储D.任何存储方式解析：解析 有序表的对分查找条件是有序表为顺序存储。 顺序查找：如果线性表为
22、无序表(即表中元素的排序是无序的)，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 分块查找(又称索引顺序查找)：分块有序表结构分为两部分，线性表本身采用顺序存储结构；在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。7.设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为（分数：2.00）A.BCAB.CBAC.ABC D.CAB解析
23、：解析 二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。 本题根据后序，可以确定 A 为根结点；根据 B 在中序中的位置，可以确定 A 没有左子树，BC 为 A 的右子树，C 为 B 的右子树。本题的具体二叉树如下： 8.下列叙述中正确的是（分数：2.00）A.存储空间不连续的所有链表一定是非线性结构B.结点中有多个指针域的所
24、有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构 解析：解析 计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项ABC 都是错误的，栈和队列按照数据的逻辑划分都是线性结构。9.算法时间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.执行算法所需要的基本运算次数 C.执行算法所需要的所有运算次数D.执行算法所需要的时间解析：解析 算法的时间复杂度：分析算法时，语句总执行次数 T(n)是关于问题规模 n 的函数，进而分析 T(n)
25、随 n 的变化情况并确定 T(n)。算法的时间复杂度也就是算法的时间量度，记作 T(n)=O(f(n)。它表示问题输入规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复杂度。f(n)是问题规模 n 的某个函数。选项 B 正确。10.设循环队列为 Q(1:m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（分数：2.00）A.1B.2C.m-1D.0 或 m 解析：解析 在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一
26、个位置。因此，从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间，所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有 front=rear，而当循环队列空时也有 front=rear。即在循环队列中，当 front=rear 时，不能确定是队列满、还是队列空。当front=rear=1，要么队列为空，队列中的元素个数为 0，要么队列为满，队列中元素个数为 m。选项 D 正确。11.在最坏情况下（分数：2.00）A.快速排序的时间复杂度比冒泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的
27、时间复杂度要小 D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的解析：解析 按平均时间将排序分为四类：平方阶(O(n 2 )排序：各类简单排序，例如直接插入、直接选择和冒泡排序；线性对数阶(O(nlog 2 n)排序：如快速排序、堆排序和归并排序；O(n1+)排序：是介于 0 和 1 之间的常数。希尔排序便是一种；线性阶(O(n)排序：本程序中的基数排序，此外还有桶、箱排序。根据以上 4 点，可以判断选项 C 正确。12.在深度为 7 的满二叉树中，度为 2 的结点个数为（分数：2.00）A.64B.63 C.32D.31解析：解析 因为在任意的二叉树中，度为 0 的结点(即叶子结点)总
28、比度为 2 的结点的个数多 1 个，而度为 0 的结点数 n 0 =2 m-1 (其中 m 为二叉树的深度)。本题的度为 0 的结点个数 n 0 =2 7-1 =2 6 =64。因此，度为 2 的结点数 n 2 =n 0 -1=63。所以选项 B 正确13.设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00）A.30B.20C.m-19 D.m-20解析：解析 根据题意，栈空间如图所示： 14.算法空间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工
29、作单元D.执行算法所需要的存储空间 解析：解析 算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项 D 正确。15.设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4 B.6C.m-5D.m-6解析：解析 初始状态为 front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾 rear 减队头 front 等于 5 个
30、元素。此时队列中有 5 个元素，而查找最大项至少要比较 n-1 次，就是 4 次。因此选项 A 正确。16.下列叙述中正确的是（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构 解析：解析 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。17.某二叉树中有 n 个叶子结点，则该二叉树中度为 2 的结点数为（分数：2.00）A.n+1B.n-1 C.2nD.n/2解析：解析 对于任意一棵二叉树，如果其叶结点数
31、为 N 0 ，而度数为 2 的结点总数为 N 2 ，则 N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有 n 个叶子结点，则该二叉树中度为 2 的结点数为 n-1。因此选项B 正确。18.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系 D.算法的时间复杂度与空间复杂度没有必然的联系解析：解析 算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系
32、，但两者之间没有直接关系，因此选项 C 错误。19.设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈顶指针 top=30(指向栈项元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20 D.19解析：解析 在操作系统中，栈是向下生长的，如下图如示： 20.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.2B.3C.4 D.5解析：解析 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位
33、于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上：结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为： 21.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构 解析：解析 数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：有且只有一个
34、根结点；每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A、B 和 C 都不能判定是否是线性结构，选项 D 正确。22.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 D.以上三项都错误解析：解析 带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C 正确。23.设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20
35、，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（分数：2.00）A.5B.6C.m-5D.m-6 解析：解析 在循环队列中元素的个数为“(rear-front+M)%M”，式中 rear 为队尾指针，front 为队首指针，M 为存储容量，%为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为 0；运算后，元素个数为 m-5，找最小值的最坏情况下的比较次数为 m-5-1=m-6，选项 D 正确。24.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.0
36、0）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA 解析：解析 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下： 25.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果
37、有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构解析：解析 选项 A 叙述是错误的，例如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项 C 叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项 D 叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项 B 正确。26.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，
38、栈顶指针和栈底指针都是在动态变化的 C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上三项都错误解析：解析 栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项 C 的说法正确，选项 B 的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A 这一说法是正确的。27.设数据元素的集合 D=1，2，3，4，5，则满足下列关系 R 的数据结构中为线性结构的是（分数：2.00）A.R=(1，2)，(3，4)，(5，1)B.R=(
39、1，3)，(4，1)，(3，2)，(5，4) C.R=(1，2)，(2，3)，(4，5)D.R=(1，3)，(2，4)，(3，5)解析：解析 把每个答案中的第一个元素集合取出来，例如 A：(1，2)，先写下来就是 12，然后看后面的(3，4)，在(1，2)中找不到前驱和后继，只能和(1，2)暂时先并列，然后是(5，1)，这里我们已经写过12 了，那么 5 在 1 前面就是 512，但是 34 要单排，所以 A 就是两个根节点 3 和 5，两个顺序是 512，34。同理选项 B 是 541，32；选项 C 是：123 和 45；选项 D 是 135，24 所以选项 B 正确。28.下列叙述中正确
40、的是（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 B.线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空解析：解析 在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B、C、D 说法错误。选项 A 中，例如双向链表就具有两个指针，也属于线性结构，所以选项 A 正确。29.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素
41、依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDC D.CDE解析：解析 栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为 E、D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、C，所以选项 C 正确。30.某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.5B.4 C.3D.2解析：解析 该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点
42、 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B 正确。31.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间解析：解析 算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A 和选项 C 不
43、正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项 B 正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项 D 错误。32.下列各序列中不是堆的是（分数：2.00）A.(91，85，53，36，47，30，24，12)B.(91，85，53，47，36，30，24，12)C.(47，91，53，85，30，12，24，36) D.(91，85，53，47，30，12，24，36)解析：解析 堆可以看成一棵完全二叉树：任一根节点=左右孩子(或者=)，(大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于
44、又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91 是最大的根，而选项 C 是“左根右”的排序，那么 91 的左边只有 47，其他都在右边，而右边无法按照此顺序排列，所以选项 C 不是堆。33.深度为 5 的完全二叉树的结点数不可能是（分数：2.00）A.15 B.16C.17D.18解析：解析 对于满二叉树，叶子结点的数目等于 2(n-1)，n 为深度，这里就是 2 的 5-1=4 次方，就是16。所以选项 A 为正确答案。34.有二叉树如下图所示，则前序序列为 （分数：2.00）A.ABDEGCFH B.DBGEAFHCC.DGEBHFCAD.A
45、BCDEFGH解析：解析 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项 A 正确，选项 B 为中序遍历，选项 C 为后序遍历，选项 D 不正确。35.下列叙述中正确的是（分数：2.00）A.循环队列是顺序存储结构 B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象解析：解析 循环队列属于队列的特例和栈同属于线性结构，所以选项 C 不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢
46、出；假溢出是由于队尾 rear 的值和队头 front 的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项 A 正确，选项 B 不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项 D 不正确。36.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结
47、点的数据结构一定是非线性结构 解析：解析 只有一个空节点的结构也属数据结构，所以选项 A 和选项 B 不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项 C 不正确，选项 D 正确。37.下列关于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境 解析：解析 算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项 D 错误。38.设有二叉树如下图所
48、示，则中序序列为 （分数：2.00）A.ABDEGCFHB.DBGEAFHC C.DGEBHFCAD.ABCDEFGH解析：解析 中序遍历(LDR)是指首先遍历左子树，然后访问根结点，最后遍历右子树，选项 B 正确。39.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高 C.便于查找D.排序时减少元素的比较次数解析：解析 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大(=1)，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意
49、存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小(1)，存储空间利用率低，故选项 B 正确。40.深度为 7 的完全二叉树中共有 125 个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63 C.64D.65解析：解析 对于满二叉树，结点的数目等于 2 n -1，叶子结点数目为 2 n-1 ，n 为深度，这里就是 2的 7 次方-1，就是 127 个结点，叶子结点是 64 个。然而题目中只有 125 个结点，说明少了两个结点，那么就少了一个叶子结点，即 63 个。41.下列叙述中正确的是（分数：2.00）A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链按存储方式存储在不连续的存储空间内 D.任何存储方式的有序表均能采用二分法进行查找解析：解析 有序表可以用顺序存储空间内连续存放的元素序列来
