国家二级ACCESS机试（选择题）模拟试卷327
选择题
1.下列叙述中错误的是( )。(B)
A. 循环链表中有一个表头节点
B. 循环链表是循环队列的存储结构
C. 循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点
D. 循环链表实现了空表与非空表运算的统一
解析：循环链表是指在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，最后一个节点的指针域的值由NULL改为指向表头节点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。
2.某棵树中共有25个节点，且只有度为3的节点和叶子节点，其中叶子节点有7个，则该树中度为3的节点数为( )。(D)
A. 6
B. 7
C. 8
D. 不存在这样的树
解析：根据题意，树中只有度为3的节点和叶子节点(7个)，则度为3的节点有25—7=18个；又根据树中的节点数：树中所有节点的度之和+1，设度为3的节点数为n，则3n+1=25，得n=8。两种方式得到的度为3的节点数不同，故不存在这样的树。
3.度为3的一棵树共有30个节点，其中度为3，l的节点个数分别为3．4。则该树中的叶子节点数为( )。(B)
A. 14
B. 15
C. 16
D. 不可能有这样的树
解析：设叶子节点数为n，则度为2的节点数为30－3－4－n=23－n，根据树中的节点数=树中所有节点的度之和+l，得3×3+2×(23一n)+l×4+0×n+1=30，则n=15。
4.深度为7的二叉树共有127个节点，则下列说法中错误的是( )。(B)
A. 该二叉树是满二叉树
B. 该二叉树有一个度为1的节点
C. 该二叉树是完全二叉树
D. 该二叉树有64个叶子节点
解析：满二叉树满足深度为m的二叉树最多有2m－1个节点，本题中二叉树深度为7且有127个l忡点，满足27一l=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第k层上有2k-1节点，则该二叉树的叶子节点数为27-1=64个。满二叉树不存在度为l的节点。
5.深度为5的完全二叉树的节点数不可能是( )。(A)
A. 15
B. 16
C. 17
D. 18
解析：设完全二叉树的节点数为n，根据深度为k的二叉树至多有2k一1个节点，再根据完全二叉树的定义可知，2k-1一1＜n≤2k一1。本题中完全二叉树的深度为5，则25-1一l<n≤25－l，15＜n≤31。因此，节点数不能为15。
6.某完全二叉树共有256个节点，则该完全二叉树的深度为( )。(C)
A. 7
B. 8
C. 9
D. 10
解析：根据完全二叉树的性质：具有n个节点的完全二叉树的深度为[log2n]+l。本题中完全二叉树共有256个节点，则深度为[log2256]+l=8+1=9。
7.在具有2n个节点的完全二叉树中，叶子节点个数为( )。(A)
A. n
B. n+l
C. n—l
D. n／2
解析：由二叉树的定义可知，树中必定存在度为O的节点和度为2的节点，设度为0节点有a个，根据度为0的节点(即叶子节点)总比度为2的节点多一个，得度为2的节点有a一1个。再根据完全二叉树的定义，度为1的节点有0个或1个，假设度l节点为0个，a+0+a一1=2n，得2a=2n一1，由于节点个数必须为整数，假设不成立；当度为1的节点为1个时，a+1+a一1=2n，得a=n，即叶子节点个数为n。
8.下列叙述中正确的是( )。(C)
A. 非完全二叉树可以采用顺序存储结构
B. 有两个指针域的链表就是二叉链表
C. 有的二叉树也能用顺序存储结构表示
D. 顺序存储结构一定是线性结构
解析：在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此A项错误，C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此D项错误。双向链表也有两个指针域，因此B项错误。
9.有二叉树如下图所示：
(A)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。
中序遍历首先遍历左子树，然后访问跟节点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟节点，最后遍历右子树。故本题的中序序列是DBGEAFHC。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。故本题的后序序列是DGEBHFCA。
10.设二叉树的前序序列为ABDEGf：ICFIJ，中序序列为DBGEHACIFJ。则后序序列为( )。(B)
A. JIHGFEDCBA
B. DGHEBIJFCA
C. GHIJDEFBCA
D. ABCDEFGHIJ
解析：二叉树的前序序列为ABDEGHCFH，由于前序遍历首先访问根节点，可以确定该二叉树的根节点是A。再由中序序列为DBGEHACIFJ，可以得到节点D、B、G、E、H位于根节点的左子树上，节点C、I、F、J位于根节点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D节点；再由后序遍历是最后访问根节点，故本题后序遍历最后访问的节点是根节点A。采用排除法可知，后续序列为。DGHEBHFCA。
11.某二叉树的中序遍历序列为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。
12.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度(根节点在第l层)为( )。(C)
A. 2
B. 3
C. 4
D. 5
解析：二叉树的前序序列为ABCDEFG，则A为根节点；中序序列为DCBAEFG，可知节点D、C、B位于根节点的左子树上，节点E、F、G位于根节点的右子树上。另外，节点B、C、D在前序序列和中序序列中顺序相反，则说明这三个节点依次位于前一个节点的左子树上；节点E、F、G顺序未变，则说明这三个节
本文档预览：3600字符，共9398字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
