国家二级C语言机试（选择题）-试卷1
(总分：80.00，做题时间：90分钟)
一、 选择题(总题数：40，分数：80.00)
1.对长度为n的线性表作快速排序，在最坏情况下，比较次数为（ ）。
（分数：2.00）
 A.n
 B.n-1
 C.n(n-1)
 D.n(n-1)/2 √
解析：解析：在最坏情况下，快速排序需要比较n(n-1)/2次。
2.下列叙述中正确的是（ ）。
（分数：2.00）
 A.有且只有一个根结点的数据结构一定是线性结构
 B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
 C.有且只有一个根结点的数据结构一定是非线性结构
 D.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构 √
解析：解析：有且只有一个根结点的数据结构可以是线性结构，如队列，也可以是非线性结构，如二叉树，所以选项D）正确。选项B）中，如果有两个根结点，则不符合线性结构的条件，说法错误。本题答案选D）。
3.下列叙述中错误的是（ ）。
（分数：2.00）
 A.在双向链表中，可以从任何一个结点开始直接遍历到所有结点
 B.在循环链表中，可以从任何一个结点开始直接遍历到所有结点
 C.在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 √
 D.在二叉链表中，可以从根结点开始遍历到所有结点
解析：解析：在线性单链表中，每一个结点只有一个指针域，由这个指针只能到后件结点，但不能到前件结点，选项C）说法错误。
4.某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（ ）。
（分数：2.00）
 A.5 √
 B.4
 C.3
 D.2
解析：解析：根据题意，该二叉树中叶子结点数和度为2的结点数的和为9。根据二叉树的基
本性质，叶子结点比度为2的结点多1个，则度为2的结点个数为4，叶子结点的个数为5，所以答案选A。
5.设栈的顺序存储空间为S(1: 50),初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。
（分数：2.00）
 A.30
 B.29
 C.20 √
 D.19
解析：解析：在栈中，top位置直接反映栈中元素的个数，top=20，则说明当前栈中的元素个数为20。
6.下列叙述中正确的是（ ）。
（分数：2.00）
 A.栈与队列都只能顺序存储
 B.循环队列是队列的顺序存储结构 √
 C.循环链表是循环队列的链式存储结构
 D.以上说法都不对
解析：解析：栈和队列都可以采用链式存储结构，选项A）错误。队列的顺序存储结构一般采用循环队列的形式，所以循环队列是队列的顺序存储结构，选项B正确，选项C）错误。答案选B）。
7.设某二叉树的前序序列为ABC，中序序列为CBA，则该二叉树的后序序列为（ ）。
（分数：2.00）
 A.BCA
 B.CBA √
 C.ABC
 D.CAB
解析：解析：前序序列为ABC，中序序列为CBA，说明根结点为A，且B和C均在该A的左子树上；结点B和C的前序序列为BC，中序序列为CB，则说明结点C在结点B的左子树上，根据以上分析，该二叉树的后序序列为CBA，答案选B）。
8.下列排序方法中，最坏情况下时间复杂度最小的是（ ）。
（分数：2.00）
 A.冒泡排序
 B.快速排序
 C.堆排序 √
 D.直接插入排序
解析：解析：在最坏情况下，堆排序时间复杂度为O(nlog 2 n)，其余选项均为O(n 2 )，所以答案选C。
9.为了对有序表进行对分查，则要求有序表（ ）。
（分数：2.00）
 A.只能顺序存储 √
 B.只能链式存储
 C.可以顺序存储也可以链式存储
 D.任何存储方式
解析：解析：对分查必须满足用顺序存储结构，且线性表是有序表两个条件，答案选A。
10.设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为（ ）。
（分数：2.00）
 A.BCA
 B.CBA
 C.ABC √
 D.CAB
解析：解析：后序序列为CBA，中序序列为ABC，则说明，A为根结点，并且B和C均在A的右子树上；结点B和C中，后序序列为CB，中序序列为BC，则说明结点C在结点B的右子树上，根据分析可得，该二叉树的前序序列为ABC，答案选C。
11.下列叙述中正确的是（ ）。
（分数：2.00）
 A.存储空间不连续的所有链表一定是非线性结构
 B.结点中有多个指针域的所有链表一定是非线性结构
 C.能顺序存储的数据结构一定是线性结构
 D.带链的栈与队列是线性结构 √
解析：解析：判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A）、B）和C）都不能判定是否是线性结构，选项D）正确，答案选D）。
12.算法时间复杂度的度量方法是（ ）。
（分数：2.00）
 A.算法程序的长度
 B.执行算法所需要的基本运算次数 √
 C.执行算法所需要的所有运算次数
 D.执行算法所需要的时间
解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，答案选B。
13.设循环队列为Q(1: m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，fr
ont=rear=1，则该循环队列中的元素个数为（ ）。
（分数：2.00）
 A.1
 B.2
 C.m-1
 D.0或m √
解析：解析：在循环队列中，当front=rear时，有两种情况，一种是队列为空，另一种是队列为满，所以答案选D。
14.在最坏情况下（ ）。
（分数：2.00）
 A.快速排序的时间复杂度比冒泡排序的时间复杂度要小
 B.快速排序的时间复杂度比希尔排序的时间复杂度要小
 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小 √
 D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的
解析：解析：在最坏情况下，快速排序、冒泡排序和直接插入排序所需要的比较次数为O(n 2 )，希尔排序所需要的比较次数为O(n 1.5 )，所以答案选C。
15.在深度为7的满二叉树中，度为2的结点个数为（ ）。
（分数：2.00）
 A.64
 B.63 √
 C.32
 D.31
解析：解析：根据满二叉树的性质，深度为7的满二叉树共有2 2 -1=127个结点。根据二叉树
的性质，该满二叉树在第7层上，共有2 7-1 =64个结点，即共有64个叶子结点，那么度为2的结点个数为127-64=63个。
16.设栈的顺序存储空间为S(1: m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。
（分数：2.00）
 A.30
 B.20
 C.m-19 √
 D.m-20
解析：解析：初始状态为top=m+1，经过运算之后，top=20，则当前栈中元素个数为m+1-20=m-19个。
17.算法空间复杂度的度量方法是（ ）。
（分数：2.00）
 A.算法程序的长度
 B.算法所处理的数据量
 C.执行算法所需要的工作单元
 D.执行算法所需要的存储空间 √
解析：解析：算法的空间复杂度，一般是指执行这个算法所需要的内存空间，答案选D。
18.下面不属于软件开发阶段任务的是（ ）。
（分数：2.00）
 A.测试
 B.可行性研究 √
 C.设计
 D.实现
解析：解析：可行性研究是属于软件定义阶段的任务，所以答案选B。
19.设循环队列为Q(1: m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻最大值的元素，最坏情况下需要比较的次数为（ ）。
（分数：2.00）
 A.4 √
 B.6
 C.m-5
 D.m-6
解析：解析：初始状态为front=rear=m，说明初始状态为空。经过一系列入队与退队运算后，front=15，rear=20，则当前共有5个元素，则在最坏情况下，需要比较的次数为4次，答
案选A。
20.下列叙述中正确的是（ ）。
（分数：2.00）
 A.循环队列属于队列的链式存储结构
 B.双向链表是二叉树的链式存储结构
 C.非线性结构只能采用链式存储结构
 D.有的非线性结构也可以采用顺序存储结构 √
解析：解析：循环队列属于队列的顺序存储结构，选项A）错误；二叉树的存储结构为二叉链表，选项B）错误；非线性结构也可以采用顺序存储结构，因此选项C）错误，选项D）正确，答案为D）。
21.某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为（ ）。
（分数：2.00）
 A.n+1
 B.n-1 √
 C.2n
 D.n/2
解析：解析：根据二叉树的性质，叶子结点的个数比度为2的结点数多一个，因此答案为B)。
22.下列叙述中错误的是（ ）。
（分数：2.00）
 A.算法的时间复杂度与算法所处理数据的存储结构有直接关系
 B.算法的空间复杂度与算法所处理数据的存储结构有直接关系
 C.算法的时间复杂度与空间复杂度有直接关系 √
 D.以上说法都不对
解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选C。
23.设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为（ ）。
（分数：2.00）
 A.30
 B.29
 C.20 √
 D.19
解析：解析：栈底指针bottom=49，栈顶指针top=30，则栈中的元素个数为49-30+1=20个，
答案选C。
二叉树的基本性质
24.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度（根结点在第1层）为（ ）。
（分数：2.00）
 A.2
 B.3
 C.4 √
 D.5
解析：解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树深度为4，答案选C。

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