全国计算机等级考试二级C语言真题题库4 2014年3月
(总分43, 做题时间120分钟)
—、选择题(每小题1分，共40分)
1. 在最坏情况下（ ）。
A 快速排序的时间复杂度比冒泡排序的时间复杂度要小 B 快速排序的时间复杂度比希尔排序的时间复杂度要小 C 希尔排序的时间复杂度比直接插入排序的时间复杂度要小 D 快速排序的时间复杂度与希尔排序的时间复杂度是一样的 答案:C
[解析]对长度为n的线性表排序常用排序方法时间复杂度如下表所示。
2. 在深度为7的满二叉树中，度为2的节点个数为（ ）。
A 64 B 63 C 32 D 31
答案:B
[解析]在树结构中，一个节点所拥有的后件个数称为该节点的度。深度，定义一棵树的根节点所在的层次为1，其他节点所在的层次等于它的父节点所在的层次加1，树的最大层次称为树的深度。满二叉树指除最后一层外，每一层上的所有节点都有两个子节点的二叉树。一棵深度为K的满二叉树，整棵二叉树共有2K-1个节点；满二叉树在其第i层上有2i-1个节点。在满二叉树中，只有度为2和度为0的节点。深度为7的满二叉树，节点个数为27-1＝127，第七层叶节点个数为27-1＝64，则127—64＝63，B选项正确。
3. 设栈的顺序存储空间为S(1：m)，初始状态为top＝m+1。现经过一系列入栈与退栈运算后，top＝20，则当前栈中的元素个数为（ ）。
A 30 B 20 C m-19 D m-20 答案:C
[解析]栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素赋予指定变量。栈为空时，栈顶指针top＝0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top＝m+1，当top＝＝20时，元素依次存储在单元20：m中，个数为m-19，故C选项正确。
4. 算法空间复杂度的度量方法是（ ）。
A 算法程序的长度 B 算法所处理的数据量 C 执行算法所需要的工作单元 D 执行算法所需要的存储空间 答案:D
[解析]算法的空间复杂度是指执行这个算法所需要的内存空间。算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。故D选项正确。
5. 下面不属于软件开发阶段任务的是（ ）。
A 测试 B 可行性研究 C 设计 D 实现 答案:B
[解析]软件生命周期分为3个时期共8个阶段：软件定义期，包括问题定义、可行性研究、需求分析；软件开发期，包括概要设计、详细设计、实现、测试；运行维护期，即运行维护阶段。可行件研究属于软件定义期任务，B选项错误。
6. 下面属于字符类的实例是（ ）。
A ?518? B ”5” C ?nm D ?＼n? 答案:D
[解析]字符实例的一般形式是用—对单引号括起来的一个字符。另外ASCII码中还有—些控制字符，C语言中用转义字符的形式来书写，转义字符以反斜杯(＼)开始，后面跟1个字符或字符序列。?518?单引号中省3个字符，A选项错误。“5”双引号为字符串，B选项错误。?nm?单引号中有两个字符，C选项错误。?＼n?为换行符，属于字符类实例，D选项正确。
7. 某系统结构图如下图所示。
该系统结构
图的最大扇出数是（ ）。
A n B 1 C 3 D 4 答案:A
[解析]扇出指的是由一个模块直接调用的其他模块数。题干中某系统为一个模块，其扇出数目为n(n＞3)，功能1与功能n模块扇出数均为2，故A选项正确。
8. 一个兴趣班可以招收多名学生，而一个学生可以参加多个兴趣班，则实体兴趣班和实体学生之间的联系是（ ）。
A 1：1联系 B 1：m联系 C m：1联系 D m：n联系 答案:D
[解析]一般来说，实体集之间必须通过联系来建立联接关系，分为3类：一对一联系(1：1)、一对多联系(1：m)、多对多联系(m：n)。一个学生可参加多个兴趣班，一个兴趣班有多个学生组成。多个兴趣班与多个学生的关系为(m：n)多对多联系，故D选项正确。
9. 有3个关系表R、S和T如下，其中3个关系对应的关键字分别为A，B和复合关键字(A，B)。
表T
的记录项(b，q，4)违反了（ ）。
A 实体完整性约束 B 参照完整性约束 C 用户定义的完整性约束 D 关系完整性约束 答案:B
[解析]关系模型中可以有3类完整性约束：实体完整性约束、参照完整性约束和用户定义的完整件约束。实体完整性约束是指，若属性M是关系的主键，则属性M中的属性值不能为空值。T中主键不为空，A选项错误。参照完整性约束是指，若属性(或属性组)A是关系M的外键，它与其系M的主码相对应，则对于关系M中的每个元组在A上的值必须为：要么取空值，要么等于关系M中某个元组的主码值。表1中属性B为关系S的外键，它与关系S的主键相对应，则T中元组在B上应该为空或S中主键值相等，题目中不相等，违反参照完整性约束，B选项正确。此题父系中无语义要求，C选项错误。
10. 在数据库系统中，给出数据模型在计算机上物理结构表示的是（ ）。
A 概念数据模型 B 逻辑数据模型 C 物理数据模型
全国计算机等级考试二级C语言真题题库4+2014年3月
