全国计算机等级考试二级 C语言真题题库1 9月
(总分43,做题时间120分帥
一、选择题侮小题1分。共40分)
1-下列叙述中正确的是()。
A解决同一个问题的不同算法的时间复杂度一般是不同的
B解决同一个问题的不同算法的时间复杂度必定是相同的
C对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定 相同
D对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定 相同
答案:A
［解析］算法的时间复杂度是指执行算法所需要的计算工作量，而计算下作量是用算法所
执行的基本运算次数来度量的。解决同一个问题的不同算法的时间复杂度，可能相同也可能
不相同。算法的时间复杂度与数据存储结构无关，对同一批数据做同一种处理或者不同处理，
数据存储结构相同或者不同，算法的时间复杂度都可能相同或者不同。故选A选项。
2-下列处理中与队列有关的是()。
A操作系统中的作业调度
B执行程序中的过程调用
C执行程序中的循环控制
D二叉树的遍历
答案:A
［解析］队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队
列的元素将最先出队，所以队列具有“先进先出”的特性，体现了 “先来先服务”的原则。作业
调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存，并
为它们创建进程、分配资源再将新创建的进程插入就绪队列的过程。执行程序中的过程调用
—般指函数调用，需要调用的时候转入被调用函数地址执行程序，与队列无关。执行程序中
的循环控制是指算法的基本控制结构，包括对循环条件的判定与执行循环体，与队列无关。
二叉树是一个有限的节点集合，二叉树的遍历是指不重复地访问二叉树中的所有节点，与队
列无关。故本题选择 A选项。
3?设栈的存储空间为8(1 : m),初始状态为top二m+1。经过一系列入栈与退栈
操作后，top二1。现又要将一个元素进栈，栈顶指针top值变为()。
A发生栈满的错误
B2
C m
D 0
答案:A
［解析］栈是一种特殊的线性表， 它所有的插入与删除都限定在表的同一端进行。入栈运
算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素并将其赋予指定变量。题目中
初始状态为top = m+1 ,可知入栈栈顶指针top二top-1 ,出栈栈顶指针top = top+1 ,由于栈 长为m,当top = 1时栈满，不能再进行人栈操作。故选 A选项。
4?设二叉树共有150个节点，其中度为1的节点有2个，则该二叉树中的叶 子节点数为()。
A 71
B 70
C 69
D不可能有这样的二叉树
答案:D
［解析］在树结构中，一个节点所拥有的后件个数称为该节点的度，所有节点中最大的度
称为树的度。对任何一棵二叉树，度为0的节点总是比度为2的节点多一个。如果有一棵
二叉树，节点总数为150,假设度为0的节点个数为n,则有n+10+n-1二150 , n二70 . 5, 由于节点个数必须是整数，所以不可能有题目中这样的二叉树。故选择D选项。
5-非空循环链表所表示的数据结构()。
A有根节点也有叶子节点
B没有根节点但有叶子节点
C有根节点但没有叶子节点
D没有根节点也没有叶子节点
答案:A
［解析］在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点， 最后一个
节点的指针域的值由 NULL改为指向表头节点，这样的链表称为循环链表。循环链表是线 性结构，有且只有一个根节点，每一个节点最多有一个前件，也最多有一个后件。循环链表
表头节点为根节点，链表的最后一个节点为叶子节点，虽然它含有一个指向表头节点的指针，
但是表头节点并不是它的一个后件。故选择A选项。
6.设二叉树中共有31个节点，其中的节点值互不相同。如果该二叉树的后序 序列与中序序列相同，则该二叉树的深度为()。
A 31
B 16
C 17
D 5
答案:A
［解析］二叉树遍历可以分为3种：前序遍历(访问根节点在访问左子树和访问右子树之 前)、中序遍历(访问根节点在访问左子树和访问右子树两者之间)、后序遍历(访问根节点在
访问左子树和访问右子树之后)o由节点值互不相同而后序序列与中序序列相同，可知该二
叉树所有的节点都没有右子树，所以 31个节点的二叉树深度为31 o故选A选项。
7?在最坏情况下，堆排序的时间复杂度是()。
A O(lgo2n)
B 0(nlog2n)
C 0(n2)
D 0(n1? 5)
答案七
［解析］若有n个元素的序列，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条
件时称为堆，大根堆是指所有节点的值大于或等于左右子节点的值；小根堆是指所有节点的
值小于或等于左右子节点的值。在调整建堆的过程中，总是将根节点值与左
