数据结构与算法复习题10(C语言版).docVIP

习题10解答 判断题： 1.排序的功能是将一个数据元素(或记录)的任意序列,重新排成一个按关键字有序的序列。( ) 答：TRUE 2.直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。( ) 答：TRUE 3.使用简单选择排序方法无论记录的初始排列如何,所需进行的关键字间的比较次数相同。( ) 答：TRUE 4.用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ） 答：FALSE (希尔排序又称“缩小增量排序”，即每趟只对相同增量距离的关键字进行比较，这与关键字序列初始有序或无序无关) 单选题： 5.在对n个元素进行简单选择排序过程中，第i趟需从( )个元素中选择出最小值元素。 A．n-i+1 B. n-i C．i D. i+1 答：A 6. n个记录直接插入排序所需的记录最小比较次数是 ( ) A. n-1?? B. 2(n-1) ??? ?C. (n+2)(n-1)/2???? D. n 答：A (注：如果初始记录序列就是一个符合要求的有序序列,则每趟操作只做一次比较，n-1趟操作仅需n-1次比较。参见严蔚敏《(c语言版)数据结构》P.265) 7. 若用起泡排序对关键字序列{18，16，14，12，10，8}进行从小到大的排序，所需进行的关键字比较总次数是（ ） A．10 B. 15 C. 21 D. 34 答：B (注：参见严蔚敏《(c语言版)数据结构》P.274, 此题所给的初始序列为“逆序”，需要进行n(n-1)/2 = 6×(6-1)/2 = 15次比较。) 8. 用起泡法对n个关键码排序，在最好情况下，只需做 次比较；在最坏的情况下要做 次比较。 答：n-1， n(n-1)/2 (注：参见严蔚敏《(c语言版)数据结构》P.273~274) 9.在所有排序方法中，关键字比较次数与记录的初始排列无关的是( )。 A．希尔排序 B. 起泡排序 C. 插入排序 D．选择排序 答：D 10. 一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为( )。 A. （80，45，55，40，42，85） B. （85，80，55，40，42，45） C. （85，80，55，45，42，40） D. （85，55，80，42，45，40） 答：B 11. 一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第一个记录为基准得到一次划分结果是( )。 A. （40，42，45，55，80，85） B. （42，40，45，80，55，85） C. （42，40，45，55，80，85） D. （42，40，45，85，55，80） 答：C 12．一组记录的关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为( )。 （15，25，35，50，20，40，80，85，36，70） （15，25，35，50，80，20，85，40，70，36） （15，25，50，35，80，85，20，36，40，70） （15，25，35，50，80，20，36，40，70，85） 答：A 填空题： 13.每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。 答：插入 选择 14. 对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较 次。 答： 3 (注：当把第7个记录60插入到有序表时,前6个记录已经有序，此时记录60由后向前与有序表中的元素进行比较，直到遇到值小于60的记录为止，也就是在有序表(15,23,38,54,72,96)中共需比较3次，因此填3) 15.在对一组记录（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取di+1=「di/2」,0≤i≤t-1,其中t=「log2n」,d0=n, d t =1, n为待排序记录的个数，则第二趟排序结束后的