数据结构（Java语言版）-习题及答案 第9章排序习题答案

第9章排序习题参考答案 一、单选题ABCDABCDn-1n+1n/2.nn/2ABCABCD排序的总趟数元素的移动次数使用辅助空间的数量元素之间的比较次数ABCABCD冒泡排序直接插入排序希尔排序二路归并排序对整数序列（8，9，10，4，5，6，20，1，2）进行递增排序，采用每趟冒出一个最小元素的冒泡排序算法，需要进行的趟数是 。AABCD468.对一组数据（2，12，16，88，5，10）进行排序，若前三趟的结果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是 。AABCD希尔排序二路归并排序基数排序

ABCABCD781213ABCD对关键字序列（，，，，，，，ABCD.，，，)602).，，，)8，，)C.，，，)8，，).，，，)8，，)ABCABCD快速排序在所有排序方法中为最快，而且所需辅助空间也最少在快速排序中，不可以用队列替代栈快速排序的空间复杂度为On)快速排序在待排序的数据随机分布时效率最高.n（n为大于10000的整数）个无序元素，希望用最快速度从中选择前k（1≤k≤n）个关键字最小的元素，在以下排序方法中应选择 。AABCD快速排序希尔排序二路归并排序直接插入排序ABCABCD直接插入排序冒泡排序简单选择排序都一样ABCABCDn2n2n-1n-1ABCDABCD.（，，，，，，，，，，）.（，，，，，，，，，，）C.（，，，，，，，，，，）.（，，，，，，，，，，）ABCD有一个整数序列为（，，，，，，，ABCD.（，，，，，，，）.（，，，，，，，）C.（，，，，，，，）.ABCABCDngngn+1n2ABCABCD快速排序二路归并排序基数排序堆排序ABCABCD10000个实数1000个由字母、数字和其他字符组成的字符串个n类型的整数10000个100以内的正整数对给定的关键字序列（110，119，007，911，114，120，122）进行基数排序，则第2趟分配收集后得到的关键字序列是 。A.，，，，，，2ABCD.，，，，，BCDC.，，，，，，2.，，，，，，9ABCABCD冒泡排序直接插入排序快速排序堆排序ABCD数据序列（，，，，，，，，ABCD简单选择排序冒泡排序直接插入排序堆排序ABCABCD简单选择排序希尔排序堆排序冒泡排序ABCABCD简单选择排序冒泡排序二路归并排序堆排序ABCABCD快速排序冒泡排序堆排序简单选择排序ABCD整数序列（，，，，，，，，ABCD冒泡排序二路归并排序堆排序简单选择排序ABCABCD外排序把外存文件调入内存，再利用内排序进行排序，所以外排序所花时间完全由采用的内排序决定外排序分为产生初始归并段和多路归并两个阶段外排序并不涉及文件的读写操作外排序完全可以由内排序来替代将一个由置换-选择排序方法得到的输出文件F1作为输入文件再次进行置换-选择排序，得到输出文件F2，问F1和F2的差异是 。AABCDF2中归并段的最大长度增大F2和F1无差异归并段个数及各归并段长度均不变，但F2中可能存在与F1不同的归并段AB采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k 。AB有关无关ABCABCD1/k/kgkmAB设有100初始归并段，如采用k路平衡归并3趟完成排序，则k值是 。AB56CDCD8ABm个初始归并段采用k路平衡归并时，构建的败者树中共有 个结点（不计冠军结点）。AB2k-1.2kCDC.CD.1ABCABCD0123ABCABCD该排序算法不允许有相同的关键字记录该排序算法允许有相同的关键字记录平均时间为Ongn的排序方法以上都不对ABCABCD经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变排序算法的性能与被排序元素的数量关系不大排序算法的性能与被排序元素的数量关系密切ABCABCD这两个元素的前后位置不发生变化这两个元素的前后位置一定发生变化这两个元素的位置不发生变化这两个元素的前后位置可能发生变化ABCABCD稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同排序方法都是在顺序表上实现的，在链表上无法实现排序方法在顺序表上实现的排序方法在链表上也可以实现ABCABCD二路归并排序拓扑排序堆排序直接插入排序ABCABCD简单选择排序冒泡排序归并排序堆排序ABCABCD希尔选择快速排序归并排序堆排序ABCD下列排序方法中，辅助空间为OnABCD希尔选择冒泡排序堆排序归并排序A下列四种排序中（）的空间复杂度最大。 A直接插入排序BBCD堆排序二路归并排序ABCABCDABCABCD快速排序归并排序基数排序堆排序ABCABCD快速排序堆排序希尔排序基数排序ABCABCD10n52ABCABCD10n52ABCABCD10000个实数1000个由字母、数字和其他字符组成的字符串个n类型的整数10000个100以内的正整数ABCABCD直接插入排序和快速排序直接插入排序和冒泡排序简单选择排序和归并排序归并排序和冒泡排序ABCABCD快速排序冒泡排序堆排序希尔排序ABCABCD0nn-13n(n-1)/2ABCABCD01n3n(n-1)/2二、编程题OJ—N排序问题时间限制：，空间限制：。问题描述：：一个序列中的未排序的度量是相对于彼此顺序不一致的条目对的数量，例如，在字母序列EC中，该度量为，因为D大于右边是个字母，E大于其右边的个字母。该度量称为该序列的逆序数。序列CE只有一个逆序对（E和），它几乎被排序好了，而序列Q有个逆序对，它是未排序的，恰好是反序。你需要对若干个N序列（仅包含个字母、C、和的字符串）分类，注意是分类而不是按字母顺序排序，而是按照“最多排序”到“最小排序”的顺序排列，所有DNA序列的长度都相同。输入格式：第一行包含两个整数，n（0<n≤50）表示字符串长度，m（0<m≤100）表示字符串个数。后面是m行，每行包含一个长度为n的字符串。输出格式：按“最多排序”到“最小排序”的顺序输出所有字符串。若两个字符串的逆序对个数相同，按原始顺序输出它们。答：prtvu*;csEeype{ntv; //存放r的逆序数nt; //存放字符串的下标i}pubccsn{cntN=;cnt=;cntn; //相邻整数的最小交换数量cn]=newnN; //存放整数序cvdergechrntntdnthgh)//两个相邻有序段归并{nt=;ntntk=;chrb=newchrhgh+; //开辟临时空间hei<=d&j<=hgh) //二路归并：d、d+hgh=>b{>){bk++=++;n+=d+; /计逆序数}eebk++=++;}hei<=d)bk++=++;hej<=hgh)bk++=++;rntk=;k1<k;k++) //bk=>hgh]+k=bk;}cvdergeSrchrntnt)//二路归并排序{>=)reurn; //的长度为或者时返回nt=+/; //取中间位置mergeSr; //对前子表排序ergeSr+; //对后子表排序erge; //将两个有序子表合并成一个有序表}cntInvernchrntn) //二路归并法求字符串的逆序数{n=;ergeSrn;returnans;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;Srng]r=newSrng;Eeype]b=newEeype;chr]p=newchrN;n=nnexIn;=nnexIn; //输入n和mrnt=;i<;++) //输入r=nnex;rnt=;i<;++) //求所有字符串的逆序数{rnt=;j<rengh;++)//将r复制的字符数组p中p=rchr;b=newEeype;bv=Invernpn; //求p的逆序b=; //记录原来的下标}rryrbnewCprr<Eeype>){pubcntcpreEeypeEeype){fvv==) //v相同时按reurn;ee //v不相同时按vreurnvv;}});rnt=;i<;++) //输出结果Syeuprn"%\n"rb;}}.OJ—求中位数问题时间限制：，空间限制：。问题描述：：FJ正在调查他的牛群以寻找最普通的牛群，他想知道产奶量的中位数：一半奶牛的产奶量与中位数一样多或更多，：一半奶牛的产奶量与中位数一样多或更少。输入格式：给定n（n为奇数，≤n<）头牛的牛奶产量（到），找到这些奶牛中产奶量的中位数。输入的第1行为整数n，第2行到第n+1中每行包含一个整数，表示一头牛奶的产奶量。输出格式：输出一行表示产奶量的中位数。答：prtvuScnner;prtvu*;pubccsn{pubccvdnSrng]rg){nlntN=;n]=newnN;Scnnern=newScnnerSyen;henhNex){ntn=nnexIn;rnt=;i<n;++)=nnexIn;rryrn;Syeuprnnn/;}}}OJ—求中位数时间限制：，空间限制：。问题描述：：对于这个问题，你需要编写一个程序读取一系列整数，在读取每个奇数序号的整数后输出到目前为止接收的整数的中值（中位数）。输入格式：第一行输入包含一个整数t（1≤t≤1000）表示数据集个数。每个数据集的第一行包含数据集编号，后跟一个空格，后跟一个奇数十进制整数（≤≤），表示要处理的有符号整数的个数，数据集中的其余行由每行个整数组成，由单个空格分隔。数据集中的最后一行可能包含少于10个整数。输出格式：对于每个数据集，第一行输出包含数据集编号，单个空格和中位数个数（应该是输入整数个数的一半加一），将在以下行中输出中位数，每行10个由单个空格分隔。最后一行可能少于10个元素，但至少有1个元素。输出中没有空行。答：prtvuScnner;prtvu*;pubccsn{crryQueue<neger>=newrryQueue<neger>;//小根堆crryQueue<neger>bg=newrryQueue<neger>newCprr<neger>){@OverrdepubcntcpreInegerIneger) //大根堆{reurnn;}});crry<neger>n=newrry;//存放中位数序列cvdddntx) //增加整数x{Epy //若小根堆空{erx; //将x插入到return;}x>peek) //若x大于小根堆堆顶元erx; //将x插入到中eebgerx; //否则将x插入到大根堆bg中e<bge) //若小根堆元素个数较少erbgp; //取出bg的堆顶元素插入到中e>bge+) //若比bg至少多个元素bgerp; //取出的堆顶元素插入到bg中}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntcx;=nnexIn;he>){heEpyp;//初始化hebgEpybgp;ncer;c=nnexIn;=nnexIn;rnt=;i<=;++){x=nnexIn;add(x); //增加整数x%==) //x为奇数序号的整数nddpeek;//将求出的中位数添加到n中}Syeuprn"%d%d\n"c+/;rnt=;<ne;++)//输出中位数序列{f>0&%==)Syeuprnn;Syeuprnnge+"";}Syeuprnn;}}}HDU11062000ms，空间限制：65536K。问题描述：：输入一行数字，如果我们把这行数字中的都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以这些头部的应该被忽略掉，除非这个整数就是由若干个组成的，这时这个整数就是）。你的任务是对这些分割得到的整数，依从小到大的顺序排序输出。输入格式：输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。输入数据保证分割得到的非负整数不会大于，输入数据不可能全由组成。输出格式：对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;pubccvdnSrng]rg){Scnnern=newScnnerSyen;Srngr;henhNex){r=nnexne;Srngp=rp"";//分拆数字字符串rntcn=;rnt=;i<pengh;++){fpequ""){ntx=InegerpreInp;cn++=x; //将非空串转换为整数添加到}}rryrcn; //对benr=rue;rnt=;i<cn;++) //输出结果{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}HDU1862—EXCEL10000ms，空间限制：32768K。问题描述：：Exce可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。答：prtvuScnner;prtvu*;csSud //学生元素类{ntn; //学号Srngne; //姓ntgrde; //成绩pubcSudntnSrngnentgrde) //构造方法{hn=n;hne=ne;hgrde=grde;}pubcvddp //输出一个学生元素{nt=InegerSrngnengh;rnt=;>;)Syeuprn;Syeuprnnn+""+ne+""+grde;}}pubccsn{cnlntN=;cSud];pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntncc=;henhNex){n=nnexIn;fn==)brek;Stud[]a=newStud[n];c=nnexIn;rnt=;i<n;++){ntn=nnexIn;Srngne=nnex;ntgrde=nnexIn;=newSudnnegrde;}fc==)rryrnnewCprr<Sud>){pubcntcpreSudSud)//按学号递增排序{reurnnn;}});eefc==)rryrnnewCprr<Sud>){pubcntcpreSudSud){fnecprene==)//姓名相同reurnnn; //按按学号递增排序ee //否则按姓名非递减排序reurnnecprene;}});ee //c==的情况rryrnnewCprr<Sud>{pubcntcpreSudSud)//按成绩的非递减排序{fgrde==grde) //成绩相同reurnnn; //按按学号递增排序ee //否则按成绩的非递减排序reurngrdegrde;}});Syeuprnn"Ce"+c+":"; //rnt=;i<n;++)dp;c++;}}}H—按绝对值排序问题时间限制：，空间限制：。问题描述：：输入n（n≤100）个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。输入格式：输入数据有多组，每组占一行，每行的第一个数字为n，接着是n个整数，n=0表示输入数据的结束，不做处理。输出格式：对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;cntrnntnt)//按表首元素为基准进行划分{nt==;ntbe=; //以表首元素为基准he=) //从表两端交替向中间遍历直至=为止{he>i&hb)<=hbbe); //从后向前遍历找一个小于基准的]f>){=; //前移覆盖]++;}hei=hbbe)++; //从前向后遍历找一个大于基准的]if(i{=; //后移覆盖]j--;}}=be; //基准归位returni; //返回归位的位置}cvdQuckSrntnt)//对的元素进行快速排序(s{nt=rn;QuckSr; //对左子表递归排序QuckSr+; //对右子表递归排序}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;henhNex){n=nnexIn;fn==)brek;rnt=;i=nnexIn;QuckSrn;benr=rue;rnt=;i{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]=newnN;cntrnntnt)//按表首元素为基准进行划分{nt==;ntbe=; //以表首元素为基准he=) //从表两端交替向中间遍历直至=为止{he>i&hb)<=hbbe); //从后向前遍历找一个小于基准的]f>){=; //前移覆盖]++;}hei=hbbe)++; //从前向后遍历找一个大于基准的]if(i{=; //后移覆盖]j--;}}=be; //基准归位returni; //返回归位的位置}cvdQuckSrntnt)//对的元素进行快速排序(s{nt=rn;QuckSr; //对左子表递归排序QuckSr+; //对右子表递归排序}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;henhNex){n=nnexIn;fn==)brek;rnt=;i=nnexIn;QuckSrn;benr=rue;rnt=;i{if(first){Syeuprn;r=e;}eeSyeuprn""+;}Syeuprnn;}}}7.求平均数问题。在演讲比赛中，当参赛者完成演讲时评委将对他的表演进行评分。工作人员删除最高分和最低分，并计算其余的平均分作为参赛者的最终成绩。这是一个容易出问题的问题，因为通常只有几名评委。考虑上面问题的一般形式，给定n个正整数，删除最大的n1个和最小的n2个，并计算其余的平均值。答：publicvoidaverageNumber(){ Scannerfin=newScanner(System.in); intn1,n2,n; while(fin.hasNext()){ n1=fin.nextInt(); n2=fin.nextInt(); n=fin.nextInt(); if(n1==0&&n2==0&&n==0)break; PriorityQueue<Long>small=newPriorityQueue<Long>();//小根堆 PriorityQueue<Long>big=newPriorityQueue<Long>(11,newComparator<Long>(){ @Override publicintcompare(Longo1,Longo2){ //大根堆 return(int)(o2-o1); } }); longsum=0,a; intsmallcnt=0,bigcnt=0; for(inti=1;i<=n;i++){ a=fin.nextLong(); sum+=a; if(smallcnt<n1){ smallcnt++; small.offer(a); } elseif(a>small.peek()){ small.poll(); small.offer(a); } if(bigcnt<n2){ bigcnt++; big.offer(a); } elseif(a<big.peek()){ big.poll(); big.offer(a); } } while(!big.isEmpty()){ longx=big.poll(); sum-=x; } while(!small.isEmpty()){ longx=small.poll(); sum-=x; } System.out.printf("%.6f\n",(sum*1.0)/(n-n1-n2)); } }三、简答题简述何时使用稳定的排序算法。 答：如果排序数据存在相同关键字的元素，而且要求排序后不改变这些相同关键字记录的相对位置，此时需要使用稳定的排序算法。如张三的成绩是82，李四成绩也是82，而张三的记录在李四的记录的前面，要求按成绩递减排序，排好序后，张三的记录仍在李四的记录的前面，这就需要使用稳定的排序算法。另一个用途是多关键字排序，如学生记录有姓名、数学、语文成绩和总分，要求这样排名次，先按总分，总分相同再按数学成绩。可以这样排序，先采用任一种排序方法按数学成绩递减排序，再选择一种稳定的排序方法按总分排序，后者一定用稳定的排序方法，否则会出现总分相同，数学成绩低的排到前面了。排序方法的稳定性受什么因素影响？ 答：在排序过程中，需要以一个较大的间隔互换元素，或把元素隔空搬运一段较大距离时，排序方法一定不稳定，它可能会把原先排在前面的元素搬到具有相同关键字值的另一个元素的后面，改变了相对位置。证明：对于一个长度为n的线性表基于比较方法进行排序，至少需要进行ngn次比较。 答：证明：对于一个长度为n的线性表基于比较方法进行排序，元素两两比较构成的判定树可以近似看成是一棵满二叉树，其中叶子结点是某种排序结果，由于n个元素总共有n!种不同的排列，所以叶子结点个数为n!，一次排序恰好经过从根结点到某个叶子结点的路径，比较次数为树的高度，而h=gn≈ngn，所以至少需要进行ngn次比较。给出关键字序列采用直接插入排序时各趟的结果。答：直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时，时间复杂度各是多少？ 答：含有n个元素的初始数据正序时，直接插入排序算法的时间复杂度为On。含有n个元素的初始数据反序时，直接插入排序算法的时间复杂度为On含有n个元素的初始数据全部相等时，直接插入排序算法的时间复杂度为On。已知序列，采用二路归并排序法对该序列作升序排序时的每一趟的结果。 答：.两个各含有n个元素的有序序列归并成一个有序序列时，关键字比较次数为n～2n-1，也就是说关键字比较次数与初始序列有关。为什么通常说二路归并排序与初始序列无关呢？答：二路归并排序中使用了辅助空间，需要先将所有归并数据移到中，然后再复制到中，所以每一趟移动元素的次数n，共需gn趟排序，总的移动次数总是Ongn并排序与初始序列无关。二路归并排序中每一趟排序都要开辟On的辅助空间，共需gn趟排序，为什么总的辅助空间仍为On？ 答：二路归并排序中每一趟排序都要开辟On的辅助空间，但在一趟排序结束后，这些辅助空间都被释放了，所以总的辅助空间仍为On.在堆排序、快速排序和归并排序中：（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？（3）若只从最坏情况下的排序时间考虑，则不应选取哪种排序方法？答：若只从存储空间考虑，则应首先选取堆排序（空间复杂度为O），其次选取快速排序（空间复杂度为Ogn），最后选取归并排序（空间复杂度为On）。若只从排序结果的稳定性考虑，则应选取归并排序。因为归并排序是稳定的，其他两种排序方法是不稳定的。若只从最坏情况下的排序时间考虑，则不应选取快速排序方法。因为快速排序方法最坏情况下的时间复杂度为On，其他两种排序方法在最坏情况下的时间复杂度为O(nlog2n)。以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。 答：内排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。因为归并的趟数s=logkm，其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。实际应用中通过败者树进行k（k≥3）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。给出关键字序列按低位到高位进行基数排序时每一趟的结果。 答：给出关键字序列按高位到低位进行基数排序时每一趟的结果。 答：排序结果如图所示，从中看到，最终的排序结果是错误的，所以对于数值数据排序时只能是按低位到高位进行基数排序。.有n个不同的英文单词（均为小写字母），它们的长度相等，均为m。若n=50，m<5，试问采用什么排序方法时其时间复杂度最小？为什么？答：采用基数排序方法最好，这里r=，其时间复杂度为On+，其他排序方法的时间复杂度最小为Ongn，当n=，<5时，n+<ngn，所以基数排序方法最好。问在一般情况下，直接插入排序、简单选择排序和冒泡排序的过程中，所需元素交换次数最少的是哪种排序方法？ 答：对于直接插入排序，有序区分别有、、…、n个元素，平均交换一半的元素，所以平均元素交换次数rd/ebeddng/eObecbn>++…n≈n/。对于简单选择排序，最多只进行n-1次元素交换对于冒泡排序，平均每趟交换一半的元素，平均排序n/趟，所以平均元素交换次数=<Obec:rd/ebeddng/eObecbn>n-+n+…n/+≈n/。所以元素交换次数最少的是简单选择排序。.在下列情况下，选择哪种内排序算法比较合适？说明理由。（1）需要对1000个大型记录进行排序，记录本身存储在外存中，在内存中只保研了所有记录的关键字。关键字之间的比较非常快，但移动代价很大，因为一旦移动一个关键字，相应的外存中的记录也要移动，这将涉及很多磁盘块的移动。（2）已知一个包含了5000个单词的列表已按字母顺序排好序，需要再进行一次检查，确保所有的单词已经排好序。（3）需要将500张随机排列的图书卡片按照字母顺序排序。答：选择简单选择排序，该排序方法可以达到尽量少地移动记录，虽然比较次数达到On，但是相对外存的处理时间来说，不是关键因素。因为整个表已经基本有序，所以应该采用直接插入排序。因为是随机排列的卡片，所以选择快速排序比较合适。四、填空题如果一组数据采用某种排序方法进行排序，排序后相同关键字的元素的相对位置不发生改变，称该排序方法是。 答：稳定的若不考虑基数排序，在排序过程中，主要进行的两种基本操作是关键字的。和记录的。 答：比较;移动每次从无序子表中取出一个元素，通过依次比较把它插入到有序子表的适当位置，此种排序方法称为。 答：直接插入排序对含有n个元素的数据序列进行直接插入排序（采用《教程》中的算法），在最好情况下移动元素的个数是，关键字比较的次数是。答：2(n-1);n-1对含有n个元素的数据序列进行直接插入排序（采用《教程》中的算法），在最坏情况下移动元素的个数是，关键字比较的次数是。答：nn+/;nn/2数据序列采用二路归并排序方法进行递增排序，经过两趟排序后的结果是。答：}数据序列采用二路归并排序方法进行递增排序，所需要关键字比较次数是。答：12.数据序列中有 个元素，采用二路归并排序方法进行递增排序，最好情况下所需要关键字比较次数是。答：在快速排序、堆排序、归并排序中，排序是稳定的。答：归并排序二路归并排序算法的空间复杂度是。答：On)题：基数排序主要适用于排序的情况。答：多关键字题：基数排序与其他几种排序方法的区别是。答：基数排序采用分配和收集实现，不需要进行关键字的比较，而其他几种排序方法都是通过关键字的比较实现的题：对数据序列采用最低位优先的基数排序，第一趟排序后的结果是。答：}题：对数据序列采用最低位优先的基数排序，第趟排序后的结果是。答：}题：基数排序的空间复杂度是。答：Or（r为排序的基数）五、判断题一组数据序列为………，与的关键字相同，采用某种排序方法排序后变为………，则该排序算法是稳定的。答：错误2.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响算法时间复杂度的主要因素。 答：错误内排序方法要求数据一定以顺序表方式存储。 答：错误所有内排序算法中的比较次数与初始元素序列的排列无关。 答：错误排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 答：错误二路归并排序算法是稳定的。 答：正确对于不同的初始数据序列，二路归并排序算法中关键字比较次数有所不同。 答：正确二路归并排序算法的时间复杂度与初始数据序列的顺序无关。 答：正确二路归并排序算法的最好时间复杂度为On。 答：错误n个元素采用二路归并排序算法，总的趟数为n。 答：错误基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。 答：错误基数排序与初始数据的次序无关。 答：正确基数排序与初始数据中关键字的大小无关。 答：错误快速排序、简单选择排序和堆排序都与初始序列次序无关。 答：错误直接插入排序、冒泡排序和简单选择排序在最好情况下的时间复杂度均为On。 答：错误第9章排序习题参考答案 一、单选题.对一组数据进行排序，若前三趟的结果如下：第一趟：8第二趟：8第三趟：8则采用的排序方法可能是(。AABCD希尔排序归并排序基数排序

ABABCD简单选择排序冒泡排序堆排序直接插入排序.对数据排序，数据的排列次序在排序过程中的变化如图所示，则采用的排序方法是（）。AABCD简单选择排序快速排序冒泡排序直接插入排序.假设排序过程中顺序表的变化情况如下：21，25，49，25，16，8（初始状态）8，25，49，25，16，218，16，49，25，25，218，16，21，25，25，498，16，21，25，25，498，16，21，25，25，49（最终状态）可以断定，所采用的排序方法是（）排序。AABCD冒泡二路归并简单选择ABCABCD直接插入和快速冒泡和快速简单选择和直接插入简单选择和冒泡ABCABCD直接插入排序冒泡排序简单选择排序都一样ABCABCD内排序速度快，而外排序速度慢内排序不涉及内、外存数据交换，而外排序涉及内、外存数据交换内排序所需内存小，而外排序所需内存大内排序的数据量小，而外排序的数据量大ABCABCD外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花时间完全由采用的内排序确定外排序所花时间=内排序时间+外存信息读写时间+内部归并所花时间外排序并不涉及文件的读写操作外排序完全可以由内排序来替代ABCABCD减少初始归前段的段数便于实现败者树减少归并趟数以上都对ABCABCDgkmgk+1gk+)gkABCABCD3456ABCDk个结点的败者树中选取最小的关键字，则所需时间为ABCDOgk)O)Ok)以上都不对ABm个初始归并段采用k路平衡归并时，构建的败者树中共有 （）个结点（不含冠军结点）。AB2k-1.2kCDC.CD.1ABCDABCDgk1gkgk+1gkm题9：m个初始归并段中总共有u个记录，采用k路平衡归并，在k个记录中选取最小关键字的记录时采用逐个比较的方式进行，则总的关键字比较次数是（）。AABCD.guk)guk/gkgu)gk)始归并段中总共有u个记录，采用k路平衡归并，在k个记录中选取最小关键字的记录时采用败者树进行，则总的关键字比较次数是 （）（用时间复杂度表示）。AABCD.guk)guk/gkgu)gk)ABCABCD成正比成反比无关以上都不对题12：如将一个由置换-选择排序得到的输出文件F1（含所有初始归并段）作为输入文件再次进行置换-选择排序，得到输出文件F2（含所有初始归并段），问F1和F2的差异是（）。AABCDF2归并段个数减少F2中归并段的最大长度增大F2和F1无差异归并段个数及各归并段长度均不变，但F2中可能存在与F1不同的归并段ABCD题13：n个记录采用置换ABCDm与n成正比m与n成反比=gn以上都不对ABCD题：当内存工作区可容纳的记录个数=时，记录序列采用置换ABCD1235题：当内存工作区可容纳的记录个数=时，记录序列采用置换选择算法产生（）有序段。 AABCD235ABCABCD.，，}.，，}C.，，}.，，}ABCD题：对于个初始归并段，构建k路最佳归并树时，设u=)%k，当u≠ABCDuk-uk-1-uu-1ABCABCDk阶平衡树平衡二叉树k阶哈夫曼树以上都不对ABCABCD./k./kC./k).ABCABCDk/k.k/k)C.k/k).AB题21：对于磁带文件的k路平衡归并最好使用（）台磁带机。ABCD1.CDC.k.k1AB题22：对于磁带文件的k路多阶段归并需要使用（）台磁带机。ABCD1.CDC.k.k1二、填空题对含有n个元素的数据序列进行冒泡排序，其中关键字比较最多的次数是。 答：n(n-1)/2对含有n个元素的数据序列进行冒泡排序，其中关键字比较最少的次数是。 答：n-1冒泡排序算法在最好情况下的时间复杂度是。 答：On)冒泡排序算法的平均时间复杂度是。 答：.对数据序列采用冒泡排序方法进行递增排序，每趟通过交换归位关键字最小的元素，经过一趟后的排序结果是。答：}简单选择排序的最好、最坏和平均时间复杂度分别为 、、。 答：On;On;On)在直接插入排序、冒泡排序和简单选择排序这三种简单排序方法中，是不稳定的。 答：简单选择排序数据序列采用简单选择排序进行递增排序，每趟挑选最小元素，经过趟排序后结果是。 答：}对含有n个元素的数据序列进行简单选择排序，总的关键字比较次数是。 答：n(n-1)/2对含有n个元素的数据序列进行简单选择排序，最好情况下元素移动的次数是。 答：0磁盘是一种设备，磁带是一种设备， 答：直接存取;顺序存取外排序有两个基本阶段，第一阶段是，第二阶段是。 答：生成初始归并段;对这些归并段采用某种归并方法，进行多遍归并外排序的基本方法是归并排序，但在之前必须先生成。 答：初始归并段外排序有两个基本阶段，置换-选择排序算法用于。 答：外排序的第一个阶段置换-选择排序算法的作用是。 答：由一个无序文件产生若干个有序子文件n个记录采用置换-选择排序，假设内存工作区可容纳的记录个数为w（n远大于w），则除最后一个初始归并段外，其他每个初始归并段的长度至少是。答：wn个记录采用置换-选择排序，假设内存工作区可容纳的记录个数为w（n远大于w），产生的初始归并段的最大长度是。 答：n一组关键字=，设内存工作区可容纳个记录，记采用置换选择排序，则产生个初始归并段。答：2一组关键字=，设内存工作区可容纳个记录，记采用置换选择排序，则产生的初始归并段为。答：，}m个初始归并段采用k路平衡归并，归并的趟数是。 答：在败者树中，“败者”是指。 答：在一次比较中，没有上升进入双亲结点的结点采用k路归并构建的败者树中，不计冠军结点，败者树的结点总数是。 答：2k-1对于n个记录采用逐个比较方式选取最小记录，总的比较次数是。对于含有n个结点（不含冠军结点）败者树，从中选取最小记录，最多的比较次数是。答：n;gn)有8个长度为2、5、3、10、4、7、9、18的初始归并段，采用3路归并，在其最佳归并树中需增加个虚段。 答：1有8个长度为2、5、3、10、4、7、9、18的初始归并段，采用3路归并，在其最佳归并树中WPL=。 答：103三、判断题冒泡排序在最好情况下的时间复杂度也是On。 答：错误采用冒泡排序进行递增排序时，关键字较小的元素总是向前移动，关键字较大的元素总是向后移动。 答：错误对n个元素进行冒泡排序，只有在初始元素反序时，冒泡排序移动元素的次数才会达到最大值。 答：正确冒泡排序在最好情况下元素移动的次数为。 答：正确冒泡排序中，关键字比较的次数与初始数据序列有关，而元素移动的次数与初始数据序列无关。 答：错误简单选择排序在初始数据正序时，其时间复杂度为On。 答：错误简单选择排序中，每趟产生的有序区中所有元素在以后的排序中不再改变位置。 答：正确简单选择排序是一种不稳定的排序方法。 答：正确n个元素采用简单选择排序进行排序，关键字比较的次数总是nn/。 答：正确从时间性能看，堆排序总是优于简单选择排序。 答：正确外排序与外部设备的特性无关。 答：错误内排序过程在数据量很大时就变成了外排序过程。 答：错误影响外排序的时间因素主要是内存与外存交换信息的次数。 答：正确外排序是把外存文件调入内存，可利用内排序方法进行排序，因此排序所花时间取决于内排序的时间。 答：错误外排序中没有关键字比较。 答：错误在外排序过程中所有记录的I/O次数必定相等。答：错误在外排序过程中，一个记录的读入内存的次数和写到外存的次数必定相等。 答：正确为了提高外排序的速度，在外排序中必须选用最快的内排序算法。 答：错误通常外排序采用多路归并排序方法，实际上也可以用其他内排序方法代替归并排序方法。 答：错误.设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并，若不采用败者树，使用逐个比较的方法选取最小记录，则总共需要396次关键字比较。答：正确设有个初始归并段，每个归并段有个记录，采用路平衡归并，若采用败者树选取最小记录，则总共需要次关键字比较。答：错误减少初始归并段的个数，可以使外排序的时间缩短。 答：正确外排序的k路平衡归并中，采用败者树时，归并效率与k无关。 答：错误采用多路平衡归并方法可以减少初始归并段的个数。 答：错误.磁盘上存放375000个记录，做5路平衡归并排序，内存工作区能容纳600个记录，内排序采用直接插入排序。为把所有记录排好序，需做6趟归并排序。答：错误k路平衡归并中，败者树的主要作用是减少归并的趟数。 答：错误k路平衡归并建立的败者树中没有度为的结点。 答：正确k路平衡归并建立的败者树的结点个数正好为k（不含冠军结点）。 答：错误置换选择排序算法的作用是由一个无序文件生成一个全部有序的文件。 答：错误置换选择排序算法的作用是由一个无序文件生成若干个有序的子文件。 答：正确n个记录采用置换选择排序算法，什么情况下产生的初始归并段的个数不可能为n。 答：错误k路最佳归并树在外排序中的作用是完成k路归并排序。 答：错误k路最佳归并树在外排序中的作用是设计k路归并排序的优化方案。 答：正确34.k路最佳归并树一定是一棵k路平衡树。 答：错误四、简答题已知序列，给出采用冒泡排序方法对该序列做升序排序时的过程。 答：冒泡排序在什么情况下需要进行的关键字比较次数最多，最多关键字比较次数是多少？ 答：冒泡排序在初始数据反序时需要进行的关键字比较次数最多，此时关键字比较次数=n+n+…+=nn/。冒泡排序在什么情况下需要进行的元素移动次数最少，最少元素移动次数是多少？ 答：冒泡排序在初始数据正序时需要移动的元素次数最小，此时移动的元素次数为0。在冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，请举例说明之。快速排序过程中有没有这种现象出现？答：在冒泡排序，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，例如，以下冒泡排序过程中关键字38便是如此：49，38，13，27，97（初始关键字）38，13，27，49，97（第1趟排序）13，27，38，49，97（第2趟排序）但在快速排序中不会出现这种情况。因为在每趟排序中，比基准元素大的都交换到其右边，而基准元素小的则交换到其左边。已知序列，给出采用快速排序方法对该序列做升序排序时的过程。 答：给出数据序列采用简单选择排序进行递增排序时各趟的结果。并指出简单选择排序的缺陷。 答：排序过程如下：=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9=：，，，，，，，，9从中看出，当=这一趟排序结束后，数据已有序，但简单选择排序仍要完成余下的各趟排序，也就是说简单选择排序没有中途退出机制。简述简单选择排序的时间性能。答：简单选择排序的主要时间花在关键字比较上，无论初始数据序列如何排列，所需关键字比较次数均为n(n-1)/2，所以简单选择排序算法的时间复杂度总是On，与初始数据序列如何排列无关。.一个有n个整数的数组n说明理由。答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k、k、…、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素k，有k<k，k<k+（<n/），这正好满足小根堆的特性，所以构成一个小根堆。已知关键字序列为，采用堆排序法对该序列进行递增排序，给出整个排序过程。 答：该序列对应的完全二叉树如图（）所示，调整成初始堆如图（b）所示，用堆排序方法排序的各趟过程如图（c）～（）所示，排序结果为。.请回答下列关于堆排序中堆的一些问题：（1）堆的存储表示是顺序还是链式的？（2）设有一个小根堆，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其中具有最大关键字的结点可能在什么地方？答：通常堆的存储表示是顺序的。因为堆排序将待排序序列看成是一棵完全二叉树，然后将其调整成一个堆。而完全二叉树特别适合于采用顺序存储结构，所以堆的存储表示采用顺序方式最合适。小根堆中具有最大关键字的结点只可能出现在叶子结点中。因为最小堆的最小关键字的结点必是根结点，而最大关键字的结点由偏序关系可知，只有叶子结点可能是最大关键字的结点。简述外排序的过程。 答：外排序过程主要分为两个阶段：生成初始归并段和对初始归并段进行归并。生成初始归并段可以采用某种内排序实现。假设内存大小为（内存中每次最多可放入个记录），要进行外排序的文件为nd序文件out.dat的过程如下：①可以每次从外存文件nd中读入个记录，采用某种内排序方法（如置换选择算法）进行排序来产生初始归并段，即产生ud、…、und有序文件，如图（）所示。②采用多路归并方法将所有初始归并段（ud、…、und文件）进行归并产生一个有序文件ud，如图（b）所示。什么是多路平衡归并，多路平衡归并的目的是什么？ 答：归并过程可以用一棵归并树来表示。多路平衡归并对应的归并树中，每个结点都是平衡的，即每个结点的所有子树的高度相差不超过1。k路平衡归并的过程是：第一趟归并将个初始归并段归并为/k个归并段，以后每一趟归并将个初始归并段归并为/k成一个大的归并段为止。个归并段采用k路平衡归并，其归并趟数=gk，其趟数是所有归并方案中最少的，所以多路平衡归并的目的是减少归并趟数。外排序中何采用k（k>）路归并而不用二路归并？这种技术用于内排序有意义吗？为什么？答：外排序中采用k（k>2）路归并，是因为k越小，归并趟数越多，读写外存次数越多，时间效率越低，所以一般应大于最少的二路归并。若将k路归并的败者树思想用于内排序，因其由胜者树改进而来，且需要辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高第9章排序习题参考答案 一、简答题什么是败者树？其主要作用是什么？用于k路归并的败者树中共有多少个结点（不含冠军结点）？ 答：败者树是一棵有k个叶子结点的完全二叉树，从叶子结点开始，两个结点进行比较，将它们中的败者（较大者）上升到双亲结点，胜者（较小者）参加更高一层的比较。败者树的主要作用是从k个记录中选取关键字最小的记录。败者树中有k个叶子结点，且没有度为的结点，即n=k，n=，n=n=k，所以n=n+n+n=k。使用败者树后，多路平衡归并的关键字比较次数与路数k无关了，因此只要内存空间允许，k越大越好，这个叙述正确吗？ 答：虽然增大k会有效地减少归并树的高度，从而减少I/O的次数，提高外排序的速度。但并不是k越大越好，因为k冲区个数。如果可供使用的内存空间不变，这样会减少每个输入缓冲区的容量，使得内、外存数据交换的次数增大，所以说当k值过大时，虽然归并趟数会减少，但读写外存的次数仍会增加。以归并排序为例，说明内排序和外排序的不同，说明外排序如何提高操作效率？ 答：内排序中的归并排序是在内存中进行的归并排序，所有数据都要调入内存，所需辅助空间为On文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外排序的效率主要取决于读写外存的次数，个初始子文件采用k路平衡归并时，其归并趟数=gk，越大读写外存的次数也越大，增大和减少m都可以减少s，从而提高外排序的效率。.w（w>1），若输入的n（n>w）个关键字为递减次序，则算法的输出是什么？答：若输入的关键字为递减次序，算法输出为：最后一个初始归并段的长度小于或等于m，其他各初始归并段的长度为m，全部归并段的个数为n/。.w（w>1），若输入的n（n>w）个关键字为递增次序，则算法的输出是什么？答：若输入的关键字为递增次序，算法输出为：只有一个初始归并段，其长度恰好为n。采用置换-选择算法产生初始归并段时，如果内存缓冲区的长度为w（w>1），则产生的初始归并段的最大长度和最短长度分别是多少？答：当输入文件递增有序时，仅产生一个初始归并段，其长度为n。除了最后产生仅含一个记录的初始归并段外，其他情况最短为w。给出一组关键字=，设内存工作区可容纳个记录，写出用置换选择方法得到的全部初始归并段。答：置换选择方法得到的结果如下：归并段：。归并段：。.在一个无序文件中存放有若干个记录，其中所有记录构成的关键字序列为。设缓冲区能有容纳个记录的容量。按置换选择方法求初始归并段。请写出各初始归并段中选出的关键字。答：置换选择方法得到的结果如下：归并段：，关键字为。归并段：，关键字为。归并段，，关键字为。.给出一组关键字=，采用置换选择方法得到的全部初始归并段。回答以下问题：（）若内存工作区容量=，给出相应的结果。（2）若内存工作区容量w=2，给出相应的结果。（3）若内存工作区容量w=5，给出相应的结果。（4）若内存工作区容量w=8，给出相应的结果。答：（1）w=1时共产生10个初始归并段，即为{10}、{9}、{8}、{7}、{6}、{5}、{4}、{3}、{2}、{1}。（）=时共产生个初始归并段，即为、、、、。（）=时共产生个初始归并段，即为、。（）=时共产生个初始归并段，即为、。外排序中的败者树和堆有什么区别？若用败者树求k个数中的最小值，在某次比较中得到>b，那么谁是败者？ 答：外排序中的“败者树”和堆的区别如下：败者树是在双亲结点中记下刚进行比较的败者（较大者），让胜者（较小者）去参加更高一层的比较。而堆可看作是一种“胜者树”，即双亲结点表示其左、右孩子中的胜者。败者树中参加比较