第1套1下列叙述中正确的是A.算法的空间复杂度与算法所处理的数据存储空间有关B.算法的空间复杂度是指算法程序控制结构的复杂程度C.算法的空间复杂度是指算法程序中指令的条数D.压缩数据存储空间不会降低算法的空间复杂度A【解析】算法的时间复杂度是指执行这个算法所需要的内存空间，包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术。A选项正确。2下列各组排序法中，最坏情况下比较次数相同的是A.希尔排序与堆排序B.简单插入排序与希尔排序C.简单选择排序与堆排序D.泡排序与快速排序D【解析】对长度为n的线性表，下表为常用排序算法最坏情况下比较次数：上表中未包括希尔排序，因为希尔排序的时间效率与所取的增量序列有关，如果增量序列为：d1=n/2,di+1=di/2，在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。由表格可知冒泡排序与快速排序比较次数相同，D选项正确。3设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=20，则栈中的元素个数为A.31B.30C.21D.20A【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=51，当top=20时，元素依次存储在单元20：50中，个数为50-19=31，A选项正确。4某二叉树共有400个结点，其中有100个度为1的结点，则该二叉树中的叶子结点数为A.149B.150C.151D.不存在这样的二叉树D【解析】在树结构中，一个结点所拥有的后件个数称为该结点的度。对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。二叉树中有400个结点，设叶子结点个数为n0，度为1的结点个数为100，设度为2的结点个数为n2。400=n0+100+n2且n0=n2+1，则n0=150.5，n2=149.5。由于结点个数必须是整数，所以不存在这样的二叉树，故选择D选项。5.下面属于“类-对象”主要特征的是A.对象一致性B.对象无关性C.类的多态性D.类的依赖性C【解析】类-对象的基本特点如下：由表格可知“类-对象”主要特征包括类的多态性，故C选项正确。6.下面不属于需求分析阶段工作的是A.需求获取B.可行性研究C.需求分析D.撰写软件需求规格说明书B【解析】需求分析阶段对待开发软...
