1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 3及答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.在最坏情况下（分数：2.00）A.快速排序的时间复杂度比冒泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的2.在深度为 7的满二叉树中，度为 2的结点个数为（分数：2.00）A.64B.63C.32D.313.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后，t
2、op=20，则当前栈中的元素个数为（分数：2.00）A.30B.20C.m-19D.m-204.算法空间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间5.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4B.6C.m-5D.m-66.下列叙述中正确的是（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性
3、结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构7.某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为（分数：2.00）A.n+1B.n-1C.2nD.n28.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系D.算法的时间复杂度与空间复杂度没有必然的联系9.设栈的顺序存储空间为 S(0：49)，栈底指针 bottom=49，栈顶指针。top=30(指向栈顶元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20D.19
4、10.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1层)为（分数：2.00）A.2B.3C.4D.511.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构12.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D.
5、以上三项都错误13.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（分数：2.00）A.5B.6C.m-5D.m-614.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA15.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相
6、等，则该链表一定是非线性结构C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构16.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上三项都错误17.设数据元素的集合 D=1，2,3,4，5)，则满足下列关系 R的数据结构中为线性结构的是（分数：2.00）A.R=(1，2)，(3,4)，(5，1)B.R=(1，3)，(4，1)，(3,2)，(5,4)C.R=
7、(1，2)，(2,3)，(4,5)D.R=(1，3)，(2,4)，(3,5)18.下列叙述中正确的是（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B.线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空19.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDCD.CD
8、E20.某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度(根结点在第 1层)为（分数：2.00）A.5B.4C.3D.221.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间22.下列各序列中不是堆的是（分数：2.00）A.(9l，85,53,36,47,30,24，12)B.(91，85,53,47,36,30,24，12)C.(47,91，53,85,30，12,24,36)D.(91，85,53,47,30，12,24,36)23.深度为 5的
9、完全二叉树的结点数不可能是（分数：2.00）A.15B.16C.17D.1824.有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH25.下列叙述中正确的是（分数：2.00）A.循环队列是顺序存储结构B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象26.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构27.下列关
10、于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境28.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH29.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高C.便于查找D.排序时减少元素的比较次数30.深度为 7的完全二叉树中共有 125个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63C
11、.64D.65国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 3答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.在最坏情况下（分数：2.00）A.快速排序的时间复杂度比冒泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小 D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的解析：解析：按平均时间将排序分为四类：平方阶(O(n 2 )排序：各类简单排序，例如直接插入、直接选择和冒泡排序；线性对数阶(O(n。log2n)排序：如快速排序、堆排序和归并排序；O(
12、n1+)排序：是介于 0和 1之间的常数。希尔排序便是一种；线性阶(O(n)排序：本程序中的基数排序，此外还有桶、箱排序。2.在深度为 7的满二叉树中，度为 2的结点个数为（分数：2.00）A.64B.63 C.32D.31解析：解析：因为在任意的二叉树中，度为 O的结点(即叶子结点)总比度为 2的结点的个数多 1个，而度为 0的结点数 n 0 =2 m-1 (其中 m为二叉树的深度)。本题的度为 0的结点个数 n 0 =2 7-1 =2 6 =64。因此，度为 2的结点数 n 2 =n 0 -1=63。所以选项 B正确3.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过
13、一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00）A.30B.20C.m-19 D.m-20解析：解析：根据题意，栈空间如下图所示。4.算法空间复杂度的度量方法是（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项 D正确。5.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（
14、分数：2.00）A.4 B.6C.m-5D.m-6解析：解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15,rear=20。队尾大手队头，则队尾 rear减队头 front等于 5个元素。此时队列中有 5个元素，而查找最大项至少要比较 n一 1次，就是 4次。因此选项 A正确。6.下列叙述中正确的是（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构 解析：解析：顺序存储方式不仅能用于存储线性结构，还可以用来存
15、放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。7.某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为（分数：2.00）A.n+1B.n-1 C.2nD.n2解析：解析：对于任意一棵二叉树，如果其叶结点数为 N 0 ，而度数为 2的结点总数为 N 2 ，则 N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 n一 1。因此选项B正确。8.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的
16、时间复杂度与空间复杂度有直接关系 D.算法的时间复杂度与空间复杂度没有必然的联系解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项 C错误。9.设栈的顺序存储空间为 S(0：49)，栈底指针 bottom=49，栈顶指针。top=30(指向栈顶元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20 D.19解析：解析：在操作系统中，栈是向下生长的，如下图如示：10.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的
17、深度(根结点在第 1层)为（分数：2.00）A.2B.3C.4 D.5解析：解析：该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为：11.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是
18、线性结构D.具有两个根结点的数据结构一定是非线性结构 解析：12.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 D.以上三项都错误解析：解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C正确。13.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数
19、为（分数：2.00）A.5B.6C.m-5D.m-6 解析：解析：在循环队列中元素的个数为“(rearfront+M)M”，式中 rear为队尾指针，front 为队首指针，M 为存储容量，为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为 0；运算后，元素个数为 m5，找最小值的最坏情况下的比较次数为 m-5-1=m-6。14.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA 解析：解析：该二叉树的前序
20、序列为 ABcDEFG，中序序列为 DCBAEFG，可知 A为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下：15.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 C.在链表中，如果每个结点有两个指针域，则该链表
21、一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构解析：解析：选项 A叙述是错误的，例如在双向链表中，每伞结点有两伞指针域，钽该链表是线性结构；选项 C叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项 D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项 B正确。16.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的 C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上三项都错误解析
22、：解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈项，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项 C的说法正确，选项 B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A这一说法是正确的。17.设数据元素的集合 D=1，2,3,4，5)，则满足下列关系 R的数据结构中为线性结构的是（分数：2.00）A.R=(1，2)，(3,4)，(5，1)B.R=(1，3)，(4，1)，(3,2)，(5,4) C.R=(1，2)，(2,3)，(4,5)D.R=(1，3)，(2,4)，(
23、3,5)解析：解析：把每个答案中的第一个元素集合取出来，例如 A：(1，2)，先写下来就是 12，然后看后面的(3,4)，在(1，2)中找不到前驱和后继，只能和(1，2)暂时先并列，然后是(5，1)，这里我们已经写过 12了，那么 5在 1前面就是 512，但是 34要单排，所以 A就是两个根节点 3和 5，两个顺序是 512,34。同理选项 B是 541，32；选项 C是：123 和 45：选项 D是 135，24 所以选项 B正确。18.下列叙述中正确的是（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 B.线性表的链式存储结构中，每个结点必须有指
24、向前件和指向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空解析：解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B、C、D 说法错误。选项 A中，例如双向链表就具有两个指针，也属于线性结构，所以选项 A正确。19.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDC D.CDE解析：解析：栈
25、是根据先进后出的原则组织数据，所以退栈三次的元素依次为 E、D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、C，所以选项 C正确。20.某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度(根结点在第 1层)为（分数：2.00）A.5B.4 C.3D.2解析：解析：该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上：并且结点 B、C、D 在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、
26、G 顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B正确。21.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间解析：解析：算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A和选项 C不正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项 B正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间
27、复杂度最低，所以选项 D错误。22.下列各序列中不是堆的是（分数：2.00）A.(9l，85,53,36,47,30,24，12)B.(91，85,53,47,36,30,24，12)C.(47,91，53,85,30，12,24,36) D.(91，85,53,47,30，12,24,36)解析：解析：堆可以看成一棵完全二叉树：任一根节点=左右孩子(或者=)， (大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91是最大的根，而选项 c是“左根右“的排序，那么 9l的左边只有
28、47，其他都在右边，而右边无法按照此顺序排列，所以选项 C不是堆。23.深度为 5的完全二叉树的结点数不可能是（分数：2.00）A.15 B.16C.17D.18解析：解析：对于满二叉树，叶子结点的数目等于 2 (n-1) ，n 为深度，这里就是 2的 5-1=4次方，就是16。所以选项 A为正确答案。24.有二叉树如下图所示： （分数：2.00）A.ABDEGCFH B.DBGEAFHCC.DGEBHFCAD.ABCDEFGH解析：解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项 A正确，选项 B为中序遍
29、历，选项 C为后序遍历，选项 D不正确。25.下列叙述中正确的是（分数：2.00）A.循环队列是顺序存储结构 B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象解析：解析：循环队列属于队列的特例和栈同属于线性结构，所以选项 c不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾 rear的值和队头 front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队
30、列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A正确，选项 B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项 D不正确。26.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构 解析：解析：只有一个空节点的结构也属数据结构，所以选项 A和选项 B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属
31、于非线性结构，故选项 C不正确，选项 D正确。27.下列关于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境 解析：解析：算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项 D错误。28.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHC C.DGEBHFCAD.ABCDEFGH解析：解析：中序遍历(LDR)是指首先遍历左子树，然后访问根结点，最后遍历右子树，选项 B正确。29.线性表
32、的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高 C.便于查找D.排序时减少元素的比较次数解析：解析：顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大(=1)，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小(1)，存储空间利用率低，故选项 B正确。30.深度为 7的完全二叉树中共有 125个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63 C.64D.65解析：解析：对于满二叉树，结点的数目等于 2 n-1 ，叶子结点数目为 2 n-1 ，n 为深度，这里就是 2的7次方-1，就是 127个结点，叶子结点是 64个。然而题目中只有 125个结点，说明少了两个结点，那么就少了一个叶子结点，即 63个。
