數(shù)據(jù)結(jié)構(gòu)復習題第章答案

1、第10章 內(nèi)部排序一、選擇題（每小題1分，共10分）1.從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后放在已排序序列的合適位置，該排序方法稱為（ A ）排序法。A.插入排序 B.選擇排序 C.希爾排序 D.二路歸并排序2.下列排序算法中( C )排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A.選擇 B.冒泡 C.歸并 D.堆3.若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為（ C ）。A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46, 79, 56,

2、 84 C. 40, 38， 46, 56, 79, 84 D. 40, 38, 46, 84, 56, 794.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ C ）。A.希爾排序 B.冒泡排序 C.插入排序 D.選擇排序5.為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是（ A ）。A. 順序存儲 B. 散列存儲 C. 鏈式存儲 D. 索引存儲6.若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為（ B ）。A. 79, 46, 56, 38, 40, 84

3、B. 84, 79, 56, 38, 40, 46 C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 38 7排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ C ）。 A希爾排序 B冒泡排序 C插入排序 D選擇排序 8在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（ D ）。A希爾排序 B冒泡排序 C直接插入排序 D直接選擇排序9堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列（ D ）是一個堆。A94,31,53,23,16,72 B94,53,31,72,16,23 C

4、16,53,23,94,31,72 D16,31,23,94,53,7210堆排序是一種（ B ）排序。 A 插入 B 選擇 C 交換 D 歸并 11（ D ）在鏈表中進行操作比在順序表中進行操作效率高。 A 順序查找 B 折半查找 C 分塊查找 D 插入 12直接選擇排序的時間復雜度為（ D ）。（n 為元素個數(shù)） AO(n) BO(log2 n) CO(nlog2 n) DO(n2 )二、判斷題（每小題1分，共10分）1.對于n個記錄的集合進行快速排序，所需要的平均時間是O(nlogn)。（ 對 ）2.（101，88，46，70，34，39，45，58，66，10）是堆。( 對 ) 3.如

5、果某種排序算法是不穩(wěn)定的則該方法沒有實際應(yīng)用價值。( × )4.外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進行排序，因此排序所花的時間取決于內(nèi)部排序的時間。 （× ）5.具有n個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。（ ）6. 在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序為穩(wěn)定排序。( )7.在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。( )8.冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（ × ）三、填空題（每空1分，共10分）1.不僅需要使用內(nèi)存，而

6、且還要使用外存的排序稱為 。答：外部排序2.若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關(guān)鍵字的 和記錄的 。答：比較、移動3.直接插入排序用監(jiān)視哨的作用是_。答：免去查找過程中每一步都要檢測整個表是否查找完畢，提高了查找效率。4.排序方法有_、_、_、_、_。答：插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序5.穩(wěn)定的排序方法有_、_、_、_。答：直接插入排序、冒泡排序、歸并排序、基數(shù)排序、折半插入排序6.不穩(wěn)定的排序方法有_、_、_、_。答：希爾排序、快速排序、簡單選擇排序（直接選擇排序）、堆排序、樹形選擇排序7.穩(wěn)定的排序方法有_、_ ；不穩(wěn)定的排序方法有_、_ 。四、簡

7、答題（共10分）1.簡述快速排序算法的基本思想。答：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。答案二：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），以該記錄作為標準，將所有記錄分成兩組，使第一組中各記錄的關(guān)鍵字都小于等于該標準關(guān)鍵字，而第二組中各記錄的值都大于等于該標準關(guān)鍵字，并把該記錄排放在這兩組的中間位置，這樣遍歷一趟文件后，將文件以該記錄為界分為兩部分，然后再對上面兩組分別重復上述過程，直到每一部分僅剩一個記錄為止。2.對于下列各種排序方法，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？（1

8、）直接插入排序； （2）希爾排序； （3）快速排序；（4）堆排序； （5）歸并排序； （6）基數(shù)排序。答：（1）（5）（6）是穩(wěn)定的排序方法；（2）（3）（4）是不穩(wěn)定的排序方法。3.希爾排序、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說明。答：(1) 希爾排序 512 275 275* 061 增量為2 275* 061 512 275 增量為1 061 275* 275 512 (2) 直接選擇排序 275 275* 512 061 i = 1 061 275* 512 275 i = 2 061 275* 512 275 i = 3 061 275* 275 512 (3)

9、 快速排序 512 275 275* 275* 275 512 (4) 堆排序 275 275* 061 170 已經(jīng)是最大堆，交換275與170 170 275* 061 275 對前3個調(diào)整 275* 170 061 275 前3個最大堆，交換275*與061 061 170 275* 275 對前2個調(diào)整 170 061 275* 275 前2個最大堆，交換170與061 061 170 275* 275 4.什么是內(nèi)排序? 什么是外排序?什么排序方法是穩(wěn)定的?什么排序方法是不穩(wěn)定的?答：內(nèi)排序是排序過程中參與排序的數(shù)據(jù)全部在內(nèi)存中所做的排序，排序過程中無需進行內(nèi)外存數(shù)據(jù)傳送，決定排序方

10、法時間性能的主要是數(shù)據(jù)排序碼的比較次數(shù)和數(shù)據(jù)對象的移動次數(shù)。外排序是在排序的過程中參與排序的數(shù)據(jù)太多，在內(nèi)存中容納不下，因此在排序過程中需要不斷進行內(nèi)外存的信息傳送的排序。決定外排序時間性能的主要是讀寫磁盤次數(shù)和在內(nèi)存中總的記錄對象的歸并次數(shù)。不穩(wěn)定的排序方法主要有希爾排序、直接選擇排序、堆排序、快速排序。不穩(wěn)定的排序方法往往是按一定的間隔移動或交換記錄對象的位置，從而可能導致具有相等排序碼的不同對象的前后相對位置在排序前后顛倒過來。其他排序方法中如果有數(shù)據(jù)交換，只是在相鄰的數(shù)據(jù)對象間比較排序碼，如果發(fā)生逆序(與最終排序的順序相反的次序)才交換，因此具有相等排序碼的不同對象的前后相對位置在排序

11、前后不會顛倒，是穩(wěn)定的排序方法。但如果把算法中判斷逆序的比較“>(或<)”改寫成“(或)”，也可能造成不穩(wěn)定。參考題：4.在什么條件下，MSD基數(shù)排序比LSD基數(shù)排序效率更高？答：由于高位優(yōu)先的MSD方法是遞歸的方法，就一般情況來說，不像低位優(yōu)先的LSD方法那樣直觀自然，而且實現(xiàn)的效率較低。但如果待排序的排序碼的大小只取決于高位的少數(shù)幾位而與大多數(shù)低位無關(guān)時，采用MSD方法比LSD方法的效率要高。5.堆排序是否是一種穩(wěn)定的排序方法？為什么？答：堆排序不是一種穩(wěn)定的排序方法。因為在堆調(diào)整的過程中，關(guān)鍵字進行比較和交換的所走路線是沿著根結(jié)點到葉子結(jié)點，因此對于相同的關(guān)鍵字就可能存在后面

12、的先被變換到前面。例如對于初始大J頂堆(2，1，)，第一遍堆調(diào)整為(,1)(2),因而堆排序不是穩(wěn)定的。6.在多關(guān)鍵字排序時，LSD和MSD兩種方法的特點是什么？答：最高位優(yōu)先（MSD）法：先對最高位關(guān)鍵字K0進行排序，將序列分成若干子序列，每個子序列中的記錄都具有相同的K0值，然后，分別就每個子序列對關(guān)鍵字K1進行排序，按K1值不同再分成若干更小的子序列，依次重復，直至最后對最低位關(guān)鍵字排序完成，將所有子序列依次連接在一起，成為一個有序子序列。最低位優(yōu)先（LSD）法：先對最低位關(guān)鍵字Kd-1進行排序，然后對高一級關(guān)鍵字Kd-2進行排序，依次重復，直至對最高位關(guān)鍵字K0排序后便成為一個有序序列

13、。進行排序時，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序，但對Ki (0<=i<d-1)排序時，只能用穩(wěn)定的排序方法。另一方面，按LSD進行排序時，可以不通過關(guān)鍵字比較實現(xiàn)排序，而是通過若干次“分配”和“收集”來實現(xiàn)排序。五、應(yīng)用題（共40分）1.已知序列503，87，512，61，908，170，897，275，652，462，采用基數(shù)排序法對該序列作升序排序時的每一趟的結(jié)果。答案依題意，采用基數(shù)排序法排序的各趟的結(jié)果如下：初始：503，87，512，61，908，170，897，275，652，462第1趟（按個位排序）：170，61，512，652，462，503，27

14、5，87，897，908 第2趟（按十為排序）：503，908，512，652，61，462，170，275，87，897第3趟（按百為排序）：61，87，170，275，462，503，512，652，897，9082.寫出快速排序的思想，并寫出序列（49，38，65，97，76，13，27，50）第一趟快速排序的過程。3.對一組記錄（54，38，96，23，15，72，60，45，83）執(zhí)行希爾排序（D=5，3，1），記錄每一趟排序結(jié)果。4.給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18) 執(zhí)行希爾排序（D=6，3，1），記錄每一趟排序結(jié)果。5.對一組記錄（5

15、4，38，96，23，15，72，60，45，83）執(zhí)行冒泡排序，記錄每一趟排序結(jié)果。6.已知一組元素的排序碼為（36，25，48，12，65，20），寫出用直接插入排序法每次向前面有序表插入一個元素后的排列結(jié)果。7.寫出關(guān)鍵字序列（265,301,751,129,937,863,742,694,076,438）執(zhí)行簡單選擇排序方法各趟結(jié)束時的序列狀態(tài)。8.寫出用堆排序算法對(29，18，25，47，58，12，51，10)進行排序時，初始堆及以后每挑好一個元素重新調(diào)整后堆的狀態(tài)。9.判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）。（1）100，85，98，77，

16、80，60，82，40，20，10，66（2）100，85，40，77，80，60，66，98，82，10，20（3）10，20，40，60，66，77，80， 82，85，98，10010.畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。11. 已知序列503，87，512，61，908，170，897，275 ，653，462 ，請給出采用希爾排序法對該序列作升序排序時每一趟的結(jié)果。12.試說明歸并排序的基本過程，并給出對關(guān)鍵字序列47，33，6l，82，72，l1，25，57進行兩路歸并排序的示意。13.給出一組關(guān)鍵字T=(12,2,16,30,8,28,4

17、,10,20,6,18).寫出用下列算法從小到大排序時第一趟結(jié)束時的序列。(1)希爾排序(第一趟排序的增量為5)(2)快速排序(選第一個記錄為樞軸(分隔)(3)鏈式基數(shù)排序(基數(shù)為10)14.給出一組關(guān)鍵字：28，07，39，10，65，14，61，17，50，21，寫出按起泡排序方法進行排序的過程。15.判別序列（12，70，33，65，24，56，48，92，86，33）是否為堆，如果不是，則把它調(diào)整為堆，試給出堆排序方法在平均時間性能最壞情況下的時間性能和輔助存儲量，并與快速排序方法在以上三方面進行比較六、算法題（共12分）1.（6分）編寫起泡排序的算法。答案一：void BubbleS

18、ort(Elem R , int n) i = n; while (i >1) lastExchangeIndex = 1;for (j = 1; j < i; j+) if (Rj+1.key < Rj.key) Swap(Rj, Rj+1); / temp=Rj ; Rj= Rj+1; Rj+1= temp; lastExchangeIndex = j; /記下進行交換的記錄位置 /ifi = lastExchangeIndex; / 本趟進行過交換的最后一個記錄的位置 / while / BubbleSort答案二：見教材16頁答案三：void paixu(int a,

19、int n)for(i=0;i<n;i+) scanf ("%d,",&ai); for(j=0;j<=9;j+) for (i=0;i<10-j;i+) 2分 if (ai>ai+1) temp=ai; ai=ai+1; ai+1=temp; 6分for(i=1;i<11;i+) printf("%5d,",ai ); printf("n"); 2.（6分）寫出一趟快速排序的算法。答案一：int partition(sqlist L, int low, int high) L.r0=L.rlow

20、; pivotkey=L.rlow.key; 1分 while(low<high)while(low<high&&L.rhigh.key>=pivotdey) high; L.rlow=L.rhigh; 3分 while(low<high&&L.rlow.key<=pivotkey) +low; L.rhigh=L.rlow; 5分L.rlow=L.r0;return low; 7分答案二：（也可以使用教材274頁算法10.6a）int Partition (RedType &R, int low, int high) pi

21、votkey = Rlow.key; while (low<high) while (low<high && Rhigh.key>=pivotkey) -high; RlowRhigh; while (low<high && Rlow.key<=pivotkey) +low; RlowRhigh; return low; / 返回標準（樞軸）所在位置 / Partition3.（6分）編寫直接插入排序的算法。void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=

22、2; i<=L.length; +i ) if (L.ri.key < L.ri-1.key) L.r0 = L.ri; / 復制為監(jiān)視哨for ( j=i-1; L.r0.key < L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置 / InsertSort4.（6分）編寫折半插入排序的算法。void BiInsertionSort ( SqList &L ) for ( i=2; i<=L.length; +i ) L.r0 = L.ri; / 將 L.ri 暫存到 L.r0low = 1; high = i-1;while (low<=high)