一、填空題

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

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

排序。

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

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

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

雜度為 O(n) 。

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

需要對(duì)樹根結(jié)點(diǎn)進(jìn)行n-1次篩運(yùn)算。

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

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

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

38,40,46)。

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

O(n2)。

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

O(n) 。

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

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

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

79 84]。

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

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

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

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

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

14對(duì)20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行 5 趟歸并，在第三趟歸并時(shí)是把長(zhǎng)度為 4 的有序表

兩兩歸并為長(zhǎng)度為 8 的有序表。

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

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