下载文档原格式
第十章内部排序一，选择1. 基于比较方法的n个数据的内部排序。
最坏情况下的时间复杂度能达到的最好下界是（）。
A. O(nlogn)B. O(logn)C. O(n)D. O(n*n)2．下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序5. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。
6．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( )A．插入排序 B．枚举排序 C．选择排序 D．交换排序7．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈快速排序〈归并排序 B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序 D．堆排序 > 快速排序 > 归并排序8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。
A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序9．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( ) A．N B．2N-1 C．2N D．N-110．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
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)11. 在下面的排序方法中，辅助空间为O（n）的是( ) 。
第10章内部排序10.1 复习笔记一、概述1．排序的相关概念（1）排序：重新排列表中元素，使其按照关键字递增或递减排列的过程。
（2）内部排序：待排序记录存放在计算机的随机存储器中进行排序的过程。
（3）外部排序：待排序记录数据量大，内存不能一次性容纳全部记录，排序时需对外存进行访问的过程。
2．排序算法的评价（1）时间复杂度（2）空间复杂度（3）稳定性在设计排序算法时，除了考虑算法的时间和空间复杂度外，还需考虑算法的稳定性，稳定性定义如下：待排序列中两个元素R i，R j对应的关键字K i＝K j，且排序前R i在R j前面，若选择某一种算法对该序列排序后，R i仍在R j前面，则称该排序算法是稳定的，否则是不稳定的。
二、插入排序1．直接插入排序（1）算法分析将待排序记录分为有序子序列和无序子序列两部分，每次将无序序列中的元素插入到有序序列中的正确位置上。
即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减的有序序列为止，整个排序过程进行n－1趟插入。
其算法实现如下：（2）算法评价①时间复杂度：平均情况下，考虑待排序列是随机的，其时间复杂度为O（n2）。
②空间复杂度：仅使用常数个辅助单元，空间复杂度为O（1）。
③稳定性：每次插入元素都是从后向前先比较再插入，不存在相同元素位置交换，所以算法是稳定的。
2．折半插入排序（1）算法分析当排序表顺序存储时，可以先折半查找出待插位置，再对该位置后的元素统一后移，并完成插入操作。
其算法实现如下：（2）算法评价①时间复杂度：折半插入排序只是减少了元素比较次数，其他的均与直接插入排序相同，因此时间复杂度仍为O（n2）。
②空间复杂度：与直接插入排序相同，为O（1）。
③稳定性：与直接插入排序相同，是稳定的算法。
3．希尔排序（1）算法分析先将整个待排记录序列分割成为若干子序列（形如L[i，i＋d，i＋2d，…，i＋kd]），分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
第10章内部排序答案一、填空题1. 大多数排序算法都有两个基本的操作：比较（两个关键字的大小）和移动（记录或改变指向记录的指针）。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较3次。
(可约定为，从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）；若初始数据基本反序，则选用选择排序。
4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。
若对其进行快速排序，在最坏的情况下所需要的时间是O(n2) 。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n) ，所需要的附加空间是O(n) 。
7．【计研题2000】对于n个记录的表进行2路归并排序，整个归并排序需进行log2n 趟（遍），共计移动n log2n次记录。
(即移动到新表中的总次数！共log2n趟，每趟都要移动n个元素)8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是H, C, Q, P, A, M, S, R, D, F, X ,Y；初始步长为4的希尔（shell）排序一趟的结果是P, A, C, S, Q, D, F, X , R, H,M, Y；二路归并排序一趟扫描的结果是H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟扫描的结果是F, H, C, D, P, A, M, Q, R, S, Y，X；堆排序初始建堆的结果是Y, S, X, R, P, C, M, H, Q, D, F, A。
9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。
第十章内部排序一、择题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）。
数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。
3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。
4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。
5.以三元组顺序表存放的稀疏矩阵的转置算法。
6.⼆叉树的性质及其四种遍历算法。
7.森林与⼆叉树的相互转换。
8.WPL、前缀编码的概念，哈夫曼树的构造算法。
9.图的相关概念，邻接矩阵及邻接表的存储结构。
10.图的深度优先/⼴度优先遍历算法。
11.最⼩⽣成树的两种算法。
12.拓扑排序的意义和算法。
13.最短路径算法。
14.顺序表、有序表的查找算法。
15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。
16.哈希表的相关概念，常⽤的冲突处理⽅法。
17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。
注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。
2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。
其他的算法则可能会出现在“算法题”中。
⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。
（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。
（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。
A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。
A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。
A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。
第10章内部排序【例10-1】已知关键字序列（12，77，21，65，38，7，38，53），给出采用直接插入排序方法按关键字递增序排列时的每一趟结果。
解：初始1趟2趟3趟4趟5趟6趟7趟（表示有序区）【例10-2】待排序列为（39，80，76，41，13，29，50，78，30，11，100，7，41，86），步长因子分别取5、3、1，给出采用希尔排序方法按关键字递增序排列时的每一趟结果。
解：排序过程如下：p=539 80 76 41 13 29 50 78 30 11 100 7 41 86子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。
第一趟排序结果：p=3 29 7 41 30 11 39 50 76 41 13 100 80 78 86子序列分别为{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
第二趟排序结果：p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：7 11 13 29 30 39 41 41 50 76 78 80 86 100【例10-3】已知序列（17，18，60，40，7，32，73，65，85），请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
解：初始1趟2趟3趟4趟5趟17 17 17 17 7 718 18 18 7 17 1760 40 7 18 18 1840 7 32 32 32 327 32 40 40 40 4032 60 60 60 60 6073 65 65 65 65 6565 73 73 73 73 7385 85 85 85 85 85（表示有序区）【例10-4】已知关键字序列（38，12，21，77，65，7，38，53）给出采用快速排序方法按关键字增序排序时的第一趟快排过程，并举出一个反例说明快速排序是不稳定排序。
