loading2015年9月全国计算机等级考试
二级《C语言》真题
(总分100, 考试时间120分钟)
一、选择题(每小题1分。共40分) 1. 下列叙述中正确的是（ ）。
A 解决同一个问题的不同算法的时间复杂度一般是不同的 B 解决同一个问题的不同算法的时间复杂度必定是相同的
C 对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同 D 对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同
答案:A
[解析]算法的时间复杂度是指执行算法所需要的计算工作量，而计算下作量是用算法所执行的基本运算次数来度量的。解决同一个问题的不同算法的时间复杂度，可能相同也可能不相同。算法的时间复杂度与数据存储结构无关，对同一批数据做同一种处理或者不同处理，数据存储结构相同或者不同，算法的时间复杂度都可能相同或者不同。故选A选项。
2. 下列处理中与队列有关的是（ ）。 A 操作系统中的作业调度 B 执行程序中的过程调用 C 执行程序中的循环控制 D 二叉树的遍历
答案:A
[解析]队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配资源再将新创建的进程插入就绪队列的过程。执行程序中的过程调用一般指函数调用，需要调用的时候转入被调用函数地址执行程序，与队列无关。执行程序中的循环控制是指算法的基本控制结构，包括对循环条件的判定与执行循环体，与队列无关。二叉树是一个有限的节点集合，二叉树的遍历是指不重复地访问二叉树中的所有节点，与队列无关。故本题选择A选项。
3. 设栈的存储空间为S(1：m)，初始状态为top＝m+1。经过一系列入栈与退栈操作后，top＝1。现又要将一个元素进栈，栈顶指针top值变为（ ）。
A 发生栈满的错误 B 2 C m D 0
答案:A
[解析]栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素并将其赋予指定变量。题目中初始状态为top＝m+1，可知入栈栈顶指针top＝top-1，出栈栈顶指针top＝top+1，由于栈长为m，当top＝1时栈满，不能再进行人栈操作。故选A选项。
4. 设二叉树共有150个节点，其中度为1的节点有10个，则该二叉树中的叶子节点数为（ ）。 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种：前序遍历(访问根节点在访问左子树和访问右子树之前)、中序遍历(访问根节点在访问左子树和访问右子树两者之间)、后序遍历(访问根节点在访问左子树和访问右子树之后)。由节点值互不相同而后序序列与中序序列相同，可知该二叉树所有的节点都没有右子树，所以31个节点的二叉树深度为31。故选A选项。
7. 在最坏情况下，堆排序的时间复杂度是（ ）。 A O(lgo2n) B 0(nlog2n) C O(n2) D O(n1．5)
答案:B
[解析]若有n个元素的序列，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆，大根堆是指所有节点的值大于或等于左右子节点的值；小根堆是指所有节点的值小于或等于左右子节点的值。在调整建堆的过程中，总是将根节点值与左、右子树的根节点进行比较，若不满足堆的条件，则将左、右子树根节点值中的大者与根节点值进行交换。堆排序最坏情况下需要O(nlog2n)次比较，所以时间复杂度是0(nlog2n)，B选项正确。
8. 软件按功能可以分为应用软件、系统软件和支撑软件(或工具软件)。下面属于系统软件的是（ ）。
A 学籍管理系统 B ERP系统 C C编译程序
D CAI软件
答案:C
[解析]计算机软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。系统软件是管理计算机的资源，提高计算机的使用效率，为用户提供各种服务的软件。应用软件是为了应用于特定的领域而开发的软件。支撑软件介于系统软件和应用软件之间，协助用户开发软件的工具型软件，其中包括帮助程序人员开发和维护软件产品的工具软件，也包括帮助管理人员控制开发进程和项目管理的工具软件，如Dephi、PowerBuilder等。选项C属于系统软件，A、B、D选项属于应用软件，故选C选项。
9. 存储在计算机内有结构的数据集合是（ ）。 A 数据库
B 数据库系统 C 数据库管理系统 D 数据结构
答案:A
[解析]数据库是指长期存储在计算机内的、有组织的、可共享的数据集合。数据库系统是由数据库及其管理软件组成的系统，是应用软件。数据库管理系统是数据库系统的核心，它位于用户与操作系统之间，属于系统软件。数据结构是计算机存储、组织数据的方式。故本题选A选项。
10. 在数据库技术中，为提高数据库的逻辑独立性和物理独立性，数据库的结构被划分成用户级、存储级和（ ）。
A 概念级 B 外部级 C 管理员级 D 内部纽
答案:A
[解析]数据库系统在其内部分为三级模式，即概念模式、内模式和外模式。概念模式是数据库系统中全局数据逻辑结构的描述，全体用户的公共数据视图。外模式也称于模式或者用户模式，是用户的数据视图，也就是用户所能够看见和使用的局部数据的逻辑结构和特征的描述，是与某一应用有关的数据的逻辑表示。内模式又称物理模式，是数据物理结构和存储方式的描述，是数据在数据库内部的存储方式。所以数据库的结构被划分成用户级、存储级和概念级。故选A选项。
11. 以下叙述错误的是（ ）。
A 一个算法所包含的操作步骤应该是有限的
B 任何能通过编译和运行的算法都一定能得到所期望的结果 C 算法中每一条指令必须有确切的含义 D 算法可以用各种描述方法来进行描述
答案:B
[解析]算法的特点：零个或多个输入，至少一个输出，可行性(能编程实现)，有穷性(有限步出结果)，确定性(描述不能有歧义)。可知A，C，D选项正确。C语言中，通过编译，可以运行的程序，不一定符合题目的本意，因此即使可以运行得到结果，也不一定和预期的结果一样，否则就不需要调试和修改程序了，故B选项错误。答案为B选项。
12. 以下是正确C语言实型常量的是（ ）。 A ．e-1 B e-1 C -1e D 1e-1