《数据结构题型分析复习资料.pdf》由会员分享，可在线阅读，更多相关《数据结构题型分析复习资料.pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构重点题型整理古月编辑-1-【题型【题型 1 1 1 1】时间复杂性分析时间复杂性分析例 1 分析下列程序段的时间复杂性。m91；n100；while(n0)if(m0)m=m-10;n=n-1;elsem=m+1;解本程序段是著名的 McCarthy 函数：对任何的 m100，91)(=mf，所以此程序段实质上是一个二重循环；对每个 n（n0）值，if 语句执行 11 次，其中 10 次是执行 m+语句，但它们与 n 无关；while 循环的执行次数取决于 n 的值大小，所以 T(n)=O(n)。例 2阅读下列算法：void suan_fa(int n)int i,j,k,s,x;fo
2、r(s=0,i=0;in;i+)for(j=i;jn;j+)s+;i=1;j=n;x=0;while(i+=mmmffmmf数据结构重点题型整理古月编辑-2-（3）在 for 循环语句中时间复杂度为2)1(+nn，在 while 循环语句中时间复杂度为2n，所以，算法时间复杂度为O(n2)。（4）s=15，x=4【题型【题型 2 2 2 2】数组存储地址分析数组存储地址分析例 1 数组 B1.10，-2.6，2.8以行为主序顺序存储；设基地址（第一个元素的地址）为100，每个元素的存储长度为 3；试求元素 B5，0，7的存储地址。解loc(Bi,j,k)=loc(Ba,b,c)+(i-a)*(
3、-2.6)*(2.8)+(j-b)*(2.8)+(k-c)*3loc(B5,0,7)=loc(B1,-2,2)+(5-1)*9*7+2*7+5*3=100+(36*7+19)*3=913例 2 设有上三角矩阵nnija)(，将其上三角元素逐行存于数组 B1.m中（m 充分大），使得ijakB=，且Cjfifk+=)()(21。试推导出函数1f和2f以及常数 C（要求1f和2f不含有常数项）。解由于要求将上三角矩阵 A 上的元素逐行存于数组 B 中。因此对于aij来说，若它在 B中的存储位置是k，则在它之前存放着 A 中第一行的n个元素，第二行的1n个元素，第1i行的2+in个元素，以及第i行的
4、1j个元素，由此可以得到k与nji,的关系如下：)1()32(*2/2)1(+=+=njinijinnnk）（,所以，);32(2/)(1iniif+=;)(2jif=)1(+=nC例 3三对角矩阵nnija)(是除主对角线以及与主对角线相邻的两条对角线以外的元素全为0，将其 3 条对角线上的元素逐行地存于数组 B1.3n-2中使得ijakB=，求：（1）用ji,表示k的下标变换公式。（2）用k表示ji,的下标变换公式。解（1）2221)1(3+=+=jiijik（2）3%3/;1 3/kkjki+=+=【题型【题型 3 3 3 3】表达式的表示表达式的表示例 1 已知表达式的中缀表示为（A+
5、B）*D+E/(F+A*D)+C，试利用栈把它改写成后缀表示，并写出转换过程中栈的变化。解AB+D*EFAD*+/+C+例 2 对于下面的中缀表达式，画出其二叉树表示（即标识符树），并写出其前缀形式和后缀形式。（1）-A+B-C+D（2）(A+B/C-D)*(E*(F+G)解中缀表达式所对应的二叉树如下所示：数据结构重点题型整理古月编辑-3-（1）根据中缀表达式画出的二叉树（1），其前缀形式为：ABCD+，后缀形式为+DCBA。（2）根据中缀表达式画出的二叉树（2），其前缀形式为：FGEBCDA+*/，后缀形式为+EFGDABC/。【题型【题型 4 4 4 4】栈的出栈序列栈的出栈序列例 1
6、设有一个栈，元素的进栈次序为 A、B、C、D、E，试问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因。（1）C、E、A、B、D（2）C、B、A、D、E（3）D、C、A、B、E（4）A、C、B、E、D（5）A、B、C、D、E（6）E、A、B、C、D解可以得到的出栈序列为（2）（4）（5）。原因如下：（2）A、B、C 依次进栈后依次出栈，即得出栈顺序为 C、B、A，然后 D 进栈后出栈，E进栈后出栈，最后的出栈序列为：C、B、A、D、E。（4）A 进栈后出栈，接着 B、C 依次进栈再依次出栈，最后 D、E 依次进栈后依次出栈，最后出栈序列为：A、C、B、E、D。（5）A 进栈后出栈，
7、B 进栈后出栈，C 进栈后出栈，D 进栈后出栈，E 进栈后出栈，最后出栈序列为：A、B、C、D、E。不能得到的出栈序列为：（1）、（3）、（6），因为栈遵守先进后出的原则，B 不可能在 A出栈之后才出栈。例 2 如下图所示，输入元素为（A，B，C），在栈的输出端得到一个输出序列 ABC，求出在栈的输入端所有可能的输入序列。输出端输入端栈ABC数据结构重点题型整理古月编辑-4-分析A，B，C 三个字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为 BCA 时，输出无法得到 ABC。因为输入序列为 BCA 时，要想先
8、输出 A，必须 BCA 均入栈，但这样只能得到序列 ACB。其余五种输入序列都可在输出端得到序列 ABC。解 ABC、ACB、BAC、CAB、CBA【题型【题型 5 5 5 5】队的出栈序列队的出栈序列例设有一顺序队列 sq，容量为 5，初始状态时 sqfront=sqrear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。（1）d，e，b 入队（2）d，e 出队（3）i，j 入队（4）b 出队（5）n，o，p 入队解队列及其头尾指针的状态变化情况如下图所示（a）初态（b）d，e，b 入队（c）d，e 出队（d）i，j 入队（e）b 出队第 5 步操作无法进行，
9、因队列已满。【题型【题型 6 6 6 6】二叉树的遍历二叉树的遍历例 1 对于如下图所示的两颗二叉树，分别写出（1）前序遍历序列（2）中序遍历序列（3）后序遍历序列（4）层次遍历序列解（1）前序遍历序列，图 A 为：ABDEHCFIG，图 B 为：ABDFCEG（2）中序遍历序列，图 A 为：DBHEAFICG，图 B 为：BFDAEGC（3）后序遍历序列，图 A 为：DHEBIFGCA，图 B 为：FDBGECASq.frontSq.rearbedSq.frontSq.rearbSq.frontSq.rearjbiSq.frontSq.rearjiSq.frontSq.rear数据结构重点题
10、型整理古月编辑-5-（4）层序遍历序列，图 A 为：ABCDEFGHI，图 B 为：ABCDEFG例 2 已知一棵二叉树的前序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK。请画出该二叉树，并写出它的后序序列和层次序列。解二叉树如图所示：恢复的二叉树的后序序列为：ACDBGJKIHFE恢复的二叉树的层次序列为：EBFADHCGIKJ【题型【题型 7 7 7 7】树的结点数目的计算树的结点数目的计算例 1 已知一棵树边的集合为（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k，（c，g），（c，f），（h，l），（c，h），（a，c）
11、，请画出这棵树并回答如下问题。（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点 g 的双亲？（4）哪些是结点 g 的祖先？（5）哪些是结点 g 的孩子？（6）哪些是结点 e 的子孙？（7）哪些是结点 e 的兄弟？哪些是结点 f 的兄弟？（8）结点 b 和结点 n 的层次号分别是多少？（9）树的深度是多少？树的度是多少？（10）以结点 c 的根的子树的深度是多少？解由边的集合表示可得此树的形状如右图所示。（1）根结点是a。（2）叶子结点有的 d，m，n，f，j，k，l。（3）结点 g 的双亲是c。（4）结点 g 的祖先为结点a，c。（5）结点 g 的孩子结点为结点 j，k。数据结构重点
12、题型整理古月编辑-6-（6）结点 e 的子孙为结点 i，m，n。（7）结点 e 的兄弟为结点 d；结点 f 的兄弟为结点 g，h。（8）结点 b 的层次号为 2；结点 n 的层次号为 5。（9）树的深度为 5；度为 3。（10）以结点 c 为根的子树的深度是 3。例 2 一棵深度为n的满k叉树是怎样的一棵树，它的第h层上的结点全部是叶子结点，其余各层上的每个结点都有k棵非空子树。如果对深度为h的满k叉树按层次自上而下，同层次自左至右的顺序从 1 开始对所有结点编号，问：（1）各层的结点数目是多少？（2）编号为n的结点的双亲结点若存在，其编号是多少？（3）编号为n的结点的第 i 个孩子结点若存在
13、，其编号是多少？（4）编号为n的结点的右兄弟的条件是什么？其右兄弟编号是多少？解（1）各层是结点数目是1ik；（2）当1=n时，该结点为根，无父结点；编号为n的结点的双亲结点编号为kkn2+);2(k（3）编号为n的结点的第i个孩子结点的编号是;1)1(+ikn（4）编号为n的结点有右兄弟的条件是;0mod)1(kn其右兄弟的编号是1+n。例 3 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？解（1）当k叉树只有一个层的分支树为k，其它层的分支树均为 1 时，此时的树是具有最大的深度；（2）当该k叉树为完全k叉树时，深度最小，其深度为1log+nk。【题型【题型 8 8 8
14、8】二叉树的存储结构二叉树的存储结构1 1 1 1）给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。例 1 画出下列二叉树的二叉链表表示图。数据结构重点题型整理古月编辑-7-解二叉树的二叉链表表示2 2 2 2）给出二叉树的顺序存储示意图，画出二叉树。给出二叉树的顺序存储示意图，画出二叉树。例 2 已知某二叉树的顺序存储结构如下所示，试画出该二叉树。ABCDEFG分析按照给出的顺序存储结构，先绘制出一棵包括空结点的完全二叉树，然后去掉空结点就是所求的二叉树。解所求二叉树如下图【题型【题型 9 9 9 9】森林、树与二叉树的互相转换森林、树
15、与二叉树的互相转换【1】森林转换成二叉树森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。将森林转换为二叉树的步骤是：（1）先把每棵树转换为二叉树；（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。数据结构重点题型整理古月编辑-8-森林转换为二叉树的转换过程示意图【2】树转换成二叉树由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。将树转换
16、成二叉树的步骤是：（1）加线。就是在所有兄弟结点之间加一条连线；（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。树转换为二叉树的过程示意图【3】二叉树转换成树二叉树转换为树是树转换为二叉树的逆过程，其步骤是：（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；(2)删除原二叉树中所有结点与其右孩子结点的连线；(3)整理（1）和（2）两步得到的树，使之结构层次分明。数据结构
17、重点题型整理古月编辑-9-二叉树转换为树的过程示意图【4】二叉树转换成森林二叉树转换为森林比较简单，其步骤如下：（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；（2）把分离后的每棵二叉树转换为树；（3）整理第（2）步得到的树，使之规范，这样得到森林。根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序
18、遍历的结果序列相同。【题型【题型 10101010】构造哈夫曼树及带权路径长度的计算构造哈夫曼树及带权路径长度的计算例 1 给定一个权重集合为 W=3,15,17,14,6,16,9,2，请画出相应的哈夫曼树，并计算其带权路径长度 WPL。解相应哈夫曼树如下图所示：该哈夫曼树的带全路径长度为：2292)1716(3)15149(465)32(=+=WPL例 2 假设用于通信的电文仅由 8 个字母字符组成，各字母字符在电文中出现的频率分别数据结构重点题型整理古月编辑-10-为 7、19、26、32、3、21、10。试为这 8 个字母字符设计哈夫曼编码。对这 8 个字母字符分别为 07 的 3 位
19、二进制表示形式编码是另一种编码方案，试比较这两种编码方案的优缺点。解构造的哈夫曼树如图所示：对图所示的哈夫曼树，叶子结点表示要编码的字符，约定左分支为“0”，右分支为“1”，则从根到叶子结点的路径上，由分支二进制数组成的二进制数字串即为该字符的编码（二进制前缀码）。因此由图可知，哈夫码编码为：7:1010,19:00,2:10000,6:1001,32:11,3:10001，21:01,10：1011。该哈夫曼树的带权路径长度为：2612)322119(4)1076(5)32(=+=WPL如使用 07 的等长 3 位二进制数表示，则3003)322119107632(=+=WPL由此得出哈夫曼
20、编码的码长较短，传输效率较高，但实现相对较难；而等长码的设计简单且易于实现，但相对效率较低。【题型【题型 1 1 1 11 1 1 1】图图的的存储结构存储结构例 1 对于下图给出是有向图和无向图，分别给出其邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度（对有向图需先确定入度和出度）。数据结构重点题型整理古月编辑-11-解（1）邻接矩阵=010000000000110000101000010000000110A=0111010101110111010101110B（2）邻接表图（a）有向图的邻接表如下图所示：图（b）无向图的邻接表如下图所示：（3）逆邻接表图（b）有向图的逆邻接表如下图所示：数
21、据结构重点题型整理古月编辑-12-（4）求顶点的度图（a）有向网顶点的度如下：312)6()6()6(330)5()5()5(321)4()4()4(321)3()3()3(211)2()2()2(220)1()1()1(=+=+=+=+=+=+=+=+=+=+=+=+=vODvIDvTDvODvIDvTDvODvIDvTDvODvIDvTDvODvIDvTDvODvIDvTD图（b）无向网顶点的度如下：3)5(3)4(4)3(3)2(3)1(=vTDvTDvTDvTDvTD例 2 对于有 n 个顶点的无向图，若采用邻接矩阵表示如何判断以下问题：（1）图中有多少条边？（2）任意两个顶点 i 和
22、 j 之间是否有边相连？（3）任意一个顶点的度是多少？解（1）图中的边数为21”的个数矩阵中“。（2）若jiA为 1，则两个顶点 i 和 j 相连。（3）顶点 i 的度为矩阵第 i 行元素的和。【题型【题型 1 1 1 12 2 2 2】图的遍历（深度优先遍历和广度优先遍历）图的遍历（深度优先遍历和广度优先遍历）和和构造最小生成树构造最小生成树例 1 对于下图给出的无向图，分别给出（1）邻接多重表（2）深度优先搜索遍历序列（分别从 v1 和 v4 开始）和深度优先生成树。（3）广度优先搜索遍历序列（分别从 v1 和 v4 开始）和广度优先生成树。（4）用 Prim 算法求得最小生成树的过程。（
23、5）用 Kruskal 算法求得最小生成树的过程。解（1）右图无向网的邻接多重表如下图所示。数据结构重点题型整理古月编辑-13-（2）深度优先搜索遍历序列（分别从 v1 和 v4 开始）分别如下：38765421vvvvvvvv87653124vvvvvvvv深度优先生成树如下：（3）广度优先搜索遍历序列（分别从 v1 和 v4 开始）分别如下：87654321vvvvvvvv87165324vvvvvvvv深度优先生成树如下：（4）用 Prim 算法求出最小生成树的过程如下图所示：数据结构重点题型整理古月编辑-14-（a）初态（b）一条边（c）两条边（d）三条边（e）四条边（f）五条边（g）
24、六条边（h）七条边（5）用 Kruskal 算法求出最小生成树的过程如下图所示：（a）初态（b）一条边（c）两条边（d）三条边数据结构重点题型整理古月编辑-15-（e）四条边（f）五条边（g）六条边（h）七条边例 2 己知一个带权无向图(G=V，E)的顶点集 V 和边集 E 分别为：V=1，2，3，4，5，6；E=（1，2）6，（1，6）1，（2，3）4，（2，6）11，（3，4）3，（3，6）5，（4，5）9，（4，6）12，（5，6）8；按照普里姆算法从 1 出发得到最小生成树，试写出在最小生成树中依次得到的边。解（1，6）1，（6，3）5，（3，4）3，（3，2）4，（6，5）8【题型【
25、题型 1 1 1 13 3 3 3】计算顶点的最短路径计算顶点的最短路径例 1 对于下图给出的有向图，分别给出（1）邻接矩阵。（2）用 Dijkstra 算法求从 v1 出发到各顶点的最短路径。数据结构重点题型整理古月编辑-16-解（1）邻接矩阵为：=022020535018100A（2）用 Dijkstra 算法求从 v1 出发到各顶点的最短路径如下表所示：P所选顶点集合 SDistiPrei1234512345初态v1v101018011001v2v1v21515135222v5v1v2v53v3v1v2v5v34v4v1v2v5v3v4结果v1v2v5v3v401015151301522
26、例 2 用 Floyd 算法求下图中每对顶点间的最短路径。解用 Floyd 算法求下图中每对顶点间的最短路径如下表所示：数据结构重点题型整理古月编辑-17-a0a1a2a3a1231231231231026026026026218081808180811083340340340240path0path1path2path3path123123123123101101101101122022022023023330330330330【题型【题型 1 1 1 14 4 4 4】二叉检索树（二分查找法）二叉检索树（二分查找法）例 1 在序列 3，8，12，30，36，38，42，50，68 中，用折
27、半查找法查找关键字 32 时，需要在哪个区间内和哪些元素进行比较，做多少次比较?解做 4 次关键字比较。第一次与 36 比较，查找区间缩小到3，8，12，30，第二次与 8比较，查找区间缩小到12，30，第三次与 12 比较，查找区间缩小到30，第四次与 30比较，查找失败。例 2 假定一个待散列存储的线性表为(32，75，29，63，48，94，25，46，18，70)，散列地址空间为 HT13，若采用除留余数法构造散列函数，处理冲突采用线性探查法，试求出每个元素的散列地址，画出最后得到的散列表，求出平均查找长度。解从题意可知散列函数可定义为：H(K)=K%13；H(32)=32%13=6H
28、(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3，冲突，线性探查加 1，得 4，不冲突。H(25)=25%13=12H(46)=46%13=7H(18)=18%13=5；H(70)=70%13=5，冲突；线性探查加 1 得 6，冲突；线性探查加 1 得 7，冲突；线性探查加数据结构重点题型整理古月编辑-18-1 得 8，不冲突。由上可知，其散列表表示应为：012345678910111229931832467048756325其平均查找长度为：（1+1+1+1+1+2+1+1+1+4）/10=14/10=1.4
29、例 3 给定一个数列 R=7,16,4,8,20,9,6,18,5，请构造出一棵二叉搜索树，并求出其中序遍历和后序遍历的排列结果。解本题产生的二叉搜索树的广义表为 7（4（，6（5），16（8（，9），20（18），可得其树型结构图如下所示。该二叉树的中序遍历结果为：4，5，6，7，8，9，16，18，20该二叉树的后序遍历结果为：5，6，4，9，8，18，20，16，7例 4 对于 10000 个项的线性表，若采用等分区间顺序检索方法进行检索，问：（1）每块的理想长度为多少？此时把线性表划分成多少个块？（2）平均检索长度为多少？假定在等概率情况下讨论。（3）若每块长度为 40，其平均检索长度
30、为多少？解（1）表长 n 已给定，此时理想的块长度为n，即10010000=nd由于采用等分区间顺序检索方法进行检索，长度为 n 的表就分成100100/10000/=dnb块（2）平均检索长度为 ASL=（b+d）/2+1=101。（3）.若每块长度为 40，则可知表就分成dnb/=，25040/10000=b块，故其平均检索长度为 ASL=（b+d）/2+1=（250+40）/2+1=146。【题型【题型 1 1 1 15 5 5 5】拓扑序列拓扑序列7 7 7 74 4 4 48 8 8 86 6 6 6161616165 5 5 5202020209 9 9 918181818数据结构
31、重点题型整理古月编辑-19-例 1 给出下图所示有向无环图的所有拓扑有序序列，并指出按拓扑排序算法求得的序列是哪一个。解按拓扑排序算法求得的序列有：526431562431564231564321vvvvvvvvvvvvvvvvvvvvvvvv例 2 对于下图所示的 AOE 网，求出各个活动可能的最早开始时间和允许的最晚开始时间。并回答下列问题。（1）整个工程的最短完成时间是多少？（2）哪些活动是关键活动？（3）是否存在这样的活动，加快它的速度可使整个工程提前完成？解（1）整个工程的最短完成时间是 25。（2）关键活动为：14129641,aaaaaa。（3）存在，如关键活动改变，则可以加快速
32、度使整个工程提前完成。【题型【题型 1 1 1 16 6 6 6】排序排序例给定排序码序列为)23,12,25,21,15,32,35,21,8,17(，试分别写出使用以下排序方法进数据结构重点题型整理古月编辑-20-行排序的过程，并说明关键字的比较次数。（1）直接插入排序；（2）希尔排序（增量为 5,2,1）；（3）二路插入排序；（4）折半插入排序；（5）共享栈插入排序；（6）冒泡排序；（7）快速排序；（8）直接选择排序；（9）树形选择排序；（10）堆排序；（11）二路归并排序；（12）基数排序。解（1）直接插入排序过程如下：)35,32,25,23,21,21,17,15,12,8(23)
33、,35,32,25,21,21,17,15,12,8(23,12),35,32,25,21,21,17,15,8(23,12,25),35,32,21,21,17,15,8(23,12,25,21),35,32,21,17,15,8(23,12,25,21,15),35,32,21,17,8(23,12,25,21,15,32),35,21,17,8(23,12,25,21,15,32,35),21,17,8(23,12,25,21,15,32,35,21),17,8(（2）希尔排序（增量为 5,2,1）的过程如下：数据结构重点题型整理古月编辑-21-（3）二路插入排序的过程如下：8(),35
34、,32,25,23,21,21,17,15,128(,23),35,32,25,21,21,17,15,128(,23,12),35,32,25,21,21,17,158(,23,12,25),35,32,21,21,17,158(,23,12,25,21),35,32,21,17,158(,23,12,25,21,15),35,32,21,178(,23,12,25,21,15,32),35,21,178(,23,12,25,21,15,32,35),21,178(,23,12,25,21,15,32,35,21),17（4）冒泡排序的过程如下：（5）快速排序的过程如下：35,32,25,2
35、3,21,21,17,15,12,835,32,25,21,21,23,17,15,12,823,21,25,21,35,32,17,15,8,12（6）直接选择排序的过程如下：35,32,25,23,21,21,17,15,12,832,35,25,23,21,21,17,15,12,832,35,25,23,21,21,17,15,12,823,35,25,32,21,21,17,15,12,823,35,25,21,32,21,17,15,12,823,35,25,21,21,32,17,15,12,823,17,25,21,21,32,35,15,12,823,17,25,21,15,32,35,21,12,823,12,25,21,15,32,35,21,17,8数据结构重点题型整理古月编辑-22-（7）二路归并排序的过程如下：3532252321211715128231235322521211715823123225211535211782312252115323521817其他排序方法参见课本习题指导书196194PP。补充：n=20，要求最坏情况速度最快，则应选择堆排序；n=20，要求既要快，又要排序稳定，则应选择直接插入排序。n=2000，要求平均情况速度最快，则应选择快速排序。