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