在下列各题的A）、B）、C）、D）四个选项中，只有一个选项是正确的，请将正确的选项涂写在答题卡相应位置上，答在试卷上不得分。

（1）算法的空间复杂度是指

    A)算法程序的长度      B)算法程序中的指令条数     C)算法程序所占的存储空间          D)执行算法需要的内存空间

（2）在结构化程序设计中,模块划分的原则是

    A)各模块应包括尽量多的功能    B)各模块的规模应尽量大    C)各模块之间的联系应尽量紧密

    D)模块内具有高内聚度、模块间具有低耦合度

（3）下列叙述中,不属于测试的特征的是

    A)测试的挑剔性    B)完全测试的不可能性     C)测试的可靠性    D)测试的经济性

（4）下面关于对象概念的描述中,错误的是

    A)对象就是C语言中的结构体变量     B)对象代表着正在创建的系统中的一个实体

    C)对象是一个状态和操作(或方法)的封装体     D)对象之间的信息传递是通过消息进行的

（5）下列关于队列的叙述中正确的是

    A)在队列中只能插入数据    B)在队列中只能删除数据     C)队列是先进先出的线性表    D)队列是先进后出的线性表

（6）已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是

    A)acbed       B)decab     C)deabc       D)cedba

（7）某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为

    A)n+1         B)n-1          C)2n           D)n/2

（8）设有如下三个关系表

R            S                   T

A            B     C            A     B     C

m           1     3            m    1     3

n                                 n     1     3

下列操作中正确的是

    A) T=R∩S    B) T=R∪S    C) T=R×S    D) T=R/S

（9）下列叙述中,正确的是

    A)用E-R图能够表示实体集间一对一的联系、一对多的联系和多对多的联系    B)用E-R图只能表示实体集之间一对一的联系     C)用E-R图只能表示实体集之间一对多的联系     D)用E-R图表示的概念数据模型只能转换为关系数据模型

（10）下列有关数据库的描述,正确的是

    A)数据处理是将信息转化为数据的过程     B)数据的物理独立性是指当数据的逻辑结构改变时,数据的存储结构不变

    C)关系中的每一列称为元组,一个元组就是一个字段     D)如果一个关系中的属性或属性组并非该关系的关键字,但它是另一个关系的关键字,则称其为本关系的外关键字

（11）C语言规定,在一个源程序中,main函数的位置

    A)必须在最开始    B)必须在系统调用的库函数的后面     C)可以任意    D)必须在最后

(1)D    【解析】算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度是指执行这个算法所需要的内存空间。

(2)D    【解析】在结构化程序设计中,一般较优秀的软件设计尽量做到高内聚、低耦合,这样有利于提高软件模块的独立性,也是模块划分的原则。

(3)C    【解析】软件测试的目标是在精心控制的环境下执行程序,以发现程序中的错误,给出程序可靠性的鉴定。它有3个方面的重要特征,即测试的挑剔性、完全测试的不可能性及测试的经济性。其中,没有测试的可靠性这一说法。

(4)A    【解析】对象是由数据和容许的操作组成的封装体,与客观实体有直接的对应关系,对象之间通过传递消息互相联系,从模拟现实世界中不同事物彼此之间的联系,B)、C)、D)是正确的,对象的思想广泛应用于C++、Java等语言中,因此A)错误。

(5)C    【解析】队列是一种操作受限的线性表。它只允许在线性表的一端进行插入操作,另一端进行删除操作。其中,允许插入的一端称为队尾(rear),允许删除的一端称为队首(front)。队列具有先进先出的特点,它是按"先进先出"的原则组织数据的。

(6)D    【解析】依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成,右子树为空;又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成,如下图所示,求得该二叉树的前序遍历序列为选项D)。

 (7)A   【解析】对于任何一棵二叉树T,如果其终端结点(叶子)数为n1,度为2的结点数为n2,则n1=n2+1,所以该二叉树的叶子结点数等于n+1。

(8)C    【解析】对于两个关系的合并操作可以用笛卡尔积表示。设有n元关系R和m元关系S,它们分别有p和q个元组,则R与S的笛卡儿积记为R×S它是一个m+n元关系,元组个数是p×q由题意可得,关系T是由关系R与关系S进行笛卡尔积运算得到的。

(9)A    【解析】两个实体之间的联系实际上是实体集间的函数关系,这种函数关系可以有下面几种,即一对一的联系、一对多(或多对一)的联系和多对多的联系;概念模型便于向各种模型转换。由于概念模型不依赖于具体的数据库管理系统,因此,容易向关系模型、网状模型和层次模型等各种模型转换。

(10)D    【解析】数据处理是指将数据转换成信息的过程,故选项A)叙述错误;数据的物理独立性是指数据的物理结构的改变,不会影响数据库的逻辑结构,故选项B)叙述错误;关系中的行称为元组,对应存储文件中的记录,关系中的列称为属性,对应存储文件中的字段,故选项C)叙述错误。

(11)C    【解析】不论main函数在整个过程中的位置如何,一个C程序总是从main函数开始执行的。