数据结构第10章作业

第10章排序作业作业一：1）对人意的7个关键字进行排序，至少要进行_______次关键字之间的两两比较。A.13B.11C.15D.16E.19【参考答案】C【解题思路】任何一个借助“比较”进行排序的算法，在最坏的情况下所需进行得比较次数至少为[)!(log2n]。[)!7(log2]=15。2）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_________。A.希尔排序B.冒泡排序C.插入排序D.选择排序【参考答案】C【解题思路】插入排序的思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。3）对记录的关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：5026388070908304020508304020902638807026830402080503890708202630384050708090其使用的排序方法是_________。A.快速排序B.希尔排序C.基数排序D.归并排序【参考答案】B【解题思路】由排序的结果直接可以确知（即使不知道其他几中排序方法）该排序是增量序列为5,3,1的希尔排序。4）已知序列{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）作业二：1）快速排序方法在_____情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数【参考答案】C【解题思路】要排序的数据（个数为n）已基本有序，采用快速排序则需要n-1趟，其时间复杂度升至O(n2)。2）用快速排序方法对线性表(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【解题思路】每一次将一个子序列以第一个元素为基准分为两段。作业三：1）采用简单选择排序，比较的次数与移动次数分别是________.A.)(log),(2nOnOB.)(),(log22nOnOC.)(),(2nOnOD.)(),log(2nOnnO【参考答案】C【解题思路】简单选择排序过程是：每趟从n-i+1个记录中选取关键字最小的记录（每趟比较的时间复杂度为O(n)）,并和第i个记录交换（每趟移动的时间复杂度为O(1)），因此，总的比较次数与移动次数分别是)(),(2nOnO。2）对n个元素的序列进行排序时，堆排序所需要的附加存储空间是_______.A.)(log2nOB.)1(OC.)(nOD.)log(2nnO【参考答案】B【解题思路】堆排序本质上是就地排序。3）已知序列{503，87，512，61，908，170，897，275，653，462}，给出采用堆排序法对该序列做降序排序时的每一趟的结果。【参考答案】排序结果为908,897,653,512,503,462,275,170,87,61。5交换897和61,输出89765350351217087462275616筛选调整61653512170874625032753交换908和87,输出90889765351217087462503275614筛选调整8765389717051246250327561503875121708979086127565334621初始堆90865389717051246250327561872建堆13交换462和87,输出462275871706114筛选调整275170618711交换503和61,输出503462275170876112筛选调整46217087275619交换512和87,输出512503462170618727510筛选调整87503170614622757交换653和61,输出65351250317061874622758筛选调整6150351217087462275作业四：1）一组纪录的排序码为{25，48，16，35，79，82，23，40，36，72}，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_______.A.16253548234079823672B.16253548798223364072C.16234835798223364072D.16253548792336407282【参考答案】A【解题思路】一趟归并过程如下：19交换87和61,输出8720输出616117交换170和61,输出17087-6118筛选调整876115交换275和61,输出275170-876116筛选调整87170612）就排序的算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是_______。A.堆排序快速排序归并排序B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序【参考答案】A【解题思路】堆排序、快速排序、归并排序所用的辅助空间依次是:O(1)、)(log2nO、O(n)。3)已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列作升序排序的每一趟结果。【参考答案】初始:10,18,4,3,6,12,1,9,15,8第1趟：[10,18][3,4][6,12][1,9][8,15]第2趟：[3,4,10,18][1,6,9,12][8,15]第3趟：[3,4,10,18][1,6,8,9,12,15]第4趟：[1,3,4,6,8,9,10,12,15,18]25，48，16，35，79，82，23，40，36，7216，25，35，48，23，40，79，82，36，72