国家二级ACCESS机试选择题（数据结构与算法）模拟试卷6
选择题
1.带链栈空的条件是(A)
A. top=bottom=NULL
B. top=-I且bottom=NULL
C. top=NULL且bottom-1
D. top=bottom=-1
解析：栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈非空时，top指向链表的第一个结点(栈顶)。所以选项A正确。
2.设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为(A)
A. 1
B. 2
C. 3
D. 不可能有这样的树
解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果n3=1。其中，n3表示度为3的结点数，所以选项A正确。
3.下列数据结构中，不能采用顺序存储结构的是(D)
A. 栈
B. 堆
C. 队列
D. 非完全二叉树
解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。
4.设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是(A)
A. 0
B. 1
C. 188
D. 不可能有这样的二叉树
解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k一1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，度为2的结点有187个，叶子结点应该有187+1=188个，度为1的结点个数=375—187-188=0。
5.在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为(A)
A. 0或1
B. 0
C. 1
D. 队列满
解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添加1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空(0)或1时，front=rear。
6.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为(B)
A. 1
B. 2
C. 3
D. 不可能有这样的树
解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，那么树中最少有一个结点的度为3。而树中没有度为2的结点，叶子结点数为5，度为1的结点下面只有一个叶子结点。因此，该树中含2个度为3的结点满足题目要求。
7.设二叉树共有500个结点，其中叶子结点有250个。则度为2的结点个数是(C)
A. 0
B. 1
C. 249
D. 不可能有这样的二叉树
解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，叶子结点有250个，度为2的结点数为n2=n0-1=250-1=249。
8.下列叙述中正确的是(B)
A. 带链栈的栈底指针是固定的
B. 带链栈的栈底指针是随栈的操作而动态变化的
C. 若带链队列的队头指针与队尾指针相同，则队列为空
D. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行桶入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈项元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。
9.带链队列空的条件是(A)
A. front=rear=NULL
B. front=rear=-1
C. front=NULL且rear=-1
D. front=-1且rear=NULL
解析：带链队列空的条件有两个：一个是front=rear，一个是它们都等于空。
10.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为(D)
A. 1
B. 2
C. 3
D. 不可能有这样的树
解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，也就是最少有一个度为3的结点。要求没有度为2的结点，且叶子结点为6，如果要有度为3的结点，那么最多只有5个叶子结点，而画不出6个叶子结点。因此这样的树是没有的。
11.下列叙述中正确的是(A)
A. 循环队列是线性结构
B. 循环队列是线性逻辑结构
C. 循环队列是链式存储结构
D. 循环队列是非线性存储结构
解析：为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
12.设某棵树的度为3，其中度为3、2、1的结点个数分别为3、0、4。则该树中的叶子结点数为(A)
A. 7
B. 8
C. 6
D. 不可能有这样的树
解析：树的度是指一棵树中，最大的结点的度称为“树的度”。根据题目可知本树中没有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设总结点数为n，那么n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为0的结点，也就是14—3—4=7。
13.设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G，H。先分别将序列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为(A)
A. D,C,B,A，E,F,G,H
B. D,C,B,A，H,G,EE
C. A,B,C,D,E,F,G,H
D. A,B,C,D,H,G,EE
本文档预览：3600字符，共11569字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
