数据结构作业

第1章 绪论

单选题

1. 数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为________。

   • B. 顺序存储结构

2. 算法指的是________。

   • D. 求解特定问题的指令有限序列

3. 下面程序段的时间复杂度为：________。

   for（i=1；i<=n；++i）
   for（j=1；j<=n；++j）
   s+=a[i][j]; 
   

   • D. O(n²)

4. 设数据结构S=（D，R），其中D={1，2，3，4}，R={<1，2>，<2，3>，❤️，4>}，则数据结构S属于________。

   • B. 线性结构

5. 设部门的上级领导下级的数据结构S=（D，R），其中D={a，b，c，d，e}，R={ a领导b a领导c，b领导d b领导 e }，则数据结构S属于________。

   • C. 树结构

6. 以下数据结构中，________是线性结构。

   • A. 字符串

7. 在数据结构中，从逻辑上可以把数据结构分为________。

   • C. 线性结构和非线性结构

8. 某算法的语句执行频度为（n²+nlog₂n+3n+8），其时间复杂度为________。

   • C. O(n²)

9. 算法的时间复杂度取决于________。

   • D. A和B

10. 设数据结构S=（DR），其中D={1234}，R={<12><23><34><41>}，则数据结构S是（ ）。

    • C. 图结构

11. 算法分析的两个主要方面是（ ）。

    • B. 时间复杂度和空间复杂度

12. 抽象数据类型的三个组成部分分别是（ ）。

    • C. 数据对象、数据关系、基本操作

13. 以下程序段中语句“m++;”的语句频度是（ ）。

    int m=0;
    for(i=1;i<=n;i++)
    for(j=1;j<=2*i;j++)m++;
    

    • A. n(n+1)

14. 链式存储的存储结构所占存储空间（ ）。

    • A. 分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

填空题

1. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
2. 线性结构中元素之间存在一对一关系，树结构中元素之间存在一对多关系，图结构中元素之间存在多对多关系。
3. 链式存储结构为了表示结点之间的关系，通常需要给每个结点附加指针字段，用于存放后继元素的地址。
4. 抽象数据类型一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括3个部分：数据对象、数据关系、基本操作。
5. 算法的5个特征是有穷性、确定性、可行性、输入、输出。
6. 顺序存储结构中数据元素之间的逻辑关系是由物理地址表示的，链式存储结构中数据元素之间的逻辑关系是由指针表示的。

简答题

1. 简述逻辑结构的四种基本关系并画出它们的关系图。

   • 逻辑结构的四种基本关系：集合结构、线性结构、树形结构、图形结构。
     • 集合结构：元素之间无特定关系
     • 线性结构：元素之间存在一对一的关系
     • 树形结构：元素之间存在一对多的层次关系
     • 图形结构：元素之间存在多对多的关系

2. 存储结构有哪两种基本的存储方法实现？

   • 顺序存储
   • 链式存储

3. 简述算法的定义与特性。

   • 算法是解决问题的一系列步骤或程序。特性包括有穷性、确定性、可行性、输入、输出。

第2章 线性表

单选题

1. 以下叙述正确的是（ ）。

   • B. 顺序表可以实现随机存取。

2. 线性表（a1a2…an）以链式方式存储时，访问第i个位置上的元素的时间复杂度为（ ）。

   • B. O(n)

3. 线性表的顺序存储结构是一种（ ）的存储结构。

   • A. 随机存取

4. 线性表在（ ）情况下适用于使用链式结构存储。

   • B. 需要不断对线性表进行插入、删除操作。

5. 以下属于顺序表的优点的是（ ）。

   • C. 存储密度大。

6. 下列叙述错误的是（ ）。

   • D. 线性表的链式存储结构优于顺序存储结构。

填空题

1. 顺序表中逻辑上相邻的元素物理位置一定相邻，单链表中逻辑上相邻的元素物理位置不一定相邻。
2. 若一个长度为n的顺序表中，在第i个位置（1≤i≤n）插入一个新的元素共需要移动n-i个元素；若一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时需向前移动n-i-1个元素。
3. 已知顺序表中第一个元素的存储地址是1000，每个元素的长度为4，则第7个元素的存储地址是1024。
4. 向一个有200个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为100。
5. 在一个以L为头指针的单循环链表中，p指针指向链尾的条件是p->next == L。

判断题

1. 线性表中每个元素都有一个前驱和一个后继。（ ）

   • 错

2. 线性表中所有元素的数据类型必须相同。（ ）

   • 对

3. 顺序表结构适宜于进行随机存取，而链表适宜于进行顺序存取。（ ）

   • 对

4. 单链表可以实现随机存取。（ ）

   • 错

5. 线性表若采用链式存储结构时，其存储结点的地址可以连续，也可以不连续。（ ）

   • 对

6. 线性表的顺序存储结构优于链式存储结构。（ ）

   • 错

7. 进行插入删除操作时，在链表中比在顺序表中效率高。（ ）

   • 对

8. 在顺序表中，逻辑上相邻的元素物理位置上不一定相邻。（ ）

   • 错

9. 若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构更合适。（ ）

   • 对

简答题

1. 简述线性结构的特点。

   • 线性结构的特点是元素之间存在一对一的线性关系，每个元素只有一个前驱和一个后继。

2. 简述顺序表和链表的主要优缺点。

   • 顺序表优点：支持随机存取，存储密度大。缺点：插入和删除操作效率低，存储空间不灵活。
   • 链表优点：插入和删除操作效率高，存储空间灵活。缺点：不支持随机存取，存储密度低。

综合题

1. 请用代码描述如下单链表的插入操作，将s所指结点插入到结点a和b之间。

   s->next = a->next;
   a->next = s;
   

2. 请用代码描述如下单链表的删除操作，将结点b删除。

   a->next = b->next;
   delete b;
   

3.**请用代码描述
b=a->next
x->pre=a
a->next=x
x->next=b
b->pre=x
4. 删除p的所指节点b
b=a->next
c=a->next->next
a->next=c
c->pre=a
delete b
第3章 栈和队列

一、单选题

1. 栈在( D,递归+表达式求值+括号匹配 )中有所应用。
2. 栈和队列的共同点是( C. 只允许在端点处插入和删除元素 )。
3. 最大容量为n的循环队列，队尾指针是rear，队头是front，则判断队空和队满的条件，正确的是( B. 队空：rearfront；队满：(rear+1)%nfront； )。
4. 下列说法中符合队列性质的是( D. 只能在一边插入和另一边删除 )。
5. 设一个队列的入队序列为d,c,b,a，则队列的输出序列是( B.dcba)。
6. 若用一个大小为6的数组实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再插入两个元素后，rear和front的值分别为( C. 2和4 )。
7. 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( A. 队列 )。
8. 若一个栈以数组V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( C top–;V[top]=x; )。
9. 若一个栈以数组V[1…n]存储，初始栈顶指针top设为0，则元素x进栈的正确操作是( A. top++; V[top]=x; )。
10. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( C. n-i )。
11. 设计一个判别表达式中左、右括号是否配对出现的算法，采用( C. 栈 )数据结构最佳。
12. 一个栈的入栈序列是a,b,c,d,e, 且在入栈过程中可出栈，则栈的不可能的输出序列是( C. dceab )。
13. 队列是限定在（ C.队尾）处进行插入操作的线性表。
14. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（ B3 ）。
15. 若元素a,b,c,d,e,f依次进栈，允许进栈、出栈操作交替进行，但不允许连续三次进行出栈工作，则不可能得到的出栈序列是（ D.afedcb ）。

二、判断题

1. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出的线性结构。（ × ）
2. 循环队列属于队列的链式存储结构。（ × ） (是队列的顺序存储结构)
3. 若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,1,5,6,4,2。（ × ）
4. 一个递归算法必须包括终止条件和递归部分。（ √ ）

三、简答题：
栈是一种先进后出（LIFO）的线性数据结构，只允许在表的一端进行插入和删除操作，即栈顶端。栈的特点是后进入的元素先出来，它可以通过顺序存储结构或链式存储结构实现。常见的应用包括递归调用、表达式求值、括号匹配等。

队列是一种先进先出（FIFO）的线性数据结构，插入操作在队尾进行，删除操作在队头进行，只能在表的两端进行操作。队列的特点是先进入的元素先出来，它同样可以通过顺序存储结构或链式存储结构实现。常见的应用包括任务调度、缓冲区管理等。

四、算法分析题：
1、

Status Push(SqStack &S, SElemType e)  
{   if (S.top == MAXSIZE - 1) return ERROR; // 判断栈满的条件S.data[++S.top] = e;  // 将e入栈，栈顶指针top上移return OK;
}  

2、

Status Pop(SqStack &S, SElemType &e)  
{  if(S.top == -1) return ERROR; // 判断栈空的条件e = S.data[S.top--]; // 用e返回栈顶元素，栈顶指针top下移return OK;
}  

3、

void conversion(int N)
{  InitStack(S);while(N){ Push(S, N % 2);  // ①将N % 2入栈N = N / 2;}while(!StackEmpty(S)){  Pop(S, e);  // ②从栈中出栈，得到二进制数的每一位cout << e;}
}

4、

Status EnQueue(SqQueue &Q, QElemType e)  
{   if((rear+1)%n==front)return ERROR;Q[rear]=e;rear++;Return OK	
}

Status DeQueue(SqQueue &Q, QElemType &e)  
{   if(rear==front)return ERROR;e=Q[front];front++;Return OK	
}

第4章 串、数组和广义表

一、单选题

1. 下面说法不正确的是（C. 广义表的表头总是一个广义表）。
2. 两个串相等必有串长度相等且（B. 串中各位置字符均对应相等）。
3. 设有两个串p和q，求q在p中首次出现的位置的运算称作（B. 模式匹配）。
4. 已知串S=“abcaba”的next数组为（C. 011123)。
   解析： 1. abcaba -->000121 (就是比较每个字符和首部是否相等)
   2.000121 每个加1------> 111232
   3.111232 向右移为：011123
   4.得到结果011123
5. 下面表述正确的是（A. 串是一种特殊的线性表）。
6. 对于n阶对称矩阵，如果采用压缩存储，需要（D. n2/2）个存储单元。
7. 对特殊矩阵进行压缩存储目的是（C. 节省存储空间）。
8. 设一维数组中有n个元素，则读取第i个数组元素的平均时间复杂度为（C. O(1)）。
9. 数组A[0…7,0…9]的每个元素占3个字节，将其按行列先次序存储在起始地址为1000的内存单元中，则元素A[7，4]的起始地址是（D. 1222）。
10. 数组A[0…5,0…6]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（B. 1200）。
11. 假设二维数组A[1…60,1…70]以列序为主序顺序存储，其基地址是10000，每个元素占2个存储单元，则元素A[32,58]的存储地址是（B. 16902）。
12. 设广义表L=（（a,b,c）），则L的长度和深度分别为（C 1和2）。
    解析：长度为第一层的所有元素个数（1），深度为一共几层括号（2）
13. 对广义表L=((a,b),(c,d),(e,f))执行操作GetTail(GetTail(L))的结果是（B.((e,f))）。

二、填空题

1. 若矩阵中的所有元素均满足aij=aji，则称此矩阵为 对称矩阵。
2. 数组A[0…7,0…8]的每个元素占4个字节，分别将其按行优先、列优先次序存储在起始地址为1000的内存单元中，则元素A[3,6]的地址是1132 和1204。
3. 模式串P=“abaabcac”的next函数值序列为 011223012。
4. 设字符串S=‘You︺did︺a︺very︺good︺job!’，其长度是24。
5. 子串“ture”在主串“datastructure”中的位置 9。
6. 设串S=“abcde”，其长度是 5。
7. 已知广义表L=((a,b),(c,d))，则head(L)是 (a,b) ，tail(L)是 ((c,d)) ，长度为 2 ，深度为 2。
8. 广义表（（a,b,c,d））的表头是 (a,b,c,d) ，表尾是 () 。
9. 已知广义表C= (a,(b,A),B)，则其长度是 3 ，深度是 无穷大 。
10. 利用KMP算法进行模式匹配时，模式串t=“abcabaa”的next函数值是 0111232。

三、判断题

1. 串是一种数据对象和操作都特殊的线性表。(√)
2. KMP算法的特点是在模式匹配时指示主串的指针不会变小。(√)
3. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×）
4. 数组和广义表不属于线性结构。(×)
5. 二维数组A[-3…5,0…10]中共有80个元素。（×）
6. 稀疏矩阵和特殊矩阵压缩存储后均可以实现随机存取。（×）
7. 数组元素的下标值越大，存取时间越长。（×）
8. 子串在主串中的位置以子串的第一个字符在主串中的位置来表示。(√)
9. KMP算法可以在O(m+n)的时间数量级上完成串的模式匹配操作。（√）
10. 对n阶矩阵，若矩阵中的元素在i>=j时均满足aij为0或为常数，则称此矩阵为下三角矩阵。（√）
11. 一个广义表的表头总是一个广义表。（×）

四、简答题
串的模式匹配是指在一个主串中查找某个子串的过程。常用的两种模式匹配算法是暴力匹配算法（BF算法）和Knuth-Morris-Pratt算法（KMP算法）。

五、算法分析题
1、BF算法：

int Index_BF(SString S, SString T, int pos) {int i = pos;int j = 1;while (i <= S.length && j <= T.length) { // ① 两个串均未比较到串尾if (S.ch[i] == T.ch[j]) { // ② 继续比较后续字符
```cppi++;j++;} else {i = i - j + 2; // ④ 指针回溯重新开始匹配j = 1;}}if (j > T.length) // ⑤ 匹配成功，返回位置序号return i - T.length;elsereturn 0; // ⑥ 匹配失败，返回0
}

2、KMP算法：

int Index_KMP(SString S, SString T, int pos) {int i = pos;int j = 1;while (i <= S.length && j <= T.length) { // ① 两个串均未比较到串尾if (j == 0 || S.ch[i] == T.ch[j]) { // ② 继续比较后续字符i++;j++;} else {j = T.next[j]; // ④ 子串向右滑动至第next[j]个位置}}if (j > T.length) // ⑤ 匹配成功，返回位置序号return i - T.length;elsereturn 0; // ⑥ 匹配失败，返回0
}

一、单选题

1. B. 100
   解析：哈夫曼树只有度（每个节点孩子数）为2和0的节点，以满二叉树为例，叶子节点有2^{(n)个，总结点数有2}(n+1)-1个
   得出总结点= n，叶子结点数有(n+1)/2
   叶子结点= n，总结点数有2n-1
   2.B. （0，1，00，11）
   解析：前缀码是指，画出的图形中不存在节点之间为父子关系
2. D. 501
3. D. 2^h-1
4. B 11
   解析：n0=n2+1记住就行
5. D5
6. B. 只有一个结点的二叉树的度为0
7. D. 2i - 1
8. A. 11
9. B. 10

二、填空题

1. 6
2. 63
3. 16
4. DGEBFCA
5. 7
6. 4, 96
   7.FBADCFHGIJK
7. n+1
8. 7 (2^(5-1)=16,第五层本来有16个结点，但是有16-7+1=8没有子节点，所以有7+8/2=11个叶子结点)
9. 是

三、判断题

1. 是
2. 是
3. 是
4. 错误
5. 错误
6. 错误
7. 错误
8. 错误
9. 错误
10. 错误
11. 是
12. 错误

四、综合题

1. 先序遍历：ABCDEFGHIJKL, 中序遍历：DCEBFAIHGKLJ, 后序遍历：DECFBIHKLJGA
2. 先序遍历：ABDHEIJCFLGMN, 中序遍历：HDBIEJAFCLMGN, 后序遍历：HDIJEBLFMNFCA
3. 先序遍历：ABCDEFGH, 中序遍历：DCEBAFHG, 后序遍历：ECBGHFA
4. 先序遍历：ABCDEF, 中序遍历：CBDAFE, 后序遍历：CDBFEA
5. 哈夫曼编码：A: 01, B: 10, C: 000, D: 001, E: 11， WPL = 91
6. 数据传输长度最短的编码：C: 000,S:001,E:01,A:10,T:11
   STATE:00111101101
   SEAT:001011011
   ACT:1000011
   TEA:110110
   CAT:0001011
   SET:0010111
   A:10
   EAT:011011
7. 先根遍历：ABDEIJFGKHC, 后根遍历：BIJEFKGHDC

一、单选题

1. D. n(n-1)/2
   解析：最多，所以是每个结点都和其余n-1个结点相连，有n*(n-1)个边
   无向图为n*(n-1) /2 ，因为重复边，要除以2
   有向图为n*(n-1) ，没有重复边
2. B. n(n-1)
3. B. 拓扑排序
4. B. 每个顶点的度等于其入度与出度之和
5. A. 2
   解析：一个边连接两个顶点，，所以是边*2
6. B. 1
   解析：入度之和=出度之和
7. A. 从源点到汇点的最长路径
8. B. 任何一个关键活动提前完成，整个工程也将提前完成
9. B 12
10. A. n-1
    解析：树的顶点数= 边数+1，随便画个树就能看出来
    11.B. 3,1,2,4,5
    解析：每次找入度为0的顶点，输出，然后删除这个顶点和连接这个顶点的边，继续找入度为0的
11. D. 对称矩阵

二、填空题

1. 6
2. 20

三、判断题

1. 错误
2. 错误
3. 错误
4. 是
5. 是
6. 是
7. 是

四、综合题
1.

• DFS序列：1364527
• BFS序列：1346527

2. [图示 Prim 算法和 Kruskal 算法构造最小生成树的全过程]
3. [AOV-网的拓扑排序序列]
   • 一种拓扑排序序列：ACEBDFHGI
   • 另一种拓扑排序序列：ACEHBDGFI
4. • Ve 和 Vl 表格如下：

顶点	最早发生时间 Ve	最晚发生时间 Vl
1	0	0
2	3	3
3	4	5
4	10	10
5	8	9
6	14	14

• 关键路径为：1 ->a1->2->a3->4->a8->6
• 工程完工的最短时间为 14 天

解析：最早发生时间就是从起点到终点找所有连接和中最大的
最晚发生时间就是从终点到起点找结点数-边值（差值）最小的
vl - ve == 0 的活动为关键活动，关键活动跟状态连起来就为关键路径。

第7章 查找

一、单选题

1. 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。

   • C. (n+1)/2

2. 适用于折半查找的表的存储方式及元素排列要求为（ ）。

   • D. 顺序方式存储，元素有序

3. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。

   • A. 20 70 30 50

4. 对22个记录的有序表作折半查找，当查找失败时，至多需要比较（ ）次关键字。

   • C. 5

5. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。

   • C (100,60,80,90,120,110,130)
     解析：二叉排序树则为左边比父类小，右边比父类大，每次从根节点开始找

6. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。

   • D. 9
     解析：二次探测法，为二次幂，1^2,22,3^2,42,累加
     线性探测为1 2 3 4 5 6线性累加

7. 衡量查找算法效率的主要标准是（ ）。

   • C. 平均查找长度

二、填空题

1. 计算哈希地址时若产生冲突，可以采用开放定址法和链地址法解决冲突。
2. 在长度为500的有序表中进行折半查找，查找不成功时和给定值进行比较的关键字个数最多为9。
   解析：log以2为底500的对数=9

三、综合题

1. 已知如下11个数据元素的有序表（05，13，19，21，37，56，64，75，80，88，92），请画出其“折半查找”到数据“37”的全过程。

   • 第一步：中间位置为56，与37比较，37<56，继续在左半部分查找。
   • 第二步：中间位置为19，与37比较，37>19，继续在右半部分查找。
   • 第三步：中间位置为37，查找成功。

2. 已知一组关键字为（47，7，29，11，16，92，22，8，3），散列函数为H(key)=key%11，用线性探测法处理冲突。设表长为11，试构造这组关键字的散列表，并写出查找每个关键字的比较次数，最后计算查找成功时的平均查找长度（四舍五入保留一位小数）。

散列地址	0	1	2	3	4	5	6	7	8	9	10
关键字	11	22		47	92	16	3	7	29	8
比较次数	1	2		1	1	1	4	1	2	2

计算查找成功时的平均查找长度：
15/9=1.7

第8章 排序

一、单选题

1、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
C．插入排序

2、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
D．选择排序

3、对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
B．从大到小排列好的

4、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。
D．n(n-1)/2

5、下面（ ）方法是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
D．基数排序

6、若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A. 38 40 46 56 79 84

7、下列关键字序列中，（ ）是堆。
D．16，23，53，31，94，72

8、堆排序是一种（ ）排序。
B．选择

9、堆的形状是一棵（ ）。
C．完全二叉树

10、下列排序算法中，（ ）不属于选择排序。
A．希尔排序

11、下列排序算法中不稳定的是（ ）。
D．快速排序

二、综合题

设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

①直接插入排序

[2 12] 16 30 28 10 16* 20 6 18

[2 12 16] 30 28 10 16* 20 6 18

[2 12 16 30] 28 10 16* 20 6 18

[2 12 16 28 30] 10 16* 20 6 18

[2 10 12 16 28 30] 16* 20 6 18

[2 10 12 16 16* 28 30] 20 6 18

[2 10 12 16 16* 20 28 30] 6 18

[2 6 10 12 16 16* 20 28 30] 18

[2 6 10 12 16 16* 18 20 28 30]

②希尔排序

10 2 16 6 18 12 16* 20 30 28 （增量选取5）

6 2 12 10 18 16 16* 20 30 28 （增量选取3）

2 6 10 12 16 16* 18 20 28 30 （增量选取1）

③简单选择排序
[2],12,16,6,30…
[2,6],12,16,30,29
[2,6,10,]…
[2,6,10,12],…
[2 6 10 12 16 16* 18 20 28 30]

一直取最小/最大 和后面的交换位置

④ 冒泡排序

2 12 16 28 10 16* 20 6 18 [30]

2 12 16 10 16* 20 6 18 [28 30]

2 12 10 16 16* 6 18 [20 28 30]

2 10 12 16 6 16* [18 20 28 30]

2 10 12 6 16 [16* 18 20 28 30]

2 10 6 12 [16 16* 18 20 28 30]

2 6 10 [12 16 16* 18 20 28 30]

2 6 10 12 16 16* 18 20 28 30]

⑤快速排序

12 [6 2 10] 12 [28 30 16* 20 16 18]

6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]

28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]

18 2 6 10 12 [16* 16] 18 [20] 28 30

16* 2 6 10 12 16* [16] 18 20 28 30