国家二级ACCESS机试选择题（数据结构与算法）模拟试卷10
选择题
1.下列叙述中正确的是(C)
A. 所谓有序表是指在顺序存储空间内连续存放的元素序列
B. 有序表只能顺序存储在连续的存储空间内
C. 有序表可以用链接存储方式存储在不连续的存储空间内
D. 任何存储方式的有序表均能采用二分法进行查找
解析：有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项C正确。
2.设有二叉树如下图所示：
(C)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：后序遍历(LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项C正确。
3.下列叙述中正确的是(B)
A. 结点中具有两个指针域的链表一定是二叉链表
B. 结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C. 二叉树只能采用链式存储结构
D. 循环链表是非线性结构
解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项A不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故选项C不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故选项D不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项B正确。
4.设某二叉树中共有140个结点，其中有40个度为1的结点。则(D)
A. 该二叉树中有51个叶子结点
B. 该二叉树中有50个叶子结点
C. 该二叉树中有51个度为2的结点
D. 不可能有这样的二叉树
解析：140个结点除去40个度为l的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选D。
5.带链的栈与顺序存储的栈相比，其优点是(C)
A. 入栈与退栈操作方便
B. 可以省略栈底指针
C. 入栈操作时不会受栈存储空间的限制而发生溢出
D. 所占存储空间相同
解析：带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故选项c正确。
6.某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为(B)
A. BADC
B. DCBA
C. CDAB
D. ABCD
解析：在二叉树前序遍历中ABCD中A是根节点，而在后序遍历中根结点位于最后，所以选项B正确。
7.下列叙述中正确的是(A)
A. 算法的时间复杂度与运行算法时特定的输入有关
B. 算法的时间复杂度与计算机的运行速度有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项A正确。
8.下列各排序法中，最坏情况下的时间复杂度最低的是(A)
A. 堆排序
B. 快速排序
C. 希尔排序
D. 冒泡排序
解析：堆排序法，最坏情况需要O(nlog2n)次比较。相比以上几种“除希尔排序法外”，堆排序法的时间复杂度最小，故选项A正确。
9.设栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为(A)
A. 1
B. 0
C. 50
D. 49
解析：栈的存储空间为S(1：50)，初始状态为top=51。现经过～系列正常的入栈与退栈操作后，top=50，则栈中有51-50=1个元素，因此选项A正确。
10.某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为(B)
A. 不存在这样的二叉树
B. 200
C. 198
D. 199
解析：在二叉树中，设叶子结点个数为n0，度为2的结点个数为n2，叶子结点的个数计算方法n0=n2+1=199+1=200，所以选项B正确。
11.下列叙述中错误的是(A)
A. 对于各种特定的输入、算法的时间复杂度是固定不变的
B. 算法的时间复杂度与使用的计算机系统无关
C. 算法的时间复杂度与使用的程序设计语言无关
D. 算法的时间复杂度与实现算法过程中的具体细节无关
解析：一般情况下，算法的基本操作重复执行的次数，是模块n的某一个函数f(n)。因此，算法的时间复杂度记做T(n)=O(f(n))。随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项A正确。
12.在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为(A)
A. (n+1)／2
B. n
C. 3n／4
D. n／4
解析：在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下查找成功时平均查找长度为(n+1)／2，所以选项A正确。
13.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是(A)
A. 中序序列
B. 前序序列
C. 后序序列
D. 前序序列或后序序列
解析：中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值<根节点节点值≤右子树节点值，是有序序列，因此选项A正确。
14.循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为(A)
A. 1，或50且产生上溢错误
B. 51
C. 26
D. 2
解析：循环队列初始状态front=rear=50，经过一系列入队和出队操作后，结束状态还是front=rear=25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是0就是50，即要么队空(0个元素)，要么队满(50个元素)。这时进行入队操作，如果是队空(0个元素)的情况，此时元素个数为1；如果是队满(50个元素)的情况，就会产生上溢错误。
15.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是(A)
A. 在顺序存储的线性表中寻找最大项
B. 在顺
本文档预览：3600字符，共8995字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
