当前位置：文档之家 › 数据结构考研习题-第十章排序

数据结构考研习题-第十章排序

  • 格式：doc
  • 大小：763.00 KB
  • 文档页数：57

下载文档原格式

  / 57

合集下载

排序算法考研真题及答案

排序算法考研真题及答案

排序算法考研真题及答案排序算法是计算机科学中的一个基本问题，它涉及到将一组元素按照特定的顺序重新排列。

在考研计算机科学专业中，排序算法是一个重要的考察点。

以下是一些常见的排序算法考研真题及答案。

真题1：描述快速排序算法的基本思想，并给出其时间复杂度。

答案：快速排序算法是一种分治算法，其基本思想是：1. 选择一个元素作为“基准”（pivot）。

2. 重新排列数组，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。

3. 递归地将这个过程应用于基准左边和右边的子数组。

快速排序的平均时间复杂度是O(n log n)，但在最坏情况下（例如，数组已经排序或所有元素相等）时间复杂度会退化到O(n^2)。

真题2：解释归并排序算法的工作原理，并说明其稳定性。

答案：归并排序是一种分治算法，其工作原理如下：1. 将数组分成两半，直到每个子数组只有一个元素。

2. 将这些只有一个元素的子数组合并，形成有序的子数组。

3. 重复这个过程，直到所有元素合并成一个有序数组。

归并排序是稳定的排序算法，因为它保证了相等元素的相对顺序在排序后不会改变。

真题3：插入排序算法在最好情况下的时间复杂度是多少？为什么？答案：插入排序算法在最好情况下的时间复杂度是O(n)。

这是因为当数组已经完全有序时，插入排序只需要进行n-1次比较，而不需要进行任何交换操作。

真题4：堆排序算法的工作原理是什么？请简要描述。

答案：堆排序算法的工作原理基于二叉堆数据结构：1. 将待排序数组构建成一个最大堆（或最小堆）。

2. 将堆顶元素（最大或最小元素）与最后一个元素交换，然后缩小堆的范围。

3. 重新调整堆，以保持堆的性质。

4. 重复步骤2和3，直到堆的大小减少到1。

真题5：为什么说冒泡排序算法在最坏情况下的时间复杂度是O(n^2)？答案：冒泡排序算法在最坏情况下的时间复杂度是O(n^2)，因为当数组完全逆序时，每次冒泡都需要将最大的元素移动到数组的末尾，这需要n次比较和交换。

数据结构-第十章-内部排序

数据结构-第十章-内部排序

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

第十章_排序方法(数据结构ppt-严蔚敏)

第十章_排序方法(数据结构ppt-严蔚敏)

第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量

最完整的数据结构1800题包括完整答案第10章 排序答案

最完整的数据结构1800题包括完整答案第10章 排序答案

1 3 C (n − 2) + 3 C(n)=
n=2 n=3 n>3
通过逐步递推，可以得到：C(n)=3n/2-2。显然，当 n>=3 时，2n-3>3n/2-2。事实上， 3n/2-2 是解决这一问题的比较次数的下限。 6. 假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个 记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没 h-1 有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2 ；反之，若有 u 个
59.1C 59.2A 59.3D 59.4B 59.5G
60.1B 60.2C 60.3A
61.1B 61.2D 61.3B 61.4C 61.5F
部分答案解释如下： 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值， 而给定的序列并不满足。 20. 本题为步长为 3 的一趟希尔排序。 24.枢轴是 73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于 n/2 的结点上。 64. 因组与组之间已有序， 故将 n/k 个组分别排序即可， 基于比较的排序方法每组的时间下 界为 O(klog 2 k),全部时间下界为 O(nlog 2 k)。 二、判断题 1.√ 14. √ 27. √ 2.× 15. √ 28. × 3.× 16. × 29. × 4.× 17. × 30. × 5.× 18. × 31. √ 6.× 19. × 7.× 20. × 8.× 21. × 9.× 22. × 10. × 23. × 11. × 24. × 12. × 25. √ 13. × 26. ×
第 10 章 排序（参考答案）

数据结构第九、十章作业答案

数据结构第九、十章作业答案

数据结构第九、⼗章作业答案第九章查找⼀、填空题1. 在数据的存放⽆规律⽽⾔的线性表中进⾏检索的最佳⽅法是顺序查找（线性查找）。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从⼩到⼤排列的，对⼀个给定的值k ，⽤⼆分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，⽤⼆分法查找时，最⼤⽐较次数是 7 。

3. 假设在有序线性表a[1..20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为 2 ；⽐较四次查找成功的结点数为 8 ,其下标从⼩到⼤依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当⽤穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.74．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 ⽐较⼤⼩。

5. 在各种查找⽅法中，平均查找长度与结点个数n ⽆关的查找⽅法是散列查找。

6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

7. 有⼀个表长为m 的散列表，初始状态为空，现将n （n8、设⼀哈希表表长M 为100 ，⽤除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找⽅法中，平均查找长度与结点个数⽆关的是哈希查找法10、对线性表进⾏⼆分查找时，要求线性表必须以顺序⽅式存储，且结点按关键字有序排列。

数据结构 排序 历年考研练习题库 试卷及答案

数据结构 排序 历年考研练习题库 试卷及答案

数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法，它通过重复地交换相邻两个元素的位置来实现排序。

算法的基本思想是从待排序的元素中比较相邻的两个元素大小，并根据需要交换它们的位置，直到整个序列有序为止。

冒泡排序的原理如下：首先从序列的第一个元素开始，比较相邻的两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置；否则，继续比较下一对相邻元素，直到比较到序列的最后一个元素。

这样一趟比较下来，序列中最大的元素就会被交换到最后一个位置。

接着，对序列中剩下的 n-1 个元素重复上述过程，执行 n-1 趟比较，直到整个序列有序。

在实践中，冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序序列的长度。

尽管冒泡排序存在其它更好的排序算法，但它具有编码简单、实现容易以及对小规模数据排序的优势。

二、选择排序选择排序也是一种简单直观的排序算法，它的思想是将待排序序列分为已排好序的部分和未排序的部分，每次选取未排序部分中最小（或最大）的元素，将其放置在已排好序的部分的末尾。

重复此过程，直到整个序列有序。

选择排序的具体步骤如下：首先从待排序序列中找到最小（或最大）的元素，然后将其与序列的第一个元素交换位置，将该元素视为已排序部分；接着，在剩下的未排序部分中找到最小（或最大）的元素，将其与第二个元素交换位置，将该元素视为已排序部分的最后一个元素；以此类推，每次选择序列中最小（或最大）的元素，并将该元素放置在已排序部分的末尾。

最终完成排序。

选择排序的时间复杂度同样为 O(n^2)，其中 n 为待排序序列的长度。

相比于冒泡排序，选择排序的交换操作较少，因此在实际应用中，选择排序的性能要优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入已排好序的部分中，直到整个序列有序。

与冒泡排序和选择排序不同，插入排序是一种原地排序算法。

第十章排序(可编辑修改word版)

第十章排序(可编辑修改word版)
主要辅助手段：多媒体
作业布置
10-4(2),(4),(5),10-6,
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
重点难点
希尔的思想，实现，算法分析
要求掌握知识点和
分析方法
1.概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2。插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段，板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
难点：堆的调整辅助手段：多媒体
作业布置
10-7,10-8
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.5归并排序10.6基数排序
讲授主要内容
归并排序 ，基数排序
重点难点
归并排序 ，基数排序的基本思想与算法实现
本章思考题和习题
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.1概念10.2插入排序
讲授主要内容
1．概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2.
插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段， 板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
教学思路：

数据结构第10章 习题答案

数据结构第10章 习题答案

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）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

数据结构第10章排序练习及答案

数据结构第10章排序练习及答案

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，不符合大根堆特点。

数据结构答案第10章排序学习与指导

数据结构答案第10章排序学习与指导

第10章排序10.1 知识点分析1. 排序根本概念:〔1〕排序将数据元素的任意序列, 重新排列成一个按关键字有序〔递增或递减〕的序列的过程称为排序。

〔2〕排序方法的稳定和不稳定假设对任意的数据元素序列, 使用某个排序方法, 对它按关键字进展排序, 假设对原先具有一样键值元素间的位置关系, 排序前与排序后保持一致, 称此排序方法是稳定的；反之, 那么称为不稳定的。

〔3〕内排序整个排序过程都在内存进展的排序称为内排序, 本书仅讨论内排序。

〔4〕外排序待排序的数据元素量大, 以致内存一次不能包容全部记录, 在排序过程中需要对外存进展访问的排序称为外排序。

2. 直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中, 从而得到一个新的, 记录数增1的有序表。

3. 二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置, 然后挪动记录, 空出插入位置, 再进展插入的排序方法。

4. 希尔排序希尔排序的根本思想是: 先选取一个小于n的整数d1作为第一个增量, 把待排序的数据分成d1个组, 所有间隔为d1的倍数的记录放在同一个组内, 在各组内进展直接插入排序, 每一趟排序会使数据更接近于有序。

然后, 取第二个增量d2, d2< d1, 重复进展上述分组和排序, 直至所取的增量di=1〔其中di< di-1 < ……< d2< d1〕, 即所有记录在同一组进展直接插入排序后为止。

5. 冒泡排序冒泡法是指每相邻两个记录关键字比大小, 大的记录往下沉〔也可以小的往上浮〕。

每一遍把最后一个下沉的位置记下, 下一遍只需检查比拟到此为止；到所有记录都不发生下沉时, 整个过程完毕。

6. 快速排序快速排序法是通过一趟排序, 将待排序的记录组分割成独立的两局部, 其中前一局部记录的关键字均比枢轴记录的关键字小；后一局部记录的关键字均比枢轴记录的关键字大, 枢轴记录得到了它在整个序列中的最终位置并被存放好。

数据结构chapter_10

数据结构chapter_10

typedef struct { //定义每个记录 数据元素) 定义每个记录( //定义每个记录(数据元素)的结构 KeyType key ; //关键字 //关键字 InfoType otherinfo; //其它数据项 //其它数据项 }RedType; //记录类型 //记录类型 typedef struct { //定义顺序表 定义顺序表L //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //存储顺序表的向量 //r[0] r[0]一般作哨兵或缓冲区 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 //顺序表的长度 }SqList; //顺序表类型 //顺序表类型
void BInsertSort (SqList &L) {
// 对顺序表 作折半插入排序 对顺序表L作折半插入排序 for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将L.r[i]暂存到 暂存到L.r[0] 暂存到 low = 1; high = i-1; while (low<=high) { // 在r[low..high]中折半查找有序插入的位置 中折半查找有序插入的位置 m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } // while for ( j=i-1; j>=low; --j ) L.r[j+1] = L.r[j]; // 记录后移 // 插入 L.r[high+1] = L.r[0]; } } // BInsertSort

数据结构Ch10习题答案

数据结构Ch10习题答案

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

计算机考研数据结构试卷十（练习题含答案）

计算机考研数据结构试卷十（练习题含答案）

计算机考研数据结构试卷十（练习题含答案）共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷10一、选择题1．下列程序段的时间复杂度为（）。

i=0，s=0；while (s(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的结点，N个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。

(A) ∑=-miiNi1)1((B) ∑=miiN1(C) ∑=miiN2(D) ∑=-+iiNi2)1(17. 二叉排序树中左子树上所有结点的值均（）根结点的值。

(A) < (B) > (C) = (D) !=8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

《数据结构与算法》第十章-排序习题

《数据结构与算法》第十章-排序习题

《数据结构与算法》第二部分习题精选一、填空题1. 大多数排序算法都有两个基本的操作：和。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。

(可约定为从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

若对其进行快速排序，在最坏的情况下所需要的时间是。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。

7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍），共计移动次记录。

二、单项选择题（）1．将5个不同的数据进行排序，至多需要比较次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25（）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（）3．排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序（）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。

Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序（）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 （）6．快速排序在下列哪种情况下最易发挥其长处。

Ａ. 被排序的数据中含有多个相同排序码Ｂ. 被排序的数据已基本有序Ｃ. 被排序的数据完全无序Ｄ. 被排序的数据中的最大值和最小值相差悬殊（）7．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)（）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79（）9．在最好情况下，下列排序算法中排序算法所需比较关键字次数最少。

数据结构第十章 排序

数据结构第十章 排序
7
10.2 插入排序 插入排序
直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序
10.2.1 直接插入排序
基本操作：将一个记录插入到已排好序的有序表中， 从而得到一个新的、记录数增1的有序表。
例:有一组待排序的记录的关键字初始序列如下:
(49,38,65,97,76,13,27,49`)
（4）归并排序 （5）基数排序
按内排过程中所需的工作量分类：
（1）简单的排序方法，其时间复杂度为O(n×n)
（2）先进的排序方法，其时间复杂度为O(nlogn);
（3）基数排序，其时间复杂度为O(d(n+rd))
排序算法的两种基本操作：
（1）比较两个关键字的大小； （2）将记录从一个位置移至另一个位置；
算法实现的关键设计:
将d看成是一个循环数组,并设两个指针first和final分别指示排序过 程中得到的有序序列中的第一个记录和最后一个记录在d中的位置.
例:有一组待排序的记录的关键字初始排列如下:
(49,38,65,97,76,13,27,49`) 16
[初始关键字] 49 38 65 97 76 13 27 49`
18
10.2.3 希尔排序 从直接插入排序
待排序序列基本有序可提高效率 回顾 待排序序列的记录数n很小时可提高效率
希尔排序的基本思想:
先将整个待排记录序列分割成为若干子序列分别进行
直接插入排序,待整个序列中的记录“基本有序”时,再对 全
体记例录:有进一行组一待次排直序接的插记入录排的序关. 键字初始排列如下: (49,38,65,97,76,13,27,49`)
} 12
直接插入排序的性能分析: 10. 3
(1)空间:只需一个记录的辅助空间r[0].

数据结构查找和排序习题

数据结构查找和排序习题

第九章查找一、选择题1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。

A.1B.2C.3D.43、解决哈希冲突的主要方法有（）。

A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、再哈希法D.线性探测法、再哈希法、链地址法4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。

A.nB.log2nC.(h+1)/2D.h5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p建立哈希表，则p应取（）为宜。

A.23B.24C.25D.266、设哈希表长m=14,哈希函数H(key)=key MOD11。

表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。

A.8B.3C.5D.99、m阶B-树中的m是指（）。

A.每个结点至少具有m棵子树B.每个结点最多具有m棵子树C.分支结点中包含的关键字的个数D.m阶B-树的深度10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD9，与18发生冲突的元素有（）个。

A.1B.2C.3D.411、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（）。

A.静态查找表B.动态查找表C.静态查找表和动态查找表D.两种表都不适合12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（B）次比较后查找成功。

A.1B.4C.2D.813、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（）。

A.顺序查找B.折半查找C.哈希查找D.分块查找14、下列二叉树中，不．平衡的二叉树是（）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第10章排序一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】A. 插入B. 冒泡C. 二路归并D. 堆积3．下列排序算法中，其中（）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。

11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）12．排序趟数与序列的原始状态有关的排序方法是( )排序法。

【北京航空航天大学 1999 一、9（2分）】A．插入 B. 选择 C. 冒泡 D. 快速13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。

( ) A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法【北京航空航天大学 2000 一、10（2分）】14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。

A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序【南京理工大学 2000 一、7 （1.5分）】15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。

【北京理工大学 2001 六、4 （2）】A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序16．比较次数与排序的初始状态无关的排序方法是( )。

【北方交通大学 2000 二、2（2分）】A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序【合肥工业大学 1999 一、3 （2分）】18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。

A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序【合肥工业大学 2000 一、3 （2分）】19．对一组数据（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则采用的排序是 ( )。

【南京理工大学 1997 一、2 （2分）】A. 选择B. 冒泡C. 快速D. 插入20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。

【南京理工大学 1998 一、8（2分）】A. 选择B. 快速C. 希尔D. 冒泡21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。

A．选择 B. 堆 C. 直接插入 D. 冒泡【南京理工大学 1998 一、9（2分）】22．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序B. shell排序C. 堆排序D.冒泡排序【合肥工业大学 2001 一、3（2分）】23．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 冒泡C. 归并D. 堆【南京理工大学 2001 一、7（1.5分）】【哈尔滨工业大学 2001 二、4（2分）】24．下列序列中，（）是执行第一趟快速排序后所得的序列。

【福州大学 1998 一、9 (2分)】A. [68，11，18，69] [23，93，73]B. [68，11，69，23] [18，93，73]C. [93，73] [68，11，69，23，18]D. [68，11，69，23，18] [93，73] 25．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。

【南京理工大学 1996 一、4 （2分）】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，2026．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

【燕山大学 2001 一、4（2分）】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,84,56,79)27. 在下面的排序方法中，辅助空间为O（n）的是( ) 。

【南京理工大学 1999 一、17（1分）】A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A．冒泡 B. 希尔 C. 快速 D. 堆【南京理工大学 2001 一、12 （1.5分）】29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法，最费时间的是（）算法。

A. 堆排序B. 快速排序C. 插入排序D. 归并排序【南开大学 2000一、5】31. 就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学 1998一、9 (2分）】A. 冒泡B. 希尔插入C. 交换D. 快速32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序【清华大学 1998 一、2 （2分）】类似本题的另外叙述有：(1)设有5000个无序的元素,希望用最快的速度挑选出其中前十个最大的元素,在以下的排序方法中( )最好?为什么? 【山东工业大学 1995 二、4 （3分）】A．快速排序 B．堆排序 C．归并排序 D．基数排序 E．SHELL排序(2)数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。

A. 堆排序B. 希尔排序C. 快速排序D. 直接选择排序【北京理工大学 2000 一、5 （2分）】(3)设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的排序方法中采用哪一种最好？ ( ) 【东北大学 1999 一、5 (3分)】A. 快速排序B. 归并排序C. 堆排序D.基数排序E.shell排序33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序 B．冒泡排序 C．简单选择排序【山东工业大学 1995 二、1 （2分）】类似本题的另外叙述有：(1)在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（）。

A. 直接插入排序B. 冒泡排序C. 简单选择排序D. 快速排序【山东大学 2001 二、2 (1分)】(2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。

【武汉大学2000 二、6】A.插入排序B. 选择排序C. 快速排序D. 归并排序34．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

【南开大学 2000 一、4】【西北大学 2001 二、1】A. 堆排序B. 冒泡排序C. 快速排序D. 插入排序35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 五、2 （8分）】A. 归并排序B. 快速排序C. 希尔排序D. 堆排序36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。

【北京航空航天大学 1999 一、8（2分）】A. 插入B. 选择C. 希尔D. 二路归并37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（）。

【中山大学 1999 一、11】A. 选择B. 冒泡C. 插入D. 堆38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。