国家二级ACCESS机试选择题（数据结构与算法）模拟试卷25
选择题
1.设有一个栈与一个队列的初始状态均为空。现有一个序列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，E，F
解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D，C，B，A。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是E，F，G，H。最后的顺序是：D，C，B，A，E，F，G，H。
2.下列叙述中错误的是(B)
A. 具有两个根结点的数据结构一定属于非线性结构
B. 具有两个以上指针域的链式结构一定属于非线性结构
C. 具有两个以上叶子结点的数据结构一定属于非线性结构
D. 具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构
解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
3.下列结构中属于线性结构链式存储的是(A)
A. 双向链表
B. 循环队列
C. 二叉链表
D. 二维数组
解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。
4.下列叙述中错误的是(B)
A. 循环链表中有一个表头结点
B. 循环链表的存储空间是连续的
C. 循环链表实现了空表与非空表运算的统一
D. 循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。
5.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为(B)
A. 14
B. 15
C. 16
D. 不可能有这样的树
解析：根据题目可知本树中还有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设度为2的结点数为x，那么30=3*3+2*×+1*4+1=2*x+14，由此可计算出x=8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30-3-8-4=15。
6.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为(A)
A. 7
B. 96
C. 48
D. 6
解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k=log2n。其中n代表长度，k为比较次数。本题中可以计算出k=7。
7.下列结构中属于非线性结构的是(B)
A. 二叉链表
B. 二维数组
C. 循环队列
D. 双向链表
解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。
8.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是(A)
A. 循环链表
B. 双向链表
C. 单向链表
D. 二叉链表
解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。
9.设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为(A)
A. HGFEDCBA
B. ABCDEFGH
C. ABCDHGFE
D. DCBAHGFE
解析：前序遍历(DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历(LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右：后序遍历(LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。根据题中前序和中序序列均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为，GFEDCBA。
10.设某棵树的度为3，其中度为3、1、0的结点个数分别为3、4、15。则该树中总结点数为(B)
A. 22
B. 30
C. 35
D. 不可能有这样的树
解析：本题采用画图法来求出结果。首先先画出包含3个度为3的结点；然后再添加4个度为1的结点，此时最大度为0的结点数为8。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为2的结点，直到度为0的结点数位15。画图结束后，不管是什么样的树，总结点数都是30。
11.下列叙述中正确的是(B)
A. 矩阵是非线性结构
B. 数组是长度固定的线性表
C. 对线性表只能作插入与删除运算
D. 线性表中各元素的数据类型可以不同
解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。
12.在快速排序法中，每经过一次数据交换(或移动)后(A)
A. 能消除多个逆序
B. 只能消除一个逆序
C. 不会产生新的逆序
D. 消除的逆序个数一定比新产生的逆序个数多
解析：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
13.线性表的长度为n。在最坏情况下，比较次数为n-1的算法是(C)
A. 顺序查找
B. 有序表的插入
C. 寻找最大项
D. 同时寻找最大项与最小项
解析：寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为n-1。
14.设某棵树的度为3，其中度为2、1、0的结点个数分别为3、4、15。则该树中总结点数为(D)
A. 22
B. 30
C. 35
D. 不可能有这样的树
解析：本题采用画图法来求出结果。首先先画出包含3个度为2的结点；然后再添加4个度为1的结点。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为3的结
本文档预览：3600字符，共8275字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
