国家二级ACCESS机试选择题（数据结构与算法）模拟试卷6(总分：84.00，做题时间：90分钟)一、选择题(总题数：42，分数：84.00)1.带链栈空的条件是（分数：2.00）A.top=bottom=NULL √B.top=-I且bottom=NULLC.top=NULL且bottom-1D.top=bottom=-1解析：解析：栈的链式存储结构称为链栈。
在链栈中，只会出现栈空和非空两种状态。
当栈为空时，有top=bottom=NULL；当栈非空时，top指向链表的第一个结点(栈顶)。
所以选项A正确。
2.设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。
该树中度为3的结点数为（分数：2.00）A.1 √B.2C.3D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n 3 =(0*6+1*1+2*3+3*n3)+1。
运算结果n 3 =1。
其中，n 3表示度为3的结点数，所以选项A正确。
3.下列数据结构中，不能采用顺序存储结构的是（分数：2.00）A.栈B.堆C.队列D.非完全二叉树√解析：解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。
4.设二叉树共有375个结点，其中度为2的结点有187个。
则度为1的结点个数是（分数：2.00）A.0 √B.1C.188D.不可能有这样的二叉树解析：解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2 i-1个结点；深度为k的二叉树至多有2k一1个结点；对任何一棵二叉树T，如果其终端结点数为n 0，度为2的结点数为n 2，则n 0 =n 2 +1。
本题中，度为2的结点有187个，叶子结点应该有187+1=188个，度为1的结点个数=375—187-188=0。
5.在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为（分数：2.00）A.0或1 √B.0C.1D.队列满解析：解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的链式存储也称为链队列。
为了便于操作，可给链队列添加1个头结点，并令头指针指向头结点。
队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。
当队列为空(0)或1时，front=rear。
6.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。
该树中度为3的结点数为（分数：2.00）A.1B.2 √C.3D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。
本题中树的度为3，那么树中最少有一个结点的度为3。
而树中没有度为2的结点，叶子结点数为5，度为1的结点下面只有一个叶子结点。
因此，该树中含2个度为3的结点满足题目要求。
7.设二叉树共有500个结点，其中叶子结点有250个。
则度为2的结点个数是（分数：2.00）A.0B.1C.249 √D.不可能有这样的二叉树解析：解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2 i-1个结点；深度为k的二叉树至多有2 k-1个结点；对任何一棵二叉树T，如果其终端结点数为n 0，度为2的结点数为n 2，则n 0 =n 2 +1。
本题中，叶子结点有250个，度为2的结点数为n 2 =n 0 -1=250-1=249。
8.下列叙述中正确的是（分数：2.00）A.带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的√C.若带链队列的队头指针与队尾指针相同，则队列为空D.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。
其限制是仅允许在表的一端进行桶入和删除运算。
这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈项元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。
9.带链队列空的条件是（分数：2.00）A.front=rear=NULL √B.front=rear=-1C.front=NULL且rear=-1D.front=-1且rear=NULL解析：解析：带链队列空的条件有两个：一个是front=rear，一个是它们都等于空。
10.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。
该树中度为3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树√解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。
本题中树的度为3，也就是最少有一个度为3的结点。
要求没有度为2的结点，且叶子结点为6，如果要有度为3的结点，那么最多只有5个叶子结点，而画不出6个叶子结点。
因此这样的树是没有的。
11.下列叙述中正确的是（分数：2.00）A.循环队列是线性结构√B.循环队列是线性逻辑结构C.循环队列是链式存储结构D.循环队列是非线性存储结构解析：解析：为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。
存储在其中的队列称为循环队列(Circular Queue)。
线性结构是一个有序数据元素的集合。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
12.设某棵树的度为3，其中度为3、2、1的结点个数分别为3、0、4。
则该树中的叶子结点数为（分数：2.00）A.7 √B.8C.6D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为“树的度”。
根据题目可知本树中没有度为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个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。
最后得到的序列为（分数：2.00）A.D,C,B,A，E,F,G,H √B.D,C,B,A，H,G,EEC.A,B,C,D,E,F,G,HD.A,B,C,D,H,G,EE解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。
其限制是仅允许在表的一端进行插入和删除运算。
因此栈的出栈顺序是先入后出，所以顺序是D,C,B,A。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
因此，队的出队顺序是，先入先出，所以顺序是：E,F,G,H。
最后的顺序是：D,C,B,A，E，F，G，H。
14.下列叙述中错误的是（分数：2.00）A.具有两个根结点的数据结构一定属于非线性结构B.具有两个以上指针域的链式结构一定属于非线性结构√C.具有两个以上叶子结点的数据结构一定属于非线性结构D.具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构解析：解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
15.下列结构中属于线性结构链式存储的是（分数：2.00）A.双向链表√B.循环队列C.二叉链表D.二维数组解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。
数据的存储结构是指数据的逻辑结构在计算机中的表示。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。
循环队列、二叉链表和二维数组都是顺序存储结构。
16.下列叙述中错误的是（分数：2.00）A.循环链表中有一个表头结点B.循环链衷的存储空间是连续的√C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点解析：解析：循环链表是另一种形式的链式存储结构。
它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。
17.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。
则该树中的叶子结点数为（分数：2.00）A.14B.15 √C.16D.不可能有这样的树解析：解析：根据题目可知本树中还有度为2的结点。
树的总结点=(度1*个数+度2*个数…)+1，这里我们设度为2的结点数为x，那么30=3*3+2*x+1*4+1=2*x+14，由此可计算出x=8。
树的叶子结点数等于总结点减去所有度不为0的结点，也就是30—3—8—4=15。
18.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为（分数：2.00）A.7 √B.96C.48D.6解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
最多比较次数的计算方式：k=log 2 n。
其中n代表长度，k为比较次数。
本题中可以计算出k=7。
19.下列结构中属于非线性结构的是（分数：2.00）A.二叉链表B.二维数组√C.循环队列D.双向链表解析：解析：线性结构是一个有序数据元素的集合。
常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
循环队列、双向链表和二叉锌表都是线性结构，而二维数组是非线性结构。
20.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（分数：2.00）A.循环链表√B.双向链表C.单向链表D.二叉链表解析：解析：循环链表是另一种形式的链式存储结构。