算法与数据结构习题

《算法与数据结构》习题1一、单项选择题1.数据结构从逻辑上分为（）。A．动态结构和静态结构B．内部结构和外部结构C．紧凑结构和非紧凑结构D．线性结构和非线性结构2.栈和队列的共同点是（）。A．都是先进后出B．都是后进先出C．只允许在端点处插入和删除元素D．没有共同点3．若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（）A．decfbga B．fegdacbC．efdgbca D．dcbefag4.在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。A．s→link=p→link；p→link=s；B．p→link=s；s→link=q；C．p→link=s→link；s→link=p；D．q→link=s；s→link=p；5．算法的计算量的大小称为计算的（）。A．效率 B.复杂性 C.现实性 D.难度6.一个算法应该是（）。A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C7.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8.以下数据结构中，哪一个是线性结构？（）A．广义表 B.二叉树 C.稀疏矩阵 D.串二、多项选择题1.以下说法正确的是（）。A.二叉树的特点是每个结点至多只有两棵子树

B.二叉树的子树无左右之分C.二叉树只能进行链式存储

D.树的结点包含一个数据元素及若干指向其子树的分支2．在数组上能做的操作有（）。A.

插入 B.

删除

C.

取值操作 D.

赋值操作3.图的应用算法有（）。A.克鲁斯卡尔算法 B.哈弗曼算法

C.迪杰斯特拉算法 D.拓扑排序算法4.计算机算法必须具备（）等特性。A.可行性、确定性 B.可行性、可移植性

C.输入、输出 D.有穷性

E.易读性 F.稳定性三、填空题1.一个算法的效率可分为效率和效率。2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。3.栈只能在插入和删除元素；对于队列只能在插入和删除元素。4.一棵具有257个结点的完全二叉树，它的深度为。四、判断题1.链表的每个结点中都恰好包含一个指针。（）2.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）3.数和二叉树都是分支结构。（）4.优先队列是一种给每个元素增加了优先级的队列，它具有队列的基本特性。（）5.数据元素是数据的最小单位。（）6.记录是数据处理的最小单位。（）7.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）五、简答题1.能否讲二叉树是一种特殊的树？为什么？2.在C语言中字符串可以用字符指针来表示。字符串的长度隐含在字符指针所指的字符数组中，通过特殊的字符‘\0\’判定。写一个递归算法，以字符指针为参数，在屏幕上打印出它反转后得到的字符串。3.算法与程序有什么区别？4.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。5.什么是网络的最小生成树？6.已知两个串为S1=“bccadcabcadf”,S2=”abc”,试求两个串的长度，并判断S2串是否是S1串的子串；如果是，请指出S2在S1中的位置。

《算法与数据结构》习题1答案一、单项选择题题号12345678答案DCABBBCD二、多项选择题题号1234答案ADCDACDACD三、填空题题号答案1时间；空间2n-i+13栈顶；队尾；队首49四、判断题题号1234567答案××√××××五、简答题1.答：不能。二叉树并不是树的特例。树和二叉树的定义及操作都是不同的，周游算法也有很大的区别。二叉树可以与一般树林建立对应，它的提出可以为研究树提供一种简单而统一的范型。2.答：voidprintRevString(char*s){If(s[0]==‘\0\’)return;/*空串*/If(s[1]==‘\0\’)putchar(s[0]);/*只有一个字符，直接打印*/Else{PrintRevString（s+1）；Putchar（s[0]）;}}3.答：算法与程序的关系十分密切，但并不等同。一般来说，一个程序并不需要满足算法的有穷性等条件，例如操作系统的程序，只要整个系统不遭到破坏，操作系统程序就永不结束。另外，程序是用机器可执行的语言书写的，而算法通常并没有这种限制。4.答：DLR：ABDFJGKCEHILM LDR：BFJDGKACHELIM LRD：JFKGDBHLMIECA5.答：因为网络是带权的连通图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并把权值最小的生成树成为最小生成树。6.答:S1的长度为14，S2的长度为3;S2是S1的子串，起始位置是S1中第九个字符。第10章排序一、

基础知识题10.1基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树。【解答】⑴内排序和外排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。⑵稳定排序和不稳定排序假设待排序记录中有关键字Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。⑶顺串外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。⑷败者树败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。⑸最佳归并树在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用nk表示度为k的个数，若(m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。

10.2设待排序的关键字序列为(15，21，6，30，23，6′，20，17)，试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。 (1)直接插入排序 (2)希尔排序(增量为5，2，1)(3)起泡排序 (4)快速排序 (5)直接选择排序 (6)锦标赛排序 (7)堆排序 (8)二路归并排序 (9)基数排序【解答】(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，17666’1566’171521630236’2017

6’156’1530

6’171521∞

30236’2017

1515231530

23171521∞

3023∞

2017

锦标赛排序的基本思想是：首先对n个待排序记录的关键字进行两两比较，从中选出én/2ù个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。上面给出了排在前三个的记录，详细过程略。

(7)堆排序 初始关键字序列：15，21，6，30，23，6′，20，17初始堆：6，17，6’，21，23，15，20，30第一次调堆：6’，17，15，21，23，30，20，【6】第二次调堆：15，17，20，21，23，30，【6’，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】

(8)二路归并排序初始关键字序列：15，21，6，30，23，6′，20，17二路归并排序结果：15，17，20，21，23，30，6，6’final↑↑first

(9)基数排序初始关键字序列：p→15→21→6→30→23→6′→20→17第一次分配得到:B[0].f→30→20←B[0].eB[1].f→21←B[1].eB[3].f→23←B[3].eB[5].f→15←B[5].eB[6].f→6→6’←B[6].eB[7].f→17←B[7].e第一次收集得到:p→30→20→21→23→15→6→6’→17第二次分配得到B[0].f→6→6’←B[0].eB[1].f→15→17←B[1].eB[2].f→20→21→23←B[5].eB[3].f→30←B[3].e第二次收集得到p→6→6’→15→17→20→21→23→30基数排序结果：6，6′，15，17，20，21，23，30

10.3在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【解答】见下表：排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序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’,1希尔排序O(n1.3)O(n1.3)O(1)不稳定3,2,2’,1(d=2,d=1)快速排序O(nlog2n)O(n2)O(log2n)不稳定2,2’,1堆排序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)稳定

10.4在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？【解答】这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。10.5在堆排序、快速排序和归并排序方法中：(1)若只从存储空间考虑，则应首先选取哪种排序，其次选取哪种排序，最后选取哪种排序？(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？【解答】(1)堆排序，快速排序，归并排序(2)归并排序(3)快速排序(4)堆排序

10.6

设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最多。【解答】对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序时关键字交换的次数为最多。

10.7快速排序的最大递归深度是多少？最小递归深度是多少？【解答】设待排序记录的个数为n,则快速排序的最小递归深度为ëlog2nû+1,最大递归深度n。

10.8我们知道，对于n个元素组成的顺序表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：(1)当n=7时，在最好情况下需进行多少次比较？请说明理由。(2)当n=7时，给出一个最好情况的初始排序的实例。(3)当n=7时，在最坏情况下需进行多少次比较？请说明理由。(4)当n=7时，给出一个最坏情况的初始排序的实例。【解答】(1)在最好情况下,每次划分能得到两个长度相等的子文件。假设文件的长度n=2k-1,那么第一遍划分得到两个长度均为ën/2û的子文件,第二遍划分得到4个长度均为ën/4û的子文件,以此类推,总共进行k=log2(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件（长度均为3,k=2）进行排序,各需2次,共10次即可。(2)在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。(3)在最坏情况下,若每次用来划分的记录的关键字具有最大(或最小)值,那么只能得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n2)。所以当n=7时,最坏情况下的比较次数为21次。(4)在最坏情况下快速排序的初始序列实例：7,6,5,4,3,2,1,要求按递增排序。

10.9判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。(1)

100，90，80，60，85，75，20，25，10，70，65，50(2)

100，70，50，20，90，75，60，25，10，85，65，80【解答】(1)是堆(2)不是堆。调成大堆：100,90,80,25,85,75,60,20,10,70,65,50

10.10

在多关键字排序时，LSD和MSD两种方法的特点是什么？【解答】最高位优先（MSD）法：先对最高位关键字K0进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K0值,然后,分别就每个子序列对关键字K1进行排序,按K1值不同再分成若干更小的子序列,……,依次重复,直至最后对最低位关键字排序完成,将所有子序列依次连接在一起,成为一个有序子序列。最低位优先（LSD）法：先对最低位关键字Kd-1进行排序,然后对高一级关键字Kd-2进行排序,依次重复,直至对最高位关键字K0排序后便成为一个有序序列。进行排序时,不必分成子序列,对每个关键字都是整个序列参加排序,但对Ki(0<=i<d-1)排序时,只能用稳定的排序方法。另一方面,按LSD进行排序时,可以不通过关键字比较实现排序,而是通过若干次“分配”和“收集”来实现排序。

10.11

给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，列出一趟分配和收集的过程。【解答】按LSD法→321→156→57→46→28→7→331→33→34→63分配[0][1][2][3][4][5][6][7][8][9]3213334156572833163467收集→321→331→33→63→34→156→46→57→7→28

10.12

奇偶交换排序如下所述：对于初始序列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进行排序时，每一趟的结果。【解答】(1)

排序结束条件为没有交换为止(2)

第一趟奇数：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(无交换)结束

10.13

设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？【解答】设归并路数为k,归并趟数为s,则s=élogk100ù,因élogk100ù=3,且k为整数，故k=5,即最少5路归并可以完成排序。

10.14

证明：置换-选择排序法产生的初始归并段的长度至少为m。(m是所用缓冲区的长度)。【证明】由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时（即初始归并段）,缓冲区中m个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m个元素。证毕。

10.15

设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做4路平衡归并，要求：(1)指出总的归并趟数；(2)构造最佳归并树；(3)根据最佳归并树计算每一趟及总的读记录数。【解答】因为(11-1)%(4-1)=1,所以加“虚段”,第一次由两个段合并。25916404853257712824264388855698(1)三趟归并(2)最佳归并树如图(3)设每次读写一个记录第一趟50次读写总的读写次数：2052[(9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)]*2

10.16

对输入文件(101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90)，当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。【解答】257140313161119151110111初始败者树

初始归并段：R1:3,19,31,51,61,71,100,101R2:9,17,19,20,30,50,55,90R3:6

10.17

选择题：下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。A．选择排序法B.插入排序法C.快速排序法D.堆排序法【解答】A

10.18

选择题：一个排序算法的时间复杂度与以下哪项有关。A．排序算法的稳定性B.所需比较关键字的次数C.所采用的存诸结构D.所需辅助存诸空间的大小【解答】B

二、算法设计题10.19

请编写一个算法，在基于单链表表示的关键字序列上进行简单选择排序。voidLinkedListSelectSort(pointerhead);∥本算法一趟找出一个关键字最小的结点,其数据和当前结点进行交换;若要交换指针∥则须记下当前结点和最小结点的前驱指针{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;}

10.20

设单链表头结点指针为L，结点数据为整型。试写出对链表L按“直接插入方法”排序的算法。voidLinkInserSort(LinkedListL)//本算法对单链表L按“直接插入方法”进行排序{p=L->next->next;//链表至少一个结点,p初始指向链表中第二结点（若存在）L->next->next=null;//初始假定第一个记录有序while(p!=null){q=p->next;//q指向p的后继结点}s=L;while(s->next!=null&&s->next->data<p->data)s=s->next;//向后找插入位置p->next=s->next;s->next=p;//插入结点p=q;//恢复p指向当前结点}}

10.21

试设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。voidBubbleSort2(inta[],intn)∥相邻两趟向相反方向起泡的冒泡排序算法{change=1;low=0;high=n-1;∥冒泡的上下界while(low<high&&change){change=0;∥设不发生交换for(i=low;i<high;i++)∥气泡上浮,大元素下沉（向右）if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;}∥有交换,修改标志changehigh--;∥修改上界for(i=high;i>low;i--)∥气泡下沉,小元素上浮（向左）if(a[i]<a[i-1]){a[i]<-->a[i-1];change=1;}low++;∥修改下界}∥while}∥BubbleSort2

10.22

写出快速排序的非递归算法。voidQuickSort(rectyper[n+1];intn){∥对r[1..n]进行快速排序的非递归算法typedefstruct{intlow,high;}nodenodes[n+1]；∥栈,容量足够大intquickpass(rectyper[],int,int);∥函数声明inttop=1;s[top].low=1;s[top].high=n;while(top>0){ss=s[top].low;tt=s[top].high;top--;if(ss<tt){k=quickpass(r,ss,tt);if(k-ss>1){s[++top].low=ss;s[top].high=k-1;}if(tt-k>1){s[++top].low=k+1;s[top].high=tt;}}}∥算法结束intquickpass(rectyper[];ints,t){i=s;j=t;rp=r[i];x=r[i].key;while（i<j）{while(i<j&&x<=r[j].key)j--;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;}r[i]=rp;return(i);}∥一次划分算法结束[算法讨论]可对以上算法进行两点改进：一是在一次划分后,先处理较短部分,较长的子序列进栈；二是用“三者取中法”改善快速排序在最坏情况下的性能。下面是部分语句片段：inttop=1;s[top].low=1;s[top].high=n;ss=s[top].low;tt=s[top].high;top--;flag=true;while(flag||top>0){k=quickpass(r,ss,tt);if(k-ss>tt-k)∥一趟排序后分割成左右两部分{if(k-ss>1)∥左部子序列长度大于右部,左部进栈{s[++top].low=ss;s[top].high=k-1;}if(tt-k>1)ss=k+1;∥右部短的直接处理elseflag=false;∥右部处理完,需退栈}elseif(tt-k>1)∥右部子序列长度大于左部,右部进栈{s[++top].low=k+1;s[top].high=tt;}if(k-ss>1)tt=k-1∥左部短的直接处理elseflag=false∥左部处理完,需退栈}if(!flag&&top>0)∥退栈{ss=s[top].low;tt=s[top].high;top--;flag=true;}}∥endofwhile(flag||top>0)}∥算法结束intquickpass(rectyper[];ints,t)∥用“三者取中法”进行快速排序的一次划分{inti=s,j=t,mid=(s+t)/2;rectypetmp;if(r[i].key>r[mid].key){tmp=r[i];r[i]=r[mid];r[mid]=tmp}if(r[mid].key>r[j].key){tmp=r[j];r[j]=r[mid];if(tmp>r[i])r[mid]=tmp;else{r[mid]=r[i];r[i]=tmp}}{tmp=r[i];r[i]=r[mid];r[mid]=tmp}∥三者取中：最佳2次比较3次赋值；最差3次比较10次赋值rp=r[i];x=r[i].key;while（i<j）{while(i<j&&x<=r[j].key)j--;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;]r[i]=rp;return(i);}∥一次划分算法结束

10.23

假设由1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要求以尽可能少的比较次数和移动次数实现排序，并按你的设计编写算法。【题目分析】设关键字小于10000的整数的记录序列存于数组中，再设容量为10000的临时整数数组，按整数的大小直接放入下标为该整数的数组单元中，然后对该数组进行整理存回原容量为1000的数组中。voidintsort(intR[],intn){//关键字小于10000的1000个整数存于数组R中，本算法对整数进行排序intR1[10000]={0};//初始化为0for(i=0;i<1000;i++)R1[R[i]]=R[i];for(i=0,k=0;i<10000;i++)if(R1[i]!=0)R[k++]=R1[i];}

10.24

荷兰国旗问题：设有一个仅有红、白、蓝三种颜色的条块组成的条块序列。编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案【题目分析】设用整型数组R表示荷兰国旗,元素值1、2和3分别表示红、白和篮色。再设整型变量i,j和k,排序结束后R[1..i-1]表示红色,R[i..j-1]表示白色,R[j..n]表示篮色。voidDutchFlag(intR[],intn)∥对红、白、篮三种颜色的条块,经排序形成荷兰国旗{inti=1,j=1,k=n;∥指针初始化,j到k是待排序元素while(j<=k)if(r[j]==1)∥红色{r[i]<-->r[j];i++;j++;}elseif(r[j]==2)j++;∥白色else{r[j]<-->r[k];k--;}∥兰色}[算法讨论]象将元素值为正数、负数和零排序成前面都是负数,接着是零,最后是正数的排序,以及字母字符、数字字符和其它字符的排序等,都属于这类荷兰国旗问题。排序后,红、白和蓝色的元素个数分别为i-1,j-i,n-j+1。

10.25

已知记录序列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;while(i<n)//若c[i]+1=i，则r[i]正好是第i个元素;否则，需要调整{if(c[i]+1!=i){j=i;rc=r[i];while(c[j]+1