国家二级ACCESS机试选择题（数据结构与算法）模拟试卷16 (题后含答案及解析)
题型有：1. 选择题
选择题
1． 下列叙述中正确的是二叉树公式
A．算法的时间复杂度与运行算法时特定的输入有关
B．算法的时间复杂度与计算机的运行速度有关
C．算法的时间复杂度与算法程序中的语句条数成正比
D．算法的时间复杂度与算法程序编制者的水平有关
正确答案：A
解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项A正确。 知识模块：数据结构
与算法
2． 下列各排序法中，最坏情况下的时间复杂度最低的是
A．堆排序
B．快速排序
C．希尔排序
D．冒泡排序
正确答案：A
解析：堆排序法，最坏情况需要O(nlog2n)次比较。相比以上几种“除希尔排序法外”，堆排序法的时间复杂度最小，故选项A正确。 知识模块：数据结构与算法
3． 设栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为
A．1
B．O
C．50
D．49
正确答案：A
解析：栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中有51-50=1个元素，因此选项A正确。 知识模块：数据结构与算法
4． 某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为
A．不存在这样的二叉树
B．200
C．198
D．199
正确答案：B
解析：在二叉树中，设叶子结点个数为n0，度为2的结点个数为n2，叶子结点的个数计算方法n0=n2+1=199+1=200，所以选项B正确。 知识模块：数据结构与算法
5． 下列叙述中错误的是
A．对于各种特定的输入，算法的时间复杂度是固定不变的
B．算法的时间复杂度与使用的计算机系统无关
C．算法的时间复杂度与使用的程序设计语言无关
D．算法的时间复杂度与实现算法过程中的具体细节无关
正确答案：A
解析：一般情况下，算法的基本操作重复执行的次数，是模块n的某一个函数f(n)。因此，算
法的时间复杂度记做T(n)=O(f(n))。随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项A正确。 知识模块：数据结构与算法
6． 在长度为n的顺序表中查一个元素，假设需要查的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为
A．(n+1)／2
B．n
C．3n／4
D．n／4
正确答案：A
解析：在一个长度为n的线性表中顺序查值为x的元素时，在等概率情况下查成功时平均
查长度为(1+1)／2，所以选项A正确。 知识模块：数据结构与算法
7． 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是
A．中序序列
B．前序序列
C．后序序列
D．前序序列或后序序列
正确答案：A
解析：中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值＜根节点节点值≤右子树节点值，是有序序列，因此选项A正确。 知识模块：数据结构与算法
8． 循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为
A．1，或50且产生上溢错误
B．5 1
C．26
D．2
正确答案：A
解析：循环队列初始状态front=rear=50，经过一系列入队和出队操作后，结束状态还是front=rear=25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是0就是50，即要么队空(0个元素)，要么队满(50个元素)。这时进行入队操作，如果是队空(0个元素)的情况，此时元素个数为1；如果是队满(50个元素)的情况，就会产生上溢错误。  知识模块：数据结构与算法
9． 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是
A．在顺序存储的线性表中寻最大项
B．在顺序存储的线性表中进行顺序查
C．在顺序存储的有序表中进行对分查
D．在链式存储的有序表中进行查
正确答案：A
解析：最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。    平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。    在顺序存储的线性表中寻最大项，其平均情况与最坏情况下的时间复杂度都是n／2。 知识模块：数据结构与算法
10． 在只有2n个结点的完全二叉树中，叶子结点个数为
A．n
B．n+1
C．n-1
D．n／2
正确答案：A
解析：在具有2n个结点的完全二叉树中，叶子结点个数为：(2n+1)／2取整，其值等于n。所以选项A正确。 知识模块：数据结构与算法
11． 下列叙述中正确的是
A．在栈中，栈顶指针的动态变化决定栈中元素的个数
B．在循环队列中，队尾指针的动态变化决定队列的长度
C．在循环链表中，头指针和链尾指针的动态变化决定链表的长度
D．在线性链表中，头指针和链尾指针的动态变化决定链表的长度
正确答案：A
解析：栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项A正确。 知识模块：数据结构与算法
12． 循环队列的存储空间为O(1：40)，初始状态为。front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为
A．39，或0且产生下溢错误
B．14
C．40
D．15 
正确答案：A
解析：循环队列初始状态front=rear=40，经过一系列入队和出队操作后，结束状态还是front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是0就是40，即要么队列为空(0个元素)，要么队列为满队列(40个元素)。这时进行．出队操作，如果是队列满(40个元素)的情况，此时队列中的元素个数为39，如果是队列空(0个元素)的情况，此时就会产生下溢错误。因此选项A正确。 知识模块：数据结构与算法
13． 某二又树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为
A．EDABC
B．CBEDA
C．CBADE
D．EDCBA
正确答案：A
解析：后序遍历次序是“左右根”，中序遍历次序是“左根右”。    由定义可知：①后序遍历中最后一个就是树根结点，即E结点：②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD是根结点E的左子树集合。问题就会转化为：求后序遍历是CBAD，中序遍历是CBAD的子树，方法同上。因为中序遍历中，D结点右边没有结点了，所以D结点不包含右子树，否则就会被分为2个子问题      以下是这道题的详细推理过程：步骤1：由CBADE得出根结点为E，由中序遍历可知{CBAD}E，右子树为空；步骤2：由CBAD得出左子树集合的根节点为D，由中序可知{CBA}D，右子树为空；步骤3：同理，二叉树更新后如下图所示。    由上图可得，前序遍历为：EDABC。 知识模块：数据结构与算法
14． 下列叙述中正确的是
A．在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
B．在循环队列中，队尾指针的动态变化决定队列的长度
C．在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度
D．在带链的栈中，栈顶指针的动态变化决定栈中元素的个数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。