算法与数据结构（C++语言版）（第2版） 第12章课后习题答案

PAGEPAGE4习题答案选择题1-5：ABCDC6-10：DCCCC填空题1、（1）比较（2）移动2、（1）减小（2）13、冒泡快速4、希尔排序、简单选择排序、快速排序、堆排序等5、外排序判断题1-5：错错错错对应用题1、设待排序的关键字序列为{15，21，6，30，23，6′，20，17}，试分别写出使用以下排序方法每趟排序后的结果。(1)直接插入排序 (2)希尔排序(增量为5，2，1) (3)冒泡排序 (4)快速排序 (5)直接选择排序 (6)堆排序(7)二路归并排序 【解答】(1)直接插入排序初始关键字序列：15，21，6，30，23，6′，20，17第一趟直接插入排序：【15，21】第二趟直接插入排序：【6，15，21】第三趟直接插入排序：【6，15，21，30】第四趟直接插入排序：【6，15，21，23，30】第五趟直接插入排序：【6，6′，15，21，23，30】第六趟直接插入排序：【6，6′，15，20，21，23，30】第七趟直接插入排序：【6，6′，15，17，20，21，23，30】(2)希尔排序(增量为5，2，1)初始关键字序列：15，21，6，30，23，6′，20，17第一趟希尔排序：6′，20，6，30，23，15，21，17第二趟希尔排序：6′，15，6，17，21，20，23，30第三趟希尔排序：6′，6，15，17，20，21，23，30(3)起泡排序初始关键字序列：15，21，6，30，23，6′，20，17第一趟起泡排序：15，6，21，23，6′，20，17，30第二趟起泡排序：6，15，21，6′，20，17，23，30第三趟起泡排序：6，15，6′，20，17，21，23，30第四趟起泡排序：6，6′，15，17，20，21，30，23第五趟起泡排序：6，6′，15，17，20，21，30，23(4)快速排序初始关键字序列：15，21，6，30，23，6′，20，17第一趟快速排序：【6′，6】15【30，23，21，20，17】第二趟快速排序：6′，6，15【17，23，21，20】30第三趟快速排序：6′，6，15，17【23，21，20】30第四趟快速排序：6′，6，15，17，【20，21】23，30第五趟快速排序：6，6′，15，17，20，21，30，23(5)直接选择排序初始关键字序列：15，21，6，30，23，6′，20，17第一趟直接选择排序：6，21，15，30，23，6′，20，17第二趟直接选择排序：6，6′，15，30，23，21，20，17第三趟直接选择排序：6，6′，15，30，23，21，20，17第四趟直接选择排序：6，6′，15，17，23，21，20，30第五趟直接选择排序：6，6′，15，17，20，21，23，30第六趟直接选择排序：6，6′，15，17，20，21，23，30第七趟直接选择排序：6，6′，15，17，20，21，23，30(6)堆排序 初始关键字序列：15，21，6，30，23，6′，20，17初始堆：6，17，6’第一次调堆：6’第二次调堆：15，17，20，21，23，30，【6’第三次调堆：17，21，20，30，23，【15，6’，6】第四次调堆：20，21，23，30，【17，15，6’，6】第五次调堆：21，30，23，【20，17，15，6’，6】第六次调堆：23，30，【21，20，17，15，6’，6】第七次调堆：30，【23，21，20，17，15，6’，6】堆排序结果调堆：【30，23，21，20，17，15，6’，6】(7)二路归并排序初始关键字序列：15，21，6，30，23，6′，20，17二路归并排序结果：15，17，20，21，23，30，6’，6final↑↑first2、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【解答】见下表：排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O(n2)O(n2)O(1)稳定折半插入排序O(n2)O(n2)O(1)稳定二路插入排序O(n2)O(n2)O(n)稳定表插入排序O(n2)O(n2)O(1)稳定起泡排序O(n2)O(n2)O(1)稳定直接选择排序O(n2)O(n2)O(1)不稳定2,2’希尔排序O(n1.3)O(n1.3)O(1)不稳定3,2,2’快速排序O(nlog2n)O(n2)O(log2n)不稳定2,2’堆排序O(nlog2n)O(nlog2n)O(1)不稳定2,1,1’2-路归并排序O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d*(rd+n))O(d*(rd+n))O(rd)稳定3、判断下面的每个结点序列是否能表示堆，如果不是堆，请把它调整成堆。100，90，80，60，85，75，20，25，10，70，65，50100，70，50，20，90，75，60，25，10，85，65，80【解答】(1)是堆(2)不是堆。调成大堆：100,90,80,25,85,75,60,20,10,70,65,504、奇偶交换排序如下所述：对于初始序列A[1]，A[2]，…，A[n]，第一趟对所有奇数i(1<=i<n)，将A[i]和A[i+1]进行比较，若A[i]>A[i+1]，则将两者交换；第二趟对所有偶数i(2<=i<n)，将A[i]和A[i+1]进行比较，若A[i]>A[i+1]，则将两者交换。第三趟对所有奇数i(1<=i<n)；第四趟对所有偶数i(2<=i<n)，…，依次类推直至到整个序列有序为止。(1)分析这种排序方法的结束条件。(2)写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。【解答】排序结束条件为，连续的第奇数趟排序和第偶数趟排序都没有交换。第一趟奇数：35,70,33,65,21,24,33第二趟偶数：35,33,70,21,65,24,33第三趟奇数：33,35,21,70,24,65,33第四趟偶数：33,21,35,24,70,33,65第五趟奇数：21,33,24,35,33,70,65第六趟偶数：21,24,33,33,35,65,70第七趟奇数：21,24,33,33,35,65,70(无交换)第八趟偶数：21,24,33,33,35,65,70(无交换)结束5、①快速排序②冒泡排序③直接插入排序④堆排序算法设计题1、对给定关键字序号j(1<j<n)，要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找。(要求用最少的时间和最少的空间)。例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。[题目分析]在无序记录r[n]中，找到第j（1<=j<=n）个记录，利用快速排序思想，找到第一轴元素的位置i，若i=j则查找结束。否则，根据j<i或j>i，在1~i-1或i+1~n之间查找，直到i=j为止。template<classType>voidfindJ(TypeA[],intn,intj){inti=partition(A,1,n);while(i!=j)if(i<j)i=partition(A,i+1,n); //在后半部分继续进行划分elsei=partition(A,1,i-1); //在前半部分继续进行划分cout<<A[i]<<endl;}2、按由大到小的顺序对一含有n个元素的数组A[n]进行排序，利用如下改进的简单选择排序方法：第一次选出最大者存入A[0]，第二次选出最小者存入A[n-1]，第三次选出次大者存入A[1]，第四次选出次小者存入A[n-2]，如此大小交替地选择，直到排序完毕。voidSimple_Selection(intA[]，intn)∥改进的选择排序，选大和选小交替进行，按题意，元素下标从0开始{for(i=0;i<n/2;i++){k=i;∥k记最大元素下标for(j=i+1;j<=n-1-i;j++)if(A[j]>A[k])k=j;∥选第i+1个最大元素(i从0开始)if(k!=i)A[i]<-->A[k];∥选出第i+1个最大元素ii=k=n-1-i;∥k记最小元素下标for(j=n-1-i;j>i;j--)if(A[j]<A[k])k=j;∥选第i+1个最小元素if(k!=ii)A[ii]<-->A[k];∥选出第i+1个最小元素}∥高层for}∥Simple_Selection设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。设计算法重新安排砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，将r[0..j-1]作为红色，r[j..k-1]为白色，r[k..n-1]为兰色。从j=0开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。为方便处理，将三种砾石的颜色用整数1、2和3表示。voidQkSort(Typer[]，intn)∥本算法对含有n个元素(砾石)的顺序表r排序，使所有红色砾石在前，白色居中，兰色在最后{inti=0，j=0，k=n-1，temp;while(j<=k)if(r[j]==1)∥当前元素是红色{temp=r[i];r[i]=r[j];r[j]=temp;i++;j++;}elseif(r[j]==2)j++;∥当前元素是白色else∥(r[j]==3当前元素是兰色{temp=r[j];r[j]=r[k];r[k]=temp;k--;}4、请编写一个算法，在基于单链表表示的关键字序列上进行简单选择排序。voidLinkedListSelectSort(LinkedListhead);∥本算法一趟找出一个关键字最小的结点,其数据和当前结点进行交换{p=head->next;while(p){q=p->next;r=p;∥设r是指向关键字最小的结点的指针while(q!=null){if(q->data<r->data)r=q;q=q->next;}if(r!=p)r->data<-->p->data;p=p->next;∥选下一个最小元素}【算法讨论】本算法只交换两个结点的数据，若要交换结点，则须记下当前结点和最小结点的前驱指针5、已知记录序列a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组c[1..n]，对每个记录a[i]，统计序列中关键字比它小的记录个数存于c[i]，则c[i]=0的记录必为关键字最小的记录，然后依c[i]值的大小对a中记录进行重新排列，编写算法实现上述排序方法。voidCountSort(rectyper[],intn){//对r[1..n]进行计数排序 c[1..n]=0;//c数组初始化，元素值指其在r中的位置。 for(i=1;i<n;i++)//一趟比较选出大小，给数组c赋值 for(j=i+1;j<=n;j++) if(r[i].key>r[j].key)c[i]++; elsec[j]++; i=1; c[1..n]=c[1..n]+1;//c数组元素值指其在r中的位置。 while(i<n) {while(c[i]!=i) {j=c[i];c[i]c[j];r[i]r[j];} i=i+1; }6.引自知乎：2022年408真题数据结构篇（修订版）-知乎()/p/565209806方法一：选择排序思想（1）遍历A[1..n]，找到最小值交换到A[1]。遍历A[2..n]，找到最小值交换到A[2]。遍历A[3..n]，找到最小值交换到A[3]。……遍历A[10..n]，找到最小值交换到A[10]。此时A[1..10]保存的就是排序好的最小的10个数。（2）算法分析：时间复杂度：O(n)，需要遍历10次数组。空间复杂度：O(1)，中间过程额外需要常数个变量。如果这里将10修改为k，则：时间复杂度：O(nk)，需要遍历k次数组。方法二：堆排序思想（1）先用A[1..10]]原地建立大顶堆（注意：这里不能用小顶堆），然后遍历剩余元素A[11..n]，每个元素A[i]（11≤i≤n）都要和堆顶元素A如果A[i]小于堆顶元素A[1]，那么就删除堆顶元素，将A[i]放入堆顶，然后将A[1..10]重新调整为大顶堆。当剩余元素（即A[11..n]）全部扫描完毕，堆中保存的就是最小的10个数。（2）算法分析：时间复杂度：O(n)，由于堆大小为常量，所以建堆，维护堆的代价为O(1)，仅需要遍历一遍数组，该算法时间复杂度为O(n)。空间复杂度：O(1)，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为O(1)。如果这里将10修改为k，则：时间复杂度：O(nlogk)，所以建堆的代价为O(k)，每次维护堆的代价为O(logk)，仅需要遍历一遍数组，总共n个元素，该算法时间复杂度为O(nlogk)。方法三：快速排序思想【中科院研究生院2003十二(15分)】【武汉理工大学2002四.3(35/3分)】曾有过相似题。题目已经给出重要提示：“平均情况下的比较次数尽可能少”，明显指向随机化选择算法。也是本题的最优解。经过快速排序算法的一次划分（partition），凡关键字小于轴的均移动至枢轴之前，凡关键字大于枢轴的均移动至枢轴之后。一趟排序后，枢轴元素保存在了下标i处，则i将序列划分为两个子序列L和R，