计算机二级Access单项选择2.doc

在最坏情况下 A) 快速排序的时间复杂度比冒泡排序的时间复杂度要小 B) 快速排序的时间复杂度比希尔排序的时间复杂度要小 C) 希尔排序的时间复杂度比直接插入排序的时间复杂度要小 D) 快速排序的时间复杂度与希尔排序的时间复杂度是一样的 【解析】对长度为n的线性表排序，下表为常用排序方法时间复杂度： 方法 平均时间 最坏情况时间 冒泡排序 O(n2) O(n2) 直接插入排序 O(n2) O(n2) 简单选择排序 O(n2) O(n2) 快速排序 O(nlog2n) O(n2) 堆排序 O(nlog2n) O(nlog2n) 上表中未包括希尔排序，因为希尔排序的时间效率与所取的增量序列有关，如果增量序列为：d1=n/2, di+1=di/2，在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。快速排序与冒泡排序的时间复杂度均为O(n2)，A选项错误。快速排序比希尔排序的时间复杂度要大（O(n2)O(n1.5))，B选项错误。希尔排序的时间复杂度比直接插入排序的时间复杂度要小（O(n1.5)O(n2))，C选项正确。快速排序比希尔排序的时间复杂度大（O(n2)O(n1.5))，D选项错误。 在深度为7的满二叉树中，度为2的结点个数为 A) 64 B) 63 C) 32 D) 31 【解析】在树结构中，一个节点所拥有的后件个数称为该节点的度。深度，定义一棵树的根节点所在的层次为１，其他节点所在的层次等于它的父节点所在的层次加１，树的最大层次称为树的深度。满二叉树指除最后一层外，每一层上的所有节点都有两个子节点的二叉树。一棵深度为K的满二叉树，整棵二叉树共有2K-1个节点；满二叉树在其第i层上有2i-1个节点。在满二叉树中，只有度为2和度为0的节点。深度为7的满二叉树，节点个数为27-1=127，第七层叶节点个数为27-1=64，则127-64=63， B选项正确。 设栈的顺序存储空间为S(1: m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 A) 30 B) 20 C) m-19 D) m-20 【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即是取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=m+1，当top=20时，元素依次存储在单元20：m中，个数为m-19，C选项正确。 算法空间复杂度的度量方法是 A) 算法程序的长度 B) 算法所处理的数据量 C) 执行算法所需要的工作单元 D) 执行算法所需要的存储空间 【解析】算法的空间复杂度是指执行这个算法所需要的内存空间，。算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。D选项正确。 下面不属于软件开发阶段任务的是 A) 测试 B) 可行性研究 C) 设计 D) 实现 【解析】软件生命周期分为3个时期共8个阶段：软件定义期，包括问题定义、可行性研究、需求分析；软件开发期，包括概要设计、详细设计、实现、测试；运行维护期，即运行维护阶段。可行性研究属于软件定义期任务，B选项错误。 下面属于字符类的实例是 A) 518 B) 5 C) nm D) \n 【解析】字符实例的一般形式是用一对单引号括起来的一个字符。另外ASCII码中还有一些控制字符，C语言中用转义字符的形式来书写这些常，转义字符一反斜杠（\）开始，后面跟1个字符或字符序列。518单引号中有三个字符，A选项错误。5双引号为字符串，B选项错误。nm单引号中有两个字符，C选项错误。\n为换行符，属于字符类实例，D选项正确。 某系统结构图如下图所示 该系统结构图的最大扇出数是 A) n B) 1 C) 3 D) 4 【解析】扇出指的是由一个模块直接调用的其他模块数。题干中某系统为一个模块，其扇出数目为n(n3)，功能1与功能n模块扇出数均为2，故A选项正确。 一个兴趣班可以招收多名学生，而一个学生可以参加多个兴趣班。则实体兴趣班和实体学生之间的联系是 A) 1:1联系 B) 1:m联系 C) m:1联系 D) m:n联系 【解析】一般来说，实体集之间必须通过联系来建立联接关系，分为3类：一对一联系（1:1）、一对多联系（1:m）、多对多联系（m:n）。多个兴趣班与多个学生的关系为m:n联系，D选项正确。 有三个关系表R、S和T如下，其中三个关系对应的关键字分别为A，B和复合关键字（A，B）。 表T的记录项