国家二级公共基础知识（数据结构与算法）模拟试卷26
单项选择题
1.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为(B)
A. 1
B. 2
C. 3
D. 不可能有这样的树
解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，那么树中最少有一个结点的度为3。而树中没有度为2的结点，叶子结点数为5，度为1的结点下面只有一个叶子结点。因此，该树中含2个度为3的结点满足题目要求。
2.设二叉树共有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。
3.下列叙述中正确的是(B)
A. 带链栈的栈底指针是固定的
B. 带链栈的栈底指针是随栈的操作而动态变化的
C. 若带链队列的队头指针与队尾指针相同，则队列为空
D. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素义称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。
4.带链队列空的条件是(A)
A. front=rear=NULL
B. front=rear=一1
C. front=NULL且rear=1
D. front=1且rear=NULL
解析：带链队列空的条件有两个：一个是front=rear，一个是他们都等于空。
5.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为(D)
A. 1
B. 2
C. 3
D. 不可能有这样的树
解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，也就是最少有一个度为3的结点。要求没有度为2的结点，且叶子结点为6，如果要有度为3的结点，那么最多只有5个叶子结点，而画不出6个叶子结点。因此这样的树是没有的。
6.下列叙述中正确的是(A)
A. 循环队列是线性结构
B. 循环队列是线性逻辑结构
C. 循环队列是链式存储结构
D. 循环队列是非线性存储结构
解析：为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
7.设某棵树的度为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。
8.设有一个栈与一个队列的初始状态均为空。现有一个序列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,F,E
C. A，B,C,D,E,F,G,H
D. A,B,C,D,H,G,F,E
解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D，C，B，A。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是，E,F,G,H。最后的顺序是：D，C，B，A，E，F，GH。
9.下列叙述中错误的是(B)
A. 具有两个根结点的数据结构一定属于非线性结构
B. 具有两个以上指针域的链式结构一定属于非线性结构
C. 具有两个以上叶子结点的数据结构一定属于非线性结构
D. 具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构
解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
10.下列结构中属于线性结构链式存储的是(A)
A. 双向链表
B. 循环队列
C. 二叉链表
D. 二维数组
解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。
11.下列叙述中错误的是(B)
A. 循环链表中有一个表头结点
B. 循环链表的存储空间是连续的
C. 循环链表实现了空表与非空表运算的统一
D. 循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
解析：循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，他不一定要是连续的存储空间，也可以是断开的空间。
12.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为(B)
A. 14
B. 15
C. 16
D. 不可能有这样的树
解析：根据题目可知本树中还有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设度为2的结点数为x，那么30=33+2x+1*4+1=2*x+14，由此可计算出x=8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30一3—8-4=15。
13.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为(A)
A. 7
B. 96
C. 48
D. 6
解析：二分查找又称折
本文档预览：3600字符，共10125字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
