数据结构习题(5)

排序；每次从无序子表中挑选一个最小或最大元素，把它交换到有序表的一端， 此种方法叫做排序 。

6.每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。

7.在内部排序中，平均比较次数最少的是 ，要求附加存储空间最大的是 ，排序时不稳定的是 、 、 、 。

8. 排序是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

9.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录（即无序表）为 。

10. 在对一组记录{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 次。

11.在堆排序和快速排序中，若原始记录接近正序，则选用 。若原始记录无序，则最好选用 。 12.在直接插入和直接选择排序中，若初始数据基本有序，则选用 ，若初始数据基本反序，则选用 。 四．简答题

1.某整型数组R的10个元素依次为{6,2,9,7,3,8,4,5,0,10}。用下列各排序方法，将R中元素从小到大排序。 （1）取第一个元素6作为划分数据，试写出快速排序第一次划分操作后R中的结果。 （2）用堆排序（大顶堆），试写出将第一个选出的数据交换到R的最后位置上，再将其余元素调整成堆后R中的结果。 2.已知序列{70,83,100,105,10,32,7,9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟结果。 3.已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用希尔排序法对该序列做升序排序的每一趟结果。 4. 已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列做升序排序的每一趟结果。 5.判断下列序列是否为堆（小根或大根堆），若不是，则将其调整为堆： （1）（100,86,73,66,39,42,57,35,21） （2）（12,70,33,65,24,56,48,92,86,33）

6.已知序列{57,40,38,11,13,34,48,75,6,19,9,7}，采用堆排序法对该序列做降序排序时的每一趟过程。 7.设计一个直接选择排序算法，将数组中的元素按降序排列。 8.设计一个算法，在n个元素的堆中增加一个元素且调整为堆。

21

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(5)在线全文阅读。