国家二级ACCESS机试选择题（公共基础知识）模拟试卷3
选择题
1.下列叙述中正确的是( )。(A)
A. 带链栈的栈底指针是随栈的操作而动态变化的
B. 若带链队列的队头指针与队尾指针相同，则队列为空
C. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
D. 不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的
解析：由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。
2.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20，该栈中的元素个数为( )。(B)
A. 0
B. 1
C. 20
D. 不确定
解析：带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为NULL;栈中只有一个元素时，头指针和尾指针都指向这个元素。
3.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为( )。(D)
A. 0
B. 1
C. 10
D. 不确定
解析：带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当top=10，bottom=20时，不能确定栈中元素的个数。
4.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为( )。(B)
A. 0
B. 1
C. l或0
D. 不确定
解析：带链队列空时，头指针和尾指针都为NULL;队列中只有一个元素时，头指针和尾指针都指向这个元素。
5.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为( )。(D)
A. 4
B. 5
C. 6
D. 不确定
解析：带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front=10，rear=5时，不能确定队列中元素的个数。
6.下列叙述中错误的是( )。(B)
A. 循环链表中有一个表头结点
B. 循环链表是循环队列的存储结构
C. 循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
D. 循环链表实现了空表与非空表运算的统一
解析：循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。
7.某棵树中共有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的结点数不同，故不存在这样的树。
8.度为3的—棵树共有30个结点．其中度为3，1的结点个数分别为3，4。则该树中的叶子结点数为( )。(B)
A. 14
B. 15
C. 16
D. 不可能有这样的树
解析：设叶子结点数为n，则度为2的结点数为30 —3 —4 —n =23 —n，根据树中的结点数=树中所有结点的度之和+1，得3×3 +2×(23 —n)+1×4+0×n+1=30，则n=15。
9.深度为7的二叉树共有127个结点，则下列说法中错误的是( )。(B)
A. 该二叉树是满二叉树
B. 该二叉树有一个度为1的结点
C. 该二叉树是完全二叉树
D. 该二叉树有64个叶子结点
解析：满二叉树满足深度为m的二叉树最多有2n—1个结点，本题中二叉树深度为7且有127个结点，满足27 —1 =127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第k层上有2k—1结点，则该二叉树的叶子结点数为27—1= 64个。满二叉树不存在度为1的结点。
10.深度为5的完全二叉树的结点数不可能是( )。(A)
A. 15
B. 16
C. 17
D. 18
解析：设完全二叉树的结点数为n，根据深度为k的二叉树至多有2k —1个结点，再根据完全二叉树的定义可知，2k—1—1＜n≤2k—1。本题中完全二叉树的深度为5，则25—1—1 ＜n≤25—1，15＜ n≤31。因此，结点数不能为15。
11.某完全二叉树共有256个结点，则该完全二叉树的深度为( )。(C)
A. 7
B. 8
C. 9
D. 10
解析：根据完全二叉树的性质：具有n个结点的完全二叉树的深度为[log：n]+1。本题中完全二叉树共有256个结点，则深度为[log2256]+1=8+1=9。
12.在具有2n个结点的完全二叉树中，叶子结点个数为( )。(A)
A. n
B. n+1
C. n—1
D. n/2
解析：由二叉树的定义可知，树中必定存在度为O的结点和度为2的结点，设度为O结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有a—1个。再根据完全二叉树的定义，度为1的结点有0个或1个，假设度1结点为0个，a+0+a—1=2n，得2a =2n —1，由于结点个数必须为整数，假设不成立；当度为1的结点为1个时，a+1+a —1=2n，得a=n，即叶子结点个数为n。
13.下列叙述中正确的是( )。(C)
A. 非完全二叉树可以采用顺序存储结构
B. 有两个指针域的链表就是二叉链表
C. 有的二叉树也能用顺序存储结构表示
D. 顺序存储结构一定是线性结构
解析：在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此A项错误，C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此D项错误。双向链表也有两个指针域，因此B项错误。
14.有二叉树如下图所示：
(A)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDFGCFH。
中序遍历首先遍历左子树，然后访问跟结点
本文档预览：3600字符，共10463字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
