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

1、第10章 內(nèi)部排序一、選擇題（每小題1分，共10分）1.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后放在已排序序列的合適位置，該排序方法稱(chēng)為（ A ）排序法。A.插入排序 B.選擇排序 C.希爾排序 D.二路歸并排序2.下列排序算法中( C )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A.選擇 B.冒泡 C.歸并 D.堆3.若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(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.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為（ C ）。A.希爾排序 B.冒泡排序 C.插入排序 D.選擇排序5.為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是（ A ）。A. 順序存儲(chǔ) B. 散列存儲(chǔ) C. 鏈?zhǔn)酱鎯?chǔ) D. 索引存儲(chǔ)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排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為（ C ）。 A希爾排序 B冒泡排序 C插入排序 D選擇排序 8在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是（ D ）。A希爾排序 B冒泡排序 C直接插入排序 D直接選擇排序9堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列（ D ）是一個(gè)堆。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 ）在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。 A 順序查找 B 折半查找 C 分塊查找 D 插入 12直接選擇排序的時(shí)間復(fù)雜度為（ D ）。（n 為元素個(gè)數(shù)） AO(n) BO(log2 n) CO(nlog2 n) DO(n2 )二、判斷題（每小題1分，共10分）1.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(nlogn)。（ 對(duì) ）2.（101，88，46，70，34，39，45，58，66，10）是堆。( 對(duì) ) 3.如

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

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

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

8、）直接插入排序； （2）希爾排序； （3）快速排序；（4）堆排序； （5）歸并排序； （6）基數(shù)排序。答：（1）（5）（6）是穩(wěn)定的排序方法；（2）（3）（4）是不穩(wěn)定的排序方法。3.希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法，試舉例說(shuō)明。答：(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 對(duì)前3個(gè)調(diào)整 275* 170 061 275 前3個(gè)最大堆，交換275*與061 061 170 275* 275 對(duì)前2個(gè)調(diào)整 170 061 275* 275 前2個(gè)最大堆，交換170與061 061 170 275* 275 4.什么是內(nèi)排序? 什么是外排序?什么排序方法是穩(wěn)定的?什么排序方法是不穩(wěn)定的?答：內(nèi)排序是排序過(guò)程中參與排序的數(shù)據(jù)全部在內(nèi)存中所做的排序，排序過(guò)程中無(wú)需進(jìn)行內(nèi)外存數(shù)據(jù)傳送，決定排序方

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

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

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

13、。進(jìn)行排序時(shí)，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序，但對(duì)Ki (0<=i<d-1)排序時(shí)，只能用穩(wěn)定的排序方法。另一方面，按LSD進(jìn)行排序時(shí)，可以不通過(guò)關(guān)鍵字比較實(shí)現(xiàn)排序，而是通過(guò)若干次“分配”和“收集”來(lái)實(shí)現(xiàn)排序。五、應(yīng)用題（共40分）1.已知序列503，87，512，61，908，170，897，275，652，462，采用基數(shù)排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。答案依題意，采用基數(shù)排序法排序的各趟的結(jié)果如下：初始：503，87，512，61，908，170，897，275，652，462第1趟（按個(gè)位排序）：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.寫(xiě)出快速排序的思想，并寫(xiě)出序列（49，38，65，97，76，13，27，50）第一趟快速排序的過(guò)程。3.對(duì)一組記錄（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.對(duì)一組記錄（5

15、4，38，96，23，15，72，60，45，83）執(zhí)行冒泡排序，記錄每一趟排序結(jié)果。6.已知一組元素的排序碼為（36，25，48，12，65，20），寫(xiě)出用直接插入排序法每次向前面有序表插入一個(gè)元素后的排列結(jié)果。7.寫(xiě)出關(guān)鍵字序列（265,301,751,129,937,863,742,694,076,438）執(zhí)行簡(jiǎn)單選擇排序方法各趟結(jié)束時(shí)的序列狀態(tài)。8.寫(xiě)出用堆排序算法對(duì)(29，18，25，47，58，12，51，10)進(jìn)行排序時(shí)，初始堆及以后每挑好一個(gè)元素重新調(diào)整后堆的狀態(tài)。9.判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請(qǐng)將它們調(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.畫(huà)出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。11. 已知序列503，87，512，61，908，170，897，275 ，653，462 ，請(qǐng)給出采用希爾排序法對(duì)該序列作升序排序時(shí)每一趟的結(jié)果。12.試說(shuō)明歸并排序的基本過(guò)程，并給出對(duì)關(guān)鍵字序列47，33，6l，82，72，l1，25，57進(jìn)行兩路歸并排序的示意。13.給出一組關(guān)鍵字T=(12,2,16,30,8,28,4

17、,10,20,6,18).寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。(1)希爾排序(第一趟排序的增量為5)(2)快速排序(選第一個(gè)記錄為樞軸(分隔)(3)鏈?zhǔn)交鶖?shù)排序(基數(shù)為10)14.給出一組關(guān)鍵字：28，07，39，10，65，14，61，17，50，21，寫(xiě)出按起泡排序方法進(jìn)行排序的過(guò)程。15.判別序列（12，70，33，65，24，56，48，92，86，33）是否為堆，如果不是，則把它調(diào)整為堆，試給出堆排序方法在平均時(shí)間性能最壞情況下的時(shí)間性能和輔助存儲(chǔ)量，并與快速排序方法在以上三方面進(jìn)行比較六、算法題（共12分）1.（6分）編寫(xiě)起泡排序的算法。答案一：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; /記下進(jìn)行交換的記錄位置 /ifi = lastExchangeIndex; / 本趟進(jìn)行過(guò)交換的最后一個(gè)記錄的位置 / while / BubbleSort答案二：見(jiàn)教材16頁(yè)答案三：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分）寫(xiě)出一趟快速排序的算法。答案一：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頁(yè)算法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; / 返回標(biāo)準(zhǔn)（樞軸）所在位置 / Partition3.（6分）編寫(xiě)直接插入排序的算法。void InsertionSort ( SqList &L ) / 對(duì)順序表 L 作直接插入排序。 for ( i=

22、2; i<=L.length; +i ) if (L.ri.key < L.ri-1.key) L.r0 = L.ri; / 復(fù)制為監(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分）編寫(xiě)折半插入排序的算法。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)