国家二级C语言（数据结构与运算）机试模拟试卷3
选择题
1.下列排序方法中，最坏情况下时间复杂度最小的是(C)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 直接插入排序
解析：
2.为了对有序表进行对分查找，则要求有序表(A)
A. 只能顺序存储\\t
B. 只能链式存储
C. 可以顺序存储也可以链式存储
D. 任何存储方式
解析：有序表的对分查找条件是有序表为顺序存储。
顺序查找：①如果线性表为无序表（即表中元素的排序是无序的），则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。分块查找（又称索引顺序查找）：分块有序表结构分为两部分，①线性表本身采用顺序存储结构；②在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。
3.设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为(C)
A. BCA
B. CBA
C. ABC
D. CAB
解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下：
4.下列叙述中正确的是(D)
A. 存储空间不连续的所有链表一定是非线性结构
B. 结点中有多个指针域的所有链表一定是非线性结构
C. 能顺序存储的数据结构一定是线性结构
D. 带链的栈与队列是线性结构
解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。
5.算法时间复杂度的度量方法是(B)
A. 算法程序的长度
B. 执行算法所需要的基本运算次数
C. 执行算法所需要的所有运算次数
D. 执行算法所需要的时间
解析：算法的时间复杂度：分析算法时，语句总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)。算法的时间复杂度也就是算法的时间量度，记作T(n)=O(f(n))。它表示问题输入规模n的增大，算法执行时间的增长率和f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复杂度。f(n)是问题规模n的某个函数。选项B正确。
6.设循环队列为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为(D)
A. 1
B. 2
C. m-1
D. 0或m
解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满、还是队列空。当front=rear=１，要么队列为空，队列中的元素个数为0，要么队列为满，队列中元素个数为m。选项D正确。
7.在最坏情况下(C)
A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小
B. 快速排序的时间复杂度比希尔排序的时间复杂度要小
C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的
解析：按平均时间将排序分为四类：①平方阶(O(n2))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(nlog2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。
8.在深度为7的满二叉树中，度为2的结点个数为(B)
A. 64
B. 63
C. 32
D. 31
解析：因为在任意的二叉树中，度为0的结点（即叶子结点）总比度为2的结点的个数多1个，而度为0的结点数n0=2m-1（其中m为二叉树的深度）。本题的度为0的结点个数n0=27-1=26=64。因此，度为2的结点数n2=n0-1=63。所以选项B正确。
9.设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为(C)
A. 30
B. 20
C. m-19
D. m-20
解析：根据题意，栈空间如下图所示。
10.算法空间复杂度的度量方法是(D)
A. 算法程序的长度
B. 算法所处理的数据量
C. 执行算法所需要的工作单元
D. 执行算法所需要的存储空间
解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。
11.设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为(A)
A. 4
B. 6
C. m-5
D. m-6
解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n-1次，就是4次。因此选项A正确。
12.下列叙述中正确的是(D)
A. 循环队列属于队列的链式存储结构
B. 双向链表是二叉树的链式存储结构
C. 非线性结构只能采用链式存储结构
D. 有的非线性结构也可以采用顺序存储结构
解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺
本文档预览：3600字符，共7933字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
