数据结构作业答案.doc

单选题1、下列关于算法的基本特征,说法不正确的是()。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义,不允许模棱两可。算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。[D]教师批改:D2、算法的时间复杂度取决于()。问题的规模待处理的数据的初态问题的难度A和B[D]教师批改:D3、下列选项中,不是算法基本特征的是()。可行性有穷性确定性高效率[D]教师批改:D4、通常一个好的算法应达到的目标中,不包括()。正确性可读***性健壮性[C]教师批改:C5、在一般的计算机系统中,基本的运算和操作不包括()。语法处理算术运算关系运算数据传输[A]教师批改:A6、工程上常用的分治法是()。列举法归纳法减半递推技术回溯法[C]教师批改:C多选题7、算法设计的要求包括()。正确性可读性健壮性唯一性[ABC]教师批改:A,B,C8、算法的时间复杂度应该与()无关。所使用的计算机程序设计语言基本运算的执行次数程序编制者[ABD]教师批改:A,B,D9、下列关于算法的描述中,不正确的有()。算法即是计算机程序算法是解决问题的计算方法算法是排序方法算法是解决问题的有限运算序列[ABC]教师批改:A,B,C填空题16、所谓算法是指()。教师批改:解题方案的准确而完整的描述17、算法的基本特征有()、()、()和()教师批改:能行性、确定性、有穷性和拥有足够的情报。18、一个算法通常由两种基本要素组成,它们是()和()。教师批改:算法中对数据的运算和操作。算法的控制结构。19、工程上常用的几种算法设计方法有列举法、()、()、()、()和回溯法。教师批改:归纳法、递推、递归、减半递推技术。20、算法的复杂度主要包括()复杂度和()复杂度。教师批改:时间、空间综合题设给定3个整数a,b,c,试写出寻找这3个整数的中数的算法;并分析在平均情况与最坏情况下,该算法分别要做多少次比较?寻找这3个整数的中数的算法用C语言描述如下(中数m由函数值返回):intmid(inta,intb,intc){intm;m=a;if(m>=b){if(m>=c){if(b>=c)m=b;elsem=c;}}else{if(m<=c){if(b>=c)m=c;elsem=b;}}return(m);}假设a,b,c中的每一个数为中数的概率相等(均为1/3)。由于当a为中数时需要比较2次,b或c为中数时均需要比较3次,因此,在平均情况下上述算法所需要的比较次数为2*(1/3)+3*(1/3)+3*(1/3)=8/3即在平均情况下,上述算法需要比较8/3次。在最坏情况下,上述算法需要比较3次(当b或c为中数时)。第二章选择题1、下列排序方法中,哪一个是稳定的排序方法()。归并排序稀尔排序堆排序快速排序[A]教师批改:A2、设输入序列为1,2,3,4,借助一个栈得到的输出序列可以是()。3,4,1,24,2,1,34,1,2,31,3,4,2[D]教师批改:D3、用数组A[m]存放循环队列的元素值,若其头尾指针分别为front和rear,则循环队列中当前元素的个数为()。(rear+front)%m(rear-front+m)%m(rear-front)%m(rear-front+1)%m[D]教师批改:B4、对于下三角矩阵A