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

数据结构第10章 习题答案.doc下列排序算法中，其中（D ）
，冒泡排序
，归并排序
有一组数据（15, 9, 7, 8, 20,
据的排序为（A ）（按递增序）。
, C, D都不对。
C. 20, 15, 8, 9, 7, -1, 4, 7
是稳定的。
，堆排序
，冒泡排序
-1, 7, 4）用快速排序的划分方法进行一趟划分后数
B. 9, 7, 8, 4, -1, 7, 15, 20
D. 9, 4, 7, 8, 7, -1, 15, 20
下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据 初始特性影响的是：（B

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用
（D ）方法最快。
.
从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在 已排序序列的合适位置，该排序方法称为（A ）排序法。
A,插入 B,选择
在排序算法中，每次从未排序的记录中挑出最小（或最大） 排序记录的末尾，该排序方法是（A

关键码字的记录，加入到已
7.
A.
8.
4,
9.
A.
）。
D.
若用冒泡排序方法对序列｛10,14,26,29,41,52｝从大到小排序，需进行（C ）次比较。
3 B. 10 C. 15 对序列｛15, 9, 7, 8, 20, -1, 4, ｝
8, 20, 9, 7｝则该次采用的增量是
A. 1 B. 4
堆排序是（E ）类排序 插入 B,交换 C,归并
D. 25
用希尔排序方法排序，经一趟后序列变为｛15, -1,
（B ）
C. 3
D. 2

,里、法从未排序的序列中依次取出元素，与已排序序列（初始时为 空）中的元素作比较，将其放入已排序序列的正确位置上;法从未排序的序列中挑选元 素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素 进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两 种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法, 是完全二叉树结构的一个重要应用。
⑴一（5） : A,选择排序 D,起泡排序
F. shell排序 H,基数排序

5 2A 3D 4B 5G
若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的—
和记录的=比较，移动
分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的
是 算法，最费时间的是 算法。冒泡，快速
设用希尔排序对数组｛98, 36, -9, 0, 47, 23, 1, 8, 10, 7｝进行排序，给出的步长（也
称增量序列）依次是4, 2, 1则排序需 趟，写出第一趟结束后，数组中数据的
排列次序= 3,（10,7,-9,0,47,23,1,8,98,