国家二级ACCESS机试选择题（数据结构与算法）模拟试卷20
选择题
1.下列各组的排序方法中，最坏情况下比较次数相同的是(A)
A. 冒泡排序与快速排序
B. 简单插入排序与希尔排序
C. 堆排序与希尔排序
D. 快速排序与希尔排序
解析：最坏情况下冒泡排序需要比较n(n-1)／2次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要n(n-1)／2次。直接插入排序，最坏情况需要比较次n(n-1)／2次。堆排序，无论是否最坏都要比较O(nlog2n)次。快速排序，最坏情况退化为冒泡排序，需要比较n(n-1)／2次。在最坏情况下，希尔排序所需要的比较次数为O(n1．5)。
2.下列叙述中正确的是(B)
A. 循环队列是队列的一种链式存储结构
B. 循环队列是队列的一种顺序存储结构
C. 循环队列是非线性结构
D. 循环队列是一种逻辑结构
解析：本题主要考查循环队列的概念，循环队列作为队列的·种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。
3.下列关于线性链表的叙述中，正确的是(C)
A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C. 进行插入与删除时，不需要移动表中的元素
D. 以上都不正确
解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
4.一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为(A)
A. 16
B. 10
C. 6
D. 4
解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故此度为1的结点个数=总结点数-叶子节点数．度为2的节点数=25-5-4=16。
5.设循环队列存储空间为Q(1：50)。初始状态为front=rear=50。经过一系列入队和退队操作后，front=14，rear=19，则该循环队列中的元素个数为(D)
A. 46
B. 45
C. 6
D. 5
解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引15位置开始到索引19位置，共有5元素。
6.下列链表中，其逻辑结构属于非线性结构的是(A)
A. 二叉链表
B. 循环链表
C. 双向链表
D. 带链的栈
解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
7.设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为(D)
A. 15
B. 16
C. 20
D. 0或35
解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为0；第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。
8.下列关于栈的叙述中，正确的是(C)
A. 栈底元素一定是最后入栈的元素
B. 栈顶元素一定是最先入栈的元素
C. 栈操作遵循先进后出的原则
D. 以上三种说法都不对
解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。
9.设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为(D)
A. 71
B. 70
C. 69
D. 不可能有这样的二叉树
解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。即有n0-n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+1+10+n2=2n2+11，所以2n2=139，度为2个结点个数不能确定。
10.下列叙述中正确的是(A)
A. 程序执行的效率与数据的存储结构密切相关
B. 程序执行的效率只取决于程序的控制结构
C. 程序执行的效率只取决于所处理的数据量
D. 以上都不正确
解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。
11.下列与队列结构有关联的是(D)
A. 函数的递归调用
B. 数组元素的引用
C. 多重循环的执行
D. 先到先服务的作业调度
解析：队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。
12.对如下图所示的二叉树
(C)
A. DYBEAFCZX
B. YDEBFZXCA
C. ABDYECFXZ
D. ABCDEFXYZ
解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：①访问根结点：②前序遍历左子树；③前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。
13.一个栈的初始状态为空。现将元素l，2,3，A，B,C依次入栈，然后再依次出栈，则元素出栈的顺序是(C)
A. 1，2，3，A，B，C
B. C，B，A，1，2，3
C. C，B，A，3,2，1
D. 1，2，3，C，B，A
解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。
14.下列叙述中正确的是(D)
A. 一个算法的空间复杂度大，则其时间复杂度也必定大
B. 一个算法的空间复杂度大，则其时间复杂度必定小
C. 一个算法的时间复杂度大，则其空间复杂度必定小
D. 算法的时间复杂度与空间复杂度没有直接关系
解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。
15.下列叙述中正确的是(A)
A. 循环队列中的元素个数随队头指针与队
本文档预览：3600字符，共7258字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
