全国计算机等级考试二级C语言真题题库3 2015年9月
(总分：43.00，做题时间：120分钟)
一、选择题(每小题1分，共40分)(总题数：40，分数：40.00)
1.下列叙述中正确的是（ ）。 （分数：1.00）
A.程序可以作为算法的一种表达方式 √ B.算法的有穷性是指算法的规模不能太大 C.算法的复杂度用于衡量算法的控制结构 D.算法的效率与数据的存储结构无关
解析：[解析]算法的有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，故B选项错误。一个算法复杂度的高低体现在运行该算法所需要的计算机资源的多少，故C选项错误。算法的效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，这就与算法本身设计的优劣以及具体的编程实现有关，数据的存储结构会极大的影响程序的执行时间，故D选项错误。算法在实现时需要用具体的程序设计语言来实现，所以程序可以作为实现算法的一种表达方式。故选A选项。
2.某循环队列的存储空间为Q(1：m)，初始状态为front＝rear＝m。现经过一系列的入队操作和退队操作后，front＝m-1，rear＝m，则该循环队列中的元素个数为（ ）。 （分数：1.00） A.m-1 B.1 √ C.m D.0
解析：[解析]循环队列长度为m，由初始状态为front＝rear＝m可知此时循环队列为空。入队运算时，首先队尾指针(rear)进1(即rear+1)，然后在rear指针指向的位置插入新元素。特别的，当队尾指针rear＝m+1时，置rear＝1。迟队运算时，排头指针(front)进1(即front+1)，然后删除front指针指向的位置上的元素，当排头指针front＝m+1时，置front＝1。从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素，则该循环队列中的元素个数为m-(m-1)＝1。故选择B选项。
3.能从任意一个节点开始没有重复地扫描到所有节点的数据结构是（ ）。 （分数：1.00） A.循环链表 √ B.双向链表 C.二叉链表 D.有序链表
解析：[解析]在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，最后一个节点的指针域的值由NULL改为指向表头节点，这样的链表称为循环链表。在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发没有重复地扫描到表中其他所有的节点。双向链表与二叉链表都可以扫描到所有节点，但是会有重复。有序链表如果是单链表的情况下，不能扫描到所有节点。故A选项正确。 4.某棵树中共有25个节点，且只有度为3的节点和叶子节点，其中叶子节点有7个，则该树中度为3的节点数为（ ）。 （分数：1.00）
A.不存在这样的树 √ B.7 C.8 D.6
解析：[解析]树是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。在树结构中，一个节点所拥有的后件个数称为该节点的度，所有节点中最大的度称为树的度。首先假设这样的树是存在
的，由于只有度为3的节点和叶子节点，可知最后一层都为叶子节点，倒数第二层一部分节点的度为3，一部分节点为叶子节点。节点总数为25，叶子节点有7个，则度为3的节点有18个，由于(3-1)／2＜18＜(3-1)／2可知，树共有5层，前三层有度为3的节点(3-1)／2＝13个，第四层有3＝27个节点，其中5个是度为3的节点，22个是叶子节点，此时与题目给出的叶子节点有7个相矛盾，故不存在这样的树。故选择A选项。
5.在最坏情况下，二分查找法的时间复杂度为（ ）。 （分数：1.00） A. B.n
5-1
4-1
4-1
4-1
C.log2 √ D.n
解析：[解析]二分法查找也称拆半查找，能使用二分法查找的线性表必须满足两个条件，用顺序存储结构以及线性表有序。利用二分法查找元素X的过程如下：将X与线