国家二级MS Office高级应用机试（选择题）模拟试卷89
选择题
1.下列叙述中正确的是( )。(C)
A. 非完全二叉树可以采用顺序存储结构
B. 有两个指针域的链表就是二叉链表
C. 有的二叉树也能用顺序存储结构表示
D. 顺序存储结构一定是线性结构
解析：在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此A项错误，c项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此D项错误。双向链表也有两个指针域，因此B项错误。
2.有二叉树如下图所示：
(A)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。
中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是DBGEAFHC。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是DGEBHFCA。
3.设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为( )。(B)
A. JIHGFEDCBA
B. DGHEBHFCA
C. GHIJDEFBCA
D. ABCDEFGHIJ
解析：二叉树的前序序列为ABDEGHCFIJ，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是A。再由中序序列为DBGEHACIFJ，可以得到结点D、B、G、E、H位于根结点的左子树上，结点C、I、F、J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点A。采用排除法可知，后续序列为DGHEBIJFCA。
4.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBEDA，则前序遍历序列为( )。(C)
A. CBADE
B. CBEDA
C. ABCDE
D. EDCBA
解析：二叉树的后序遍历序列为CBEDA，由于后序遍历最后访问根结点，可以确定该二叉树的根结点是A。再由中序遍历序列为CBADE，可以得到子序列(CB)一定在左子树中，子序列(DE)一定在右子树中。结点C、B在中序序列和后序序列中顺序未变，说明结点B是结点c的父结点；结点D、E在中序序列和后序序列中顺序相反，说明结点D是结点E的父结点。因此该二叉树的前序遍历序列为ABCDE。
5.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度(根结点在第1层)为( )。(C)
A. 2
B. 3
C. 4
D. 5
解析：二叉树的前序序列为ABCDEFG，则A为根结点；中序序列为DCBAEFG，可知结点D、C、B位于根结点的左子树上，结点E、F、G位于根结点的右子树上。另外，结点B、C、D在前序序列和中序序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为4。
6.某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为( )。(C)
A. HGFEDCBA
B. HFDBGECA
C. ABCDEFGH
D. ACEGBDFH
解析：二叉树的前序序列为ABDFHCEG，可以确定这个二叉树的根结点是A；再由中序序列HFDBACEG，可以得到HFDB为根结点A的左子树，CEG为根结点A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到该二叉树的结构如下：
7.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为( )。(B)
A. ABCDEFGH
B. ABDHECFG
C. HDBEAFCG
D. HDEBFGCA
解析：完全二叉树的特点是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为ABCDEFGH，可以得到该二叉树的结构如下：
8.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是( )。(B)
A. 前序序列
B. 中序序列
C. 后序序列
D. 前序序列或后序序列
解析：中序遍历的次序是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子树结点值＜根结点值≤右子树结点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。
9.设二叉树中共有15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为( )。(C)
A. 4
B. 6
C. 15
D. 不存在这样的二叉树
解析：在具有n个结点的二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为n。故本题中二叉树的深度为15。
10.在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为( )。(D)
A. n／4
B. n
C. 3n／4
D. (n+1)／2
解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。则平均比较次数：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2。
11.在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。(B)
A. n
B. 3n／4
C. n／2
D. n／4
解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。这是找到元素的情况。如果没有找到元素，则要比较n次。因此，平均需要比较：找到元素的情况×
