数据结构第10章 习题答案.doc

1下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序2有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 A下面的B，C，D都不对。 B9，7，8，4，-1，7，15，20C20，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快速排列 CShell排序 D堆排序 E简单选择排序5从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。A. 插入 B. 选择 C. 希尔 D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆7. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行 （ C ）次比较。 A. 3 B. 10 C. 15 D. 258. 对序列15，9，7，8，20，-1，4， 用希尔排序方法排序，经一趟后序列变为15，-l，4，8，20，9，7则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 29. 堆排序是（ E ）类排序A. 插入 B. 交换 C. 归并 D. 基数 E. 选择10排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）-（5）: A选择排序 B快速排序 C插入排序 D起泡排序 E归并排序 Fshell排序 G堆排序 H基数排序10.1C 5 2A 3D 4B 5G1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。比较,移动2分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。冒泡,快速3. 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。3,(10,7,-9,0,47,23,1,8,98,36)4对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。答案：初始序列：28,07,39,10,65,14,61,17,50,21 21移动：21,07,39,10,65,14,61,17,50,39移动：21,07,10,65,14,61,17,50,39 17移动：21,07,17,10,65,14,61,50,3965移动：21,07,17,10,14,61,65,50,39 14移动：21,07,17,10,14,28,61,65,50,395已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。建立堆结构：_交换与调整：（1）87 70 26 61 45 12 3 97;（2）_; （3）61 45 26 3 12 70 87 97;（4）_; （5）26 12 3 45 61 70 87 97;（6）_; （7）3 12 26 45 61 70 87 97; 答案：建立堆结构:97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97(4)45,12,26,3,61,70,87,97 (6)12,3,26,45,61,70,87,971全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？答案：在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n2)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k2)个最大（或最小）元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。2给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列； (1) 希尔排序（第一趟排序的增量为5） (2) 快速排序(3) 基数排序（基数为10）答案： (1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 （ D=5） (2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,18 (3)基数排序LSD 0123456789 分配 30 12 4 16 8 10 2 6 28 20 18 收集：3010201224166828183给定一个关键字序列24，19，32，43，38，6，13，22，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？答案： 一趟快速排序：22,19,13,6,24,38,43,32初始大堆：43,38,32,22,24,6,13,19二路并归：第一趟：19,24,32,43,6,38,13,22 第二趟：19,24,32,43,6,13,22,38 第三趟：6,13,19,22,24,32,38,43堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。 4. 已知序列29 38 22 45 23 67 31，请给出快速排序时每一趟的结果。5.知序列7, 4, -2, 19, 13, 6，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。6. 已知序列23, 38, 22, 45, 67, 31, 15, 41，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。初始关键字序列: 23 38 22 45 67 31 15 41第一趟排序后: 23 22 38 45 31 15 41 67第二趟排序后: 22 23 38 31 15 41 45 67第三趟排序后: 22 23 31 15 38 41 45 67第四趟排序后: 22 23 15 31 38 41 45 67第五趟排序后: 22 23 15 31 38 41 45 67第六趟排序后: 22 15 23 31 38 41 45 67第七趟排序后: 15 22 23 31 38 41 45 677.已知序列28，17，85，96，75，8，42，65，04 ，请给出采用二路归并排序法对该序列作递增排序时的每一趟的结果。 原序列 28， 17， 85， 96， 75， 8， 42， 65， 04 281785 9675 842 65 04第一趟 17, 28 85, 96 8, 75 42, 65 04第