国家二级MS Office高级应用机试（选择题）模拟试卷260 (题后含
答案及解析)
题型有：1. 选择题
选择题
1． 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)／2的排序方法是
A．快速排序 B．冒泡排序
C．直接插入排序 D．堆排序
正确答案：D
解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序n(n-1)／2、快速排序n(n-1)／2、简单插入排序n(n-1)／2、希尔排序O(n1.5)、简单选择排序n(n-1)／2、堆排序O(nlog2n)。 知识模块：算法与数据结构
2． 对于循环队列，下列叙述中正确的是 A．队头指针是固定不变的 B．队头指针一定大于队尾指针 C．队头指针一定小于队尾指针
D．队头指针可以大于队尾指针，也可以小于队尾指针
正确答案：D 解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。 知识模块：算法与数据结构
3． 下列叙述中正确的是
A．栈是“先进先出”的线性表 B．队列是“先进后出”的线性表 C．循环队列是非线性结构
D．有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
正确答案：D 解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，
队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。 知识模块：算法与数据结构
4． 下列叙述中正确的是
A．在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 B．在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C．在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D．上述三种说法都不对
正确答案：C
解析：在栈中，允许插入与删除的一端称为栈项，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。 知识模块：算法与数据结构
5． 下列叙述中正确的是
A．循环队列是队列的一种链式存储结构 B．循环队列是队列的一种顺序存储结构 C．循环队列是非线性结构 D．循环队列是一种逻辑结构
正确答案：B 解析：本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。 知识模块：算法与数据结构
6． 设二叉树共有150个结点，其中度为l的结点有l0个，则该二叉树中的叶子结点数为
A．71 B．70 C．69
D．不可能有这样的二叉树
正确答案：D
解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。即有n0=n2+l。对于这个题来说，总结点数150=n0+n1+n2=n2+1+lO+n2=2n2+ll，所以2n2=139，度为2个结点个数不能确定。选项D正确。 知识模块：算法与数据结构
7． 一棵二叉树有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为
A．219 B．229
C．230 D．231
正确答案：B
解析：根据二叉树的性质，在任意二叉树中，度为O的结点(即叶子结点)总是比度为2的结点多一个，故总结点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。 知识模块：算法与数据结构
8． 下列叙述中错误的是
A．在双向链表中，可以从任何一个结点开始直接遍历到所有结点 B．在循环链表中，可以从任何一个结点开始直接遍历到所有结点 C．在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 D．在二叉链表中，可以从根结点开始遍历到所有结点
正确答案：C 解析：线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项C的描述是错误的。 知识模块：算法与数据结构
9． 设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为
A．BCA B．CBA C．ABC D．CAB
正确答案：C 解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下：因此，这棵二叉树的前序是ABC，选项C正确。 知识模块：算法与数据结构
10． 算法空间复杂度的度量方法是 A．算法程序的长度 B．算法所处理的数据量
C．执行算法所需要的工作单元 D．执行算法所需要的存储空间
正确答案：D 解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的
度量，因此选项D正确。 知识模块：算法与数据结构
11． 下列叙述中正确的是
A．存储空间连续的数据结构一定是线性结构 B．存储空间不连续的数据结构一定是非线性结构 C．没有根结点的非空数据结构一定是线性结构 D．具有两个根结点的数据结构一定是非线性结构
正确答案：D
解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A、B和c都不能判定是否是线性结构，选项D正确。 知识模块：算法与数据结构
12． 下列叙述中正确的是
A．链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构
B．线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针
C．线性表的链式存储结构中，每个结点只能有一个指向后件的指针 D．线性表的链式存储结构中，叶子结点的指针只能是空
正确答案：A
解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B、C、D说法错误。选项A中，例如双向链表就具有两个指针，也属于线性结构，所以选项A正确。 知识模块：算法与数据结构
13． 下列叙述中正确的是 A．循环队列是顺序存储结构 B．循环队列是链式存储结构 C．循环队列是非线性结构
D．循环队列的插入运算不会发生溢出现象
正确答案：A
解析：循环队列属于队列的特例和栈同属于线性结构，所以选项C不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头。front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A正确，选项B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢
出，故选项D不正确。 知识模块：算法与数据结构
14． 设有二叉树如下图所示，则后序序列为 A．ABDEGCFH B．DBGEAFHC C．DGEBHFCA D．ABCDEFGH
正确答案：C
解析：后序遍历(LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项C正确。 知识模块：算法与数据结构
15． 设栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为
A．1 B．0 C．50 D．49
正确答案：A
解析：栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中有51-50=1个元素，因此选项A正确。 知识模块：算法与数据结构
16． 在具有2n个结点的完全二叉树中，叶子结点个数为 A．n B．n+1 C．n-1 D．n／2
正确答案：A 解析：在具有2n个结点的完全二叉树中，叶子结点个数为：(2n+1)／2取整，其值等于n。所以选项A正确。 知识模块：算法与数据结构
17． 在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为
A．(3+n)／4 B．n C．n／2 D．n／4
正确答案：A
解析：在长度为n的顺序表中查找一个元素，最好的情况是目标在第一个，
一次找到；最坏的情况是目标在最后一个，n次找到。那么平均长度为：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2。本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为((1+n)／2+1)／2=(3+n)／4。所以选项A正确。 知识模块：算法与数据结构
18． 循环队列的存储空间为Q(1：100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为
A．0或100 B．1 C．2 D．99
正确答案：A
解析：循环队列中，由于入队时尾指针rear向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为O)，要么队列为满(元素个数为100)，因此选项A正确。 知识模块：算法与数据结构
19． 某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)的序列为
A．ABCDEF B．BCDEFA C．FEDCBA D．DEFABC
正确答案：A
解析：前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道：①前序遍历中第一个就是树根结点，即A结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即BCDEF是根结点A的右子树集合。问题就会转化为：求前序遍历是BCDEF，中序遍历是BCDEF的子树，方法同上。详细推理过程：步骤l：由ABCDEF得出根结点为A，由中序遍历可知：左子树为空，A{BCDE F}；步骤2：由BCDEF得出右子树集合的根节点为B，由中序可知：左子树为空，B{CDEF}；步骤3：同理，二叉树更新后如下。所以按层次输出(同一层从左到右)的序列为ABCDEF，选项A正确。 知识模块：算法与数据结构
20． 下列各排序法中，最坏情况下时间复杂度最小的是 A．堆排序 B．快速排序 C．希尔排序 D．冒泡排序
正确答案：A
解析：快速排序、冒泡排序最坏情况下时间复杂度是O(n2)，；希尔排序最坏情况下时间复杂度是O(n1.2)。堆排序最坏情况下时间复杂度是O(nlog2n)，所以选项A正确。 知识模块：算法与数据结构
21． 下列叙述中正确的是
A．解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 B．解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的 C．解决一个问题的算法是唯一的
D．算法的时间复杂度与计算机系统有关
正确答案：A 解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有10种左右算法，它们复杂度显然是不一样的。所以选项A正确。 知识模块：算法与数据结构
22． 设一棵树的度为3，共有27个结点，其中度为3，2，O的结点数分别为4，1，10。该树中度为1的结点数为
A．11 B．12 C．13
D．不可能有这样的树
正确答案：B
解析：因为任一棵树中，结点总数=总分支数目+1，所以：27=(O*10+n1*1+2*1+3*4)+l。运算结果n1=12。其中，n1表示叶子结点，所以选项B正确。 知识模块：算法与数据结构
23． 在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为
A．0或1 B．0 C．1
D．队列满
正确答案：A
解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添加1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空 (0)或1时，front=rear。 知识模块：算法与数据结构
24． 设某棵树的度为3，其中度为3、2、l的结点个数分别为3、0、4。则
该树中的叶子结点数为
A．7 B．8 C．6
D．不可能有这样的树
正确答案：A
解析：树的度是指一棵树中，最大的结点的度称为“树的度”。根据题目可知本树中没有度为2的结点。树的总结点：(度1*个数+度2*个数…)+1，这里我们设总结点数为n，那么n=3*3+2*O+1*4+1=14。树的叶子结点数等于总结点减去所有度不为O的结点，也就是14-3-4=7。 知识模块：算法与数据结构
25． 下列结构中属于非线性结构的是 A．二叉链表 B．二维数组 C．循环队列 D．双向链表
正确答案：B
解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，数组，广义表，树(二叉树等)，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。 知识模块：算法与数据结构
26． 设某棵树的度为3，其中度为2、1、0的结点个数分别为3、4、15。则该树中总结点数为
A．22 B．30 C．35
D．不可能有这样的树
正确答案：D
解析：本题采用画图法来求出结果。首先，先画出包含3个度为2的结点；然后，添加4个度为1的结点。根据题目中描述的度为O的结点数有15个，这时要在书中添加度为3的结点，不管怎么添加都不能添加出15个度为O的结点，因此不可能有这样的树。 知识模块：算法与数据结构
27． 设循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的操作后，front=1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
A．0 B．1 C．48 D．49
正确答案：C
解析：front指向队头位置，删除一个元素就将front顺时针移动一位；rear指尾指针，指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；操作后，循环队列的队头指针一1等于尾指针，说明出队一位，那么总数就是49了。在该队列中寻找最大值元素，最多比较次数是总数-1，因此是49-l=48次。 知识模块：算法与数据结构
28． 设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是
A．堆排序
B．有序链表查找 C．希尔排序
D．循环链表中寻找最大项
正确答案：D
解析：在循环链表中寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为n-1。 知识模块：算法与数据结构
