1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 4及答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.下列叙述中正确的是（分数：2.00）A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链接存储方式存储在不连续的存储空间内D.任何存储方式的有序表均能采用二分法进行查找2.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH3.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B
2、.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构4.设某二叉树中共有 140个结点，其中有 40个度为 1的结点。则（分数：2.00）A.该二叉树中有 51个叶子结点B.该二叉树中有 50个叶子结点C.该二叉树中有 51个度为 2的结点D.不可能有这样的二叉树5.带链的栈与顺序存储的栈相比，其优点是（分数：2.00）A.A栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出D.所占存储空间相同6.某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为（分数：2.00）A.BADCB.D
3、CBAC.CDABD.ABCD7.下列叙述中正确的是（分数：2.00）A.算法的时间复杂度与运行算法时特定的输入有关B.算法的时间复杂度与计算机的运行速度有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关8.下列各排序法中，最坏情况下的时间复杂度最低的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序9.设栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为（分数：2.00）A.1B.0C.50D.4910.某二叉树共有 399个结点，其中有 199个度为
4、2的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200C.198D.19911.下列叙述中错误的是（分数：2.00）A.对于各种特定的输入，算法的时间复杂度是固定不变的B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关12.在长度为 n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（分数：2.00）A.(n+1)2B.nC.3n4D.n413.设非空二叉树的所有子树中，其左子树上的结点值均小于根
5、结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A.中序序列B.前序序列C.后序序列D.前序序列或后序序列14.循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50且产生上溢错误B.51C.26D.215.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻找最大项B.在顺序存储的线性表中进
6、行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找16.在具有 2n个结点的完全二叉树中，叶子结点个数为（分数：2.00）A.nB.n+1C.n-1D.n/217.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度18.循环队列的存储空间为 Q(1：40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一
7、个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0且产生下溢错误B.14C.40D.1519.某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABCB.CBEDAC.CBADED.EDCBA20.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数21.设栈的存储空间为 S(1：60)，初始状态为 top=61。
8、现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（分数：2.00）A.60B.59C.0D.122.设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n一 1)2 的是（分数：2.00）A.堆排序B.快速排序C.简单插入排序D.冒泡排序23.在长度为 n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（分数：2.00）A.(3+n)/4B.nC.n/2D.n/424.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子
9、结点数为（分数：2.00）A.10B.11C.12D.不可能有这样的树25.设栈的存储空间为 s(1：50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为（分数：2.00）A.不可能B.50C.0D.126.设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)2 的是（分数：2.00）A.快速排序B.堆排序C.顺序查找D.寻找最大项27.设表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.二分查找法B.堆排序C.快速排序D.顺序查找法28.下列叙述中错误的是（分数：2.00）A.循环链表是循环队列的
10、存储结构B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构29.设一棵树的度为 4，其中度为 4，3，2，1 的结点个数分别为 2，3，3，0。则该棵树中的叶子结点数为（分数：2.00）A.16B.15C.17D.不可能有这样的树30.循环队列的存储空间为 Q(1：100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0或 100B.1C.2D.99国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 4答案解析(总分：60.00，做题时间：90 分钟)一、选
11、择题(总题数：30，分数：60.00)1.下列叙述中正确的是（分数：2.00）A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链接存储方式存储在不连续的存储空间内 D.任何存储方式的有序表均能采用二分法进行查找解析：解析：有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项 C正确。2.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCA D.ABC
12、DEFGH解析：解析：后序遍历(LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项 C正确。3.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C.二叉树只能采用链式存储结构D.循环链表是非线性结构解析：解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项 A不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故选项 C不正确；循环链表是在单链表中，将终端结点的指针域 NULL改为指向表头结点
13、或开始结点的线性结构，故选项 D不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项 B正确。4.设某二叉树中共有 140个结点，其中有 40个度为 1的结点。则（分数：2.00）A.该二叉树中有 51个叶子结点B.该二叉树中有 50个叶子结点C.该二叉树中有 51个度为 2的结点D.不可能有这样的二叉树 解析：解析：140 个结点除去 40个度为 1的结点，说明有 100个度为 2的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选 D。5.带链的栈与顺序存储的栈相比，其优点是（分数：2.00）A.A栈与退栈操作方
14、便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出 D.所占存储空间相同解析：解析：带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故选项 C正确。6.某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为（分数：2.00）A.BADCB.DCBA C.CDABD.ABCD解析：解析：在二叉树前序遍历中 ABCD中 A是根节点，而在后序遍历中根结点位于最后，所以选项 B正确。7.下列叙述中正确的是（分数：2.00）A.算法的时间复杂度与运行算法时特定的输入有关 B.算法的时间复杂度与计算机的运行速度有关C.算法的时间复杂度与算法程
15、序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项 A正确。8.下列各排序法中，最坏情况下的时间复杂度最低的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：堆排序法，最坏情况需要 O(nlog2n)次比较。相比以上几种“除希尔排序法外”，堆排序法的时间复杂度最小，故选项 A正确。9.设栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个
16、数为（分数：2.00）A.1 B.0C.50D.49解析：解析：栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中有 5150=1 个元素，因此选项 A正确。10.某二叉树共有 399个结点，其中有 199个度为 2的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200 C.198D.199解析：解析：在二叉树中，设叶子结点个数为 n0，度为 2的结点个数为 n2，叶子结点的个数计算方法 n 0 =n 2 +1=199+1=200，所以选项 B正确。11.下列叙述中错误的是（分数：2.00）A.对于各
17、种特定的输入，算法的时间复杂度是固定不变的 B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关解析：解析：一般情况下，算法的基本操作重复执行的次数，是模块 n的某一个函数 f(n)。因此，算法的时间复杂度记做 T(n)=O(f(n)。随着模块 n的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项 A正确。12.在长度为 n的顺序表中查找一个元素，假设需要查找
18、的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（分数：2.00）A.(n+1)2 B.nC.3n4D.n4解析：解析：在一个长度为 n的线性表中顺序查找值为 x的元素时，在等概率情况下查找成功时平均查找长度为(n+1)2，所以选项 A正确。13.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A.中序序列 B.前序序列C.后序序列D.前序序列或后序序列解析：解析：中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树
19、。而左子树结点值根节点节点值右子树节点值，是有序序列，因此选项 A正确。14.循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50且产生上溢错误 B.51C.26D.2解析：解析：循环队列初始状态 front=rear=50，经过一系列入队和出队操作后，结束状态还是front=rear=25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 50，即要么队空(0 个元素)，要
20、么队满(50 个元素)。这时进行入队操作，如果是队空(0 个元素)的情况，此时元素个数为 1；如果是队满(50 个元素)的情况，就会产生上溢错误。15.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻找最大项 B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找解析：解析：最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长
21、。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。在顺序存储的线性表中寻找最大项，其平均情况与最坏情况下的时间复杂度都是 n2。16.在具有 2n个结点的完全二叉树中，叶子结点个数为（分数：2.00）A.n B.n+1C.n-1D.n/2解析：解析：在具有 2n个结点的完全二叉树中，叶子结点个数为：(2n+1)2 取整，其值等于 n。所以选项 A正确。17.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指
22、针的动态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析：栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项 A正确。18.循环队列的存储空间为 Q(1：40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=re
23、ar=15，此后又退出一个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0且产生下溢错误 B.14C.40D.15解析：解析：循环队列初始状态 front=rear=40，经过一系列入队和出队操作后，结束状态还是front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 40，即要么队列为空(0 个元素)，要么队列为满队列(40 个元素)。这时进行出队操作，如果是队列满(40 个元素)的情况，此时队列中的元素个数为 39，如果是队列空(0 个元素)的情况，此时就会产生下溢错误。因此选项 A正确。19.某二
24、叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABC B.CBEDAC.CBADED.EDCBA解析：解析：后序遍历次序是“左右根”，中序遍历次序是“左根右”。 由定义可知：后序遍历中最后一个就是树根结点，即 E结点：在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD是根结点 E的左子树集合。问题就会转化为：求后序遍历是 CBAD，中序遍历是 CBAD的子树，方法同上。因为中序遍历中，D 结点右边没有结点了，所以 D结点不包含右子树，否则就会被分为 2个子问题以下是这道题的详细推理过程：步骤 1：由 CBADE得出根结点
25、为 E，由中序遍历可知CBADE，右子树为空；步骤 2：由 CBAD得出左子树集合的根节点为 D，由中序可知CBAD，右子树为空；步骤 3：同理，二叉树更新后如下图所示。20.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数解析：解析：循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可
26、能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：21.设栈的存储空间为 S(1：60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（分数：2.00）A.60 B.59C.0D.1解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。当压入第一个元素时，TOP 指针指向 60+1一 1=60；当压入第二个元素时，TOP 指针指向 60+1一 2=59；，以此类推，当压入第 N个元素时，TOP 指针指向 60+1-N=1，则 N=60。所以选项 A正确。22.设顺序表的长度为 n。下列排序方法中，最坏
27、情况下比较次数小于 n(n一 1)2 的是（分数：2.00）A.堆排序 B.快速排序C.简单插入排序D.冒泡排序解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n2 遍的从前往后扫描和：n2 遍的从后往前扫描，需要比较次数为 n(n1)2。快速排序法的最坏情况比较次数也是 n(n-1)2。简单插入排序，无论是否最坏都需要。n(n-1)2 比较。堆排序，无论是否最坏都需要比较 O(nlog 2 n)次。所以选项 A正确。23.在长度为 n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需
28、要比较的次数大约为（分数：2.00）A.(3+n)/4 B.nC.n/2D.n/4解析：解析：在长度为 n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n 次找到。那么平均长度为：(1+2+n)n=(n(n+1)2)n=(n+1)2 本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为(1+n)2+1)2=(3+n)4。所以选项 A正确。24.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10 B.11C.12D.不可能有这样的树解析：解析：因为任一棵树中，结点
29、总数=总分支数目+1，所以：n 0 +4+1+3=(n 0 *0+3*4+2*1+1*3)+1，计算结果 n 0 =10。其中，n 0 表示叶子结点。所以选项 A正确。25.设栈的存储空间为 s(1：50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为（分数：2.00）A.不可能 B.50C.0D.1解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素，top 值减 1，即 0-1=一 1，发生下溢错误，所以选项 A正确。26.设顺序表的长度为 n。
30、下列算法中，最坏情况下比较次数等于 n(n-1)2 的是（分数：2.00）A.快速排序 B.堆排序C.顺序查找D.寻找最大项解析：解析：假设线性表的长度为 n，则在最坏情况下，快速排序法的最坏情况比较次数也是 n(n-1)2；堆排序，无论是否最坏都是比较 O(nlog 2 n)次，所以选项 A正确。27.设表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.二分查找法 B.堆排序C.快速排序D.顺序查找法解析：解析：二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在
31、线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log 2 n次。所以选项 A正确。28.下列叙述中错误的是（分数：2.00）A.循环链表是循环队列的存储结构 B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构解析：解析：循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项 A正确。29.设一棵树的度为 4，其中度为 4，3，2，1 的结点个数分别为 2，3，3，0。则该棵树中的叶子结点
32、数为（分数：2.00）A.16 B.15C.17D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：n 0 +2+3+3+0=(n 0 *0+4*2+3*3+2*3+1*0)+1。计算得出 n 0 =16。其中，n 0 表示叶子结点，所以选项 A正确。30.循环队列的存储空间为 Q(1：100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0或 100 B.1C.2D.99解析：解析：循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指针 front向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 100)，因此选项 A正确。
