1、填空題,1. 大多數(shù)排序算法都有兩個基本的操作： 2. 在對一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置至少需比較 次。 3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 ；若初始數(shù)據(jù)基本反序，則選用 。,比較和移動,3,插入,選擇,填空題,4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 ；若初始記錄基本無序，則最好選用 。 5.內(nèi)部排序依排序方式可分為_、 和_。 6對n個元素的序列進(jìn)行冒泡排序時，最少的比較次數(shù)是 最多的比較次數(shù) 。,堆,快速,插入、選擇、交換,n-1,n(n-1)/2

2、,填空題,7一組記錄元素的關(guān)鍵碼為75,84,26,33,92,15，則利用快速排序的方法，以第一個記錄為樞紐值得到的一次劃分結(jié)果是： 8設(shè)表中元素的初態(tài)是按鍵值遞增的，若分別用堆排序、快速排序、冒泡排序方法對其仍按遞增排序進(jìn)行排序，則_ 最省時間，_最費(fèi)時間。 9從一個無序序列建立一個堆的方法；首先將要排序的所有鍵值分放到一棵_ _的各個結(jié)點(diǎn)中，然后從i=_的結(jié)點(diǎn)ki開始，逐步把以Ki-1、Ki-2、。、K1為根的子樹排成堆，直到以K1為根的樹排成堆，就完成了建堆的過程。,15,33,26,75,92,84,冒泡,快速,完全二叉樹,n/2,填空題,10_方法是對序列中的元素通過適當(dāng)?shù)奈恢媒粨Q

3、將有關(guān)元素一次性地放置在其最終位置上。 11.對n個記錄的表r1.n進(jìn)行簡單選擇排序,所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為( ),快速排序,n(n-1)/2,單選題,1 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（ ） . 希爾排序 . 冒泡排序 . 插入排序 . 選擇排序 2從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（ ） . 希爾排序 . 歸并排序 . 插入排序 . 選擇排序,C,D,單選題,3對個不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（ ） . 從小到大排

4、列好的 . 從大到小排列好的 . 元素?zé)o序 . 元素基本有序 4對個不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（ ） . n+1 . n . n-1 . n(n-1)/2,C,D,單選題,5快速排序在下列哪種情況下最易發(fā)揮其長處。（ ） . 被排序的數(shù)據(jù)中含有多個相同排序碼 . 被排序的數(shù)據(jù)已基本有序 . 被排序的數(shù)據(jù)完全無序 . 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊 6若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ） . 38, 40, 46, 56, 79, 84 . 40, 38, 4

5、6 , 79, 56, 84 . 40, 38，46, 56, 79, 84 . 40, 38, 46, 84, 56, 79,C,C,單選題,7下列關(guān)鍵字序列中， 是堆。（ ） . 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 72 8堆是一種 排序。（ ） . 插入 .選擇 . 交換 . 歸并 9堆的形狀是一棵 （ ） . 二叉排序樹 .滿二叉樹 . 完全二叉樹 . 平衡二叉樹,D,B,C,單選題,10若一組記錄的排序碼為（46, 79, 56, 3

6、8, 40, 84），則利用堆排序的方法建立的初始堆為（ ） . 79, 46, 56, 38, 40, 84 . 84, 79, 56, 38, 40, 46 . 84, 79, 56, 46, 40, 38 . 84, 56, 79, 40, 46, 38 11、如果只想得到1024個元素序列中第5個最小元素之前的部分排序的序列，用（）方法最快。 A.起泡排序 B.快速排序 C.簡單選擇排序 D.堆排序,B,D,單選題,12.如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。 A.插入排序 B.快速排序 C.冒泡

7、排序 D.合并排序 13.下列排序方法中，哪一種方法的比較次數(shù)與記錄的初始排列狀態(tài)無關(guān)？（） A.插入排序 B.冒泡排序 C.快速排序 D.選擇排序,B,D,單選題,14.下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是( )。 A. 冒泡排序 B. 快速排序 C. 插入排序 D. 希爾排序 15.若對n個元素進(jìn)行直接插入排序,則進(jìn)行第I趟排序過程前,有序表中的元素個數(shù)為( ) (A)i (B)I+1 (C)I-1 (D)1 16.在對n個元素進(jìn)行直接選擇排序過程中,第I趟需從( )個元素中選擇出最小值元素. (A)n-I+1 (B)n-I (C)I (D)I+1,

8、A,A,A,單選題,17若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（） A 快速排序B 堆排序 C 歸并排序D 直接插入排序 18、在下列算法中，（）算法可能出現(xiàn)下列情況：在最后一趟開始之前，有的元素不在其最終的位置上。 A 堆排序 B 冒泡排序 C 插入排序 D 快速排序,C,C,單選題,19、對給出的一組關(guān)鍵字14,5,19,20,11,19。若按關(guān)鍵字非遞減排序，第一趟排序結(jié)果為14,5,19,20,11,19，問采用的排序算法是（） A 簡單選擇排序 B 快速排序 C 希爾排序 D 二路歸并排序,C,簡答題,1判別序列（12，70，33，65，24，56，48，92，