下载文档原格式
1．下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是( )。
A. 选择B. 冒泡C. 快速D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。
A. 选择B. 快速C. 希尔D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。
A．选择 B. 堆 C. 直接插入 D. 冒泡7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A. 堆排序B. 冒泡排序C. 快速排序D. 插入排序9. 下列排序算法中，占用辅助空间最多的是：( )A. 归并排序B. 快速排序C. 希尔排序D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。
A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,4011. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。
一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
1．下列排序算法中，其中（ D ）是稳定的。
A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。
A．下面的B，C，D都不对。
B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。
A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。
A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。
A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。
A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。
A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。
数据结构(第二版)习题库章节练习题1-9章全数据结构(第二版)习题库章节练习题1-9章全第一章：引论引论部分为数据结构的开篇，主要介绍了数据结构的基本概念和分类。
在这一章中，我们学习了数据结构的定义、作用以及与算法的关系。
接下来，将为你详细介绍第一章的习题内容。
1. 习题1-1题目：请简述数据结构的定义和作用。
要求：通过一段简洁清晰的语言来回答问题，并给出你的理解。
答案：数据结构是计算机中存储、组织和管理数据的方式。
它旨在将数据以特定的方式进行排列，以便高效地进行存储和检索。
数据结构作为计算机科学的基础，为我们解决实际问题提供了有效的工具和方法。
2. 习题1-2题目：你认为数据结构与算法之间的关系是什么？要求：结合实际案例，详细解释数据结构与算法之间的相互依赖关系。
答案：数据结构和算法是密不可分的，它们之间存在着相互依赖的关系。
数据结构提供了算法操作的基础，而算法则对数据结构进行操作和处理。
例如，在搜索算法中，我们需要合适的数据结构来存储和组织数据，以便能够高效地进行搜索操作。
而无论是数组、链表还是树，都需要通过算法来进行增删改查等操作。
第二章：算法分析算法分析是数据结构中的重要概念，它涉及到算法的运行时间和空间效率。
在这一章中，我们将学习算法分析的基本方法和常用技巧，并通过习题来巩固所学知识。
3. 习题2-1题目：请解释渐进记号中的"O"表示什么意思。
要求：简明扼要地回答问题，并辅以例子说明。
答案：在算法分析中，"O"表示渐进上界。
它描述了算法在最坏情况下的运行时间复杂度。
例如，如果一个算法的时间复杂度为O(n)，那么说明该算法的运行时间与输入规模n成正比。
即使输入规模变大，算法的运行时间也不会超过n的某个常数倍。
4. 习题2-2题目：请说明算法的平均情况分析与最坏情况分析有何区别？要求：用简洁的语言说明两种分析方法的不同之处，并给出具体的示例。
答案：算法的平均情况分析和最坏情况分析的区别在于对输入数据的预先假设。
单元测验4一．判断题<下列各题，正确的请在前面的括号内打√；错误的打╳）<√）<1）队列是限制在两端进行操作的线性表。
<√）<2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。
<×）<3）在链队列上做出队操作时，会改变front指针的值。
<√）<4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。
<×）<5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。
<√）<6）链队列在一定范围内不会出现队满的情况。
<×）<7）在循环链队列中无溢出现象。
<×）<8）栈和队列都是顺序存储的线性结构。
<×）<9）在队列中允许删除的一端称为队尾。
<×）<10）顺序队和循环队关于队满和队空的判断条件是一样的。
二．填空题（1）在队列中存取数据应遵循的原则是先进先出。
（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
（3）在队列中，允许插入的一端称为队尾。
（4）在队列中，允许删除的一端称为队首<或队头）。
（5）队列在进行出队操作时，首先要判断队列是否为空。
（6）顺序队列在进行入队操作时，首先要判断队列是否为满。
（7）顺序队列初始化后，front=rear= -1 。
（8）解决顺序队列“假溢出”的方法是采用循环队列。
循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。
（10）链队列LQ为空时，LQ->front->next= NULL 。
（11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O<n）。
（12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0<1）。
9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。
A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。
A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。
Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。
数据结构试卷（十）一、选择题(24分)1．下列程序段的时间复杂度为（）。
i=0，s=0；while (s<n) {s=s+i；i++；}(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
(A) 单向链表(B) 单向循环链表(C) 双向链表(D) 双向循环链表3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。
(A) s->next=p->next；p->next=-s；(B) q->next=s； s->next=p；(C) p->next=s->next；s->next=p；(D) p->next=s；s->next=q；4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。
(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。
(A) 10 (B) 19 (C) 28 (D) 556．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。
(A) ∑=-miiNi1)1((B) ∑=miiN1(C) ∑=miiN2(D) ∑=-+miiNi2)1(17. 二叉排序树中左子树上所有结点的值均（）根结点的值。
(A) < (B) > (C) = (D) !=8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。
数据结构试题及答案(10套最新)数据结构试题及答案(10套最新)第一套试题：问题一：什么是数据结构？数据结构的作用是什么？回答：数据结构是一种组织和存储数据的方式，它关注数据元素之间的关系以及对数据元素的操作。
数据结构的作用包括提供高效的数据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法的性能和程序的可读性。
问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。
回答：常见的线性数据结构包括数组、链表和栈。
数组是一种连续存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出原则的数据结构，常用于解决递归问题。
问题三：请说明二叉树的定义及其性质。
回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点。
二叉树具有以下性质：每个节点最多有两个子节点，分别称为左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个数为n，边的个数为n-1。
问题四：在数组中查找一个元素的时间复杂度是多少？为什么？回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组的长度。
因为在数组中查找元素需要按照索引一个一个比较，最坏情况下需要比较n次才能找到目标元素。
问题五：请解释堆排序算法的原理及时间复杂度。
回答：堆排序算法利用堆这种数据结构进行排序。
首先将待排序的元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得到从小到大排序的序列。
堆排序的时间复杂度为O(nlogn)。
第二套试题：问题一：请解释图的邻接矩阵和邻接表表示法。
回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系，数组中的元素表示相应节点之间的边的关系。
邻接表表示法使用链表来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。
问题二：请说明深度优先搜索算法的原理及其应用。
回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。
单元测验10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。
（√）（2）希尔排序是不稳定的排序。
（ㄨ）（3）冒泡排序是不稳定的排序。
（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。
（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。
（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。
（ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。
（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。
（√）（9）采用归并排序可以实现外排序。
（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。
二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。
（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。
（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。
（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。
（5）对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。
（6）在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。
（7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。
（8）快速排序在最坏情况下的时间复杂度是 O(n2) 。
（9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。
（10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。
（11）若原始数据接近无序，则选用快速排序最好。
（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。
（13）在插入排序和选择排序中，若初始数据基本正序，则选用插入排序较好。
（14）当增量为1时，该趟希尔排序与直接插入排序基本一致。
（15）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。
（16）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。
（17）在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。
（18）在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。
（19）两个序列分别为：L1={25，57，48，37，92，86，12，33}L2={25，37，33，12，48，57，86，92}。
用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L2 。
（20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。
三．选择题（1）排序是根据（ A ）的大小重新安排各元素的顺序。
A．关键字 B．数组 C．元素件 D．结点（2）评价排序算法好坏的标准主要是（ D ）。
A．执行时间 B．辅助空间C．算法本身的复杂度 D．执行时间和所需的辅助空间（3）直接插入排序的方法是（ B ）的排序方法。
A．不稳定 B．稳定 C．外部 D．选择（4）直接插入排序的方法要求被排序的数据（ B ）存储。
A．必须链表 B．必须顺序 C．顺序或链表 D．可以任意（5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 ( D )。
A．希尔排序 B．归并排序 C．插入排序 D. 选择排序（6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ C ）。
A．冒泡排序 B．堆排序 C．快速排序 D. 归并排序（7）快速排序在（ C ）情况下最易发挥其长处。
A．待排序的数据中含有多个相同的关键字 B．待排序的数据已基本有序C．待排序的数据完全无序 D．待排序的数据中最大值与最小值相差悬殊（8）下述几种排序方法中，要求内存量最大的是：（ D ）。
A．插入排序 B．选择排序 C．快速排序 D. 归并排序（9）直接插入排序的方法是从第（ B ）个元素开始，插入到前边适当位置的排序方法。
A．1 B．2 C．3 D．n（10）堆的形状是一棵（ C ）。
A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树（11）内排序是指在排序的整个过程中，全部数据都在计算机的（ A ）中完成的排序。
A．内存 B．外存 C．内存和外存 D．寄存器（12）快速排序的方法是（ A ）的排序方法。
A．不稳定 B．稳定 C．外部 D．选择（13）下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（ A ）。
A．选择排序 B．希尔排序 C．插入排序 D．冒泡排序（14）下述几种排序方法中，平均时间复杂度最小的是（ A ）。
A．希尔排序 B．插入排序 C．冒泡排序 D．选择排序（15）对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ B ）。
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)（16）冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（ C ）次。
A．1 B．2 C．n-1 D．n（17）对ｎ个不同的排序码进行冒泡（递增）排序，在下列（ B ）情况比较的次数最多。
A．从小到大排列好的 B．从大到小排列好的 C．元素无序 D．元素基本有序（18）用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（ B ）。
A，94，32，40，90，80，46，21，69 B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80 D．90，69，80，46，21，32，94，40（19）一组记录的排序码为(25，48，16，35，79，82，23，40)，其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为：（ A ）。
A，16 25 35 48 23 40 79 82 36 72 B．16 25 35 48 79 82 23 36 40 72C．16 25 48 35 79 82 23 36 40 72 D．16 25 35 48 79 23 36 40 72 82（20）一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（ C ）A．（38，40，46，56，79，84） B．（40，38，46，79，56，84）C．（40，38，46，56，79，84） D．（40，38，46，79，56，84）四．排序过程分析1．已知数据序列{10，8，18，15，7，16}，写出采用直接插入算法排序时，每一趟排序的结果。
解： 10 8 18 15 7 16第一趟结束时结果： [8 10] 18 15 7 16第二趟结束时结果： [8 10 18] 15 7 16第三趟结束时结果： [8 10 15 18] 7 16第四趟结束时结果： [7 8 10 15 18] 16第五趟结束时结果： [7 8 10 15 16 18]2．已知数据序列{18，17，60，40，07，32，73，65}，写出采用直接插入算法排序时，每一趟排序的结果。
解： 18 17 60 40 07 32 73 65第一趟结束时结果： [17 18] 60 40 07 32 73 65第二趟结束时结果： [17 18 60] 40 07 32 73 65第三趟结束时结果： [17 18 40 60] 07 32 73 65第四趟结束时结果： [07 17 18 40 60] 32 73 65第五趟结束时结果： [07 17 18 32 40 60] 73 65第六趟结束时结果： [07 17 18 32 40 60 73] 65第七趟结束时结果： [07 17 18 32 40 60 65 73]3. 已知数据序列{17，18，60，40，7，32，73，65，85}请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。
解：第一趟排序结果：第二趟排序结果：第三趟排序结果：第四趟排序结果：第五趟排序结果：第五趟排序过程中已无记录交换，排序结束。
4．已知数据序列{80，18，9，90，27，75，42，69，34}请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。
解： 80 18 09 90 27 75 42 69 34第一趟排序结果：第二趟排序结果：第三趟排序结果：第四趟排序结果：第五趟排序结果：第六趟排序结果：第六趟排序过程中已无记录交换，排序结束。
5．已知数据序列{10，18，4，3，6，12，9，15，8}，写出希尔排序每一趟（设d=4、2、1）排序的结果。
解：10 18 4 3 6 12 9 15 8d=4 6 12 4 3 8 18 9 15 10d=2 4 3 6 12 8 15 9 18 10d=1 3 4 6 8 9 10 12 15 186．已知数据序列{12，02，16，30，28，10，17，20，06，18}，写出希尔排序每一趟排序的结果。
（设d=5、2、1）解： 12 02 16 30 28 10 17 20 06 18d=510 02 16 06 18 12 17 20 30 28d=212 02 16 06 17 12 18 20 30 28d=1 02 06 10 12 16 17 18 20 28 307．已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。
[10] [18] [4] [3] [6] [12] [9] [15][10 18] [3 4] [6 12] [9 15] 第一趟排序结果[3 4 10 18] [6 9 12 15] 第二趟排序结果[3 4 6 9 10 12 15 18] 第三趟排序结果8．已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。
解： [53 36 48 36 60 7 18 41]（7） [36 48 36 60 53 18 41]（7 18） [48 36 60 53 36 41]（7 18 36） [48 60 53 36 41]（7 18 36 36） [60 53 48 41]（7 18 36 36 41） [53 48 60]（7 18 36 36 41 48） [53 60]（7 18 36 36 41 48 53） [60]（7 18 36 36 41 48 53 60 ）9．已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。
