一、填空題

1.每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做 插入 排序；

每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 選擇

排序。

2每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序

方法叫做交換排序，每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做二路歸并排序。

3在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為 O(n2)，記錄移動次數(shù)的時間復(fù)

雜度為 O(n) 。

4在堆排序的過程中，對n個記錄建立初始堆需要進行[n/2]次篩運算，由初始堆到堆排序結(jié)束，

需要對樹根結(jié)點進行n-1次篩運算。

5在堆排序過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為O(log2n),

整個堆排序過程的時間復(fù)雜度為O(nlog2n)。

6假定一組的記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為(84,79,56,

38,40,46)。

7快速排序在平均情況下的時間復(fù)雜度為O(nlog2n)，在最壞情況下的時間復(fù)雜度為

O(n2)。

8快速排序在平均情況下的空間復(fù)雜度為O(log2n)，在最壞情況下的空間復(fù)雜度為

O(n) 。

9在快速排序方法中，進行每次劃分時，是從當(dāng)前待排序空間的 兩端 向 中間 依次查找出處于逆

序的元素并交換之,最后將基準(zhǔn)元素交換到一個確定位置,從而以該位置把當(dāng)前區(qū)間劃分為前后兩個子區(qū)間。

10假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的一次劃分的結(jié)果為[38 40]46[56

79 84]。

11假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序過程中，對應(yīng)二叉樹的深度為

4 ，分支點結(jié)點數(shù)為 4 。

12在二路歸并排中，對n個記錄進行歸并的趟數(shù)為 [log2n] 。

13在歸并排序中，進行每趟歸并的時間復(fù)雜度為O(n)，整個排序過程的時間復(fù)雜度為O(nlog2n)，

空間復(fù)雜度為 O(n) 。

14對20個記錄進行歸并排序時，共需要進行 5 趟歸并，在第三趟歸并時是把長度為 4 的有序表

兩兩歸并為長度為 8 的有序表。

15假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行歸并排序的過程中，第二趟歸并后的結(jié)果

為[38 46 56 79][40 84]。