数据结构作业.doc

第10章排序作业作业一:对人意的7个关键字进行排序,至少要进行_______次关键字之间的两两比较。【参考答案】C【解题思路】任何一个借助“比较”进行排序的算法,在最坏的情况下所需进行得比较次数至少为[]。[]=15。排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为_________。 【参考答案】C【解题思路】插入排序的思想是:每一趟将一个待排序的记录,按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。对记录的关键字为{50,26,38,80,70,90,8,30,40,20}进行排序,各趟排序结束时的结果为:5026388070908304020508304020902638807026830402080503890708202630384050708090其使用的排序方法是_________。 【参考答案】B【解题思路】由排序的结果直接可以确知(即使不知道其他几中排序方法)该排序是增量序列为5,3,1的希尔排序。已知序列{70,83,100,65,10,32,7,9},请给出采用插入排序法对该序列作升序排序时的每一趟的结果。【参考答案】采用插入排序方法排序的各趟的结果如下:初始:(70),83,100,65,10,32,7,9第一趟:(70,83),100,65,10,32,7,9第二趟:(70,83,100),65,10,32,7,9第三趟:(65,70,83,100),10,32,7,9第四趟:(10,65,70,83,100),32,7,9第五趟:(10,32,65,70,83,100),7,9第六趟:(7,10,32,65,70,83,100),9第七趟:(7,9,10,32,65,70,83,100)作业二:快速排序方法在_____情况下最不利于发挥其长处。 【参考答案】C【解题思路】要排序的数据(个数为n)已基本有序,采用快速排序则需要n-1趟,其时间复杂度升至O(n2)。用快速排序方法对线性表(24,84,20,47,15,26,68,35,19)进行排序时,写出元素序列的变化情况:【参考答案】(1)24,84,20,47,15,26,68,35,19(2)19,15,20,24,47,26,68,35,84(3)15,19,20,24,35,26,47,68,84(4)15,19,20,24,26,35,47,68,84【解题思路】每一次将一个子序列以第一个元素为基准分为两段。作业三:采用简单选择排序,.【参考答案】C【解题思路】简单选择排序过程是:每趟从n-i+1个记录中选取关键字最小的记录(每趟比较的时间复杂度为O(n)),并和第i个记录交换(每趟移动的时间复杂度为O(1)),因此,总的比较次数与移动次数分别是。对n个元素的序列进行排序时,.【参考答案】B【解