數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題第章答案-免費(fèi)閱讀
【正文】 else R2[k] = R[j]。 ++i) { // 選擇第 i 小的記錄，并交換到位j = SelectMinKey(R, i)。 // 插入點(diǎn)在高半?yún)^(qū)}//在 [1..i1]中折半查找插入位置；for ( j=i1。L ) {for ( i=2。 i=。amp。return low。amp。} } 6分for(i=1。a[i])。 // temp=R[j] 。=(12,2,16,30,8,28,4,10,20,6,18).寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（54，38，96，23，15，72，60，45，83）執(zhí)行冒泡排序，記錄每一趟排序結(jié)果。，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è)有序子序列。不穩(wěn)定的排序方法往往是按一定的間隔移動(dòng)或交換記錄對(duì)象的位置，從而可能導(dǎo)致具有相等排序碼的不同對(duì)象的前后相對(duì)位置在排序前后顛倒過(guò)來(lái)。答案二：在待排序的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è)記錄為止。答：比較、移動(dòng)。( 對(duì) ) ．則該方法沒(méi)有實(shí)際應(yīng)用價(jià)值。 A．希爾排序 B．冒泡排序 C．插入排序 D．選擇排序 8．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是（ D ）。第10章 內(nèi)部排序一、選擇題（每小題1分，共10分），然后放在已排序序列的合適位置，該排序方法稱為（ A ）排序法。
A．希爾排序 B．冒泡排序 C．直接插入排序 D．直接選擇排序9．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。( )，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。答：免去查找過(guò)程中每一步都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率。，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？（1）直接插入排序； （2）希爾排序； （3）快速排序；（4）堆排序； （5）歸并排序； （6）基數(shù)排序。其他排序方法中如果有數(shù)據(jù)交換，只是在相鄰的數(shù)據(jù)對(duì)象間比較排序碼，如果發(fā)生逆序(與最終排序的順序相反的次序)才交換，因此具有相等排序碼的不同對(duì)象的前后相對(duì)位置在排序前后不會(huì)顛倒，是穩(wěn)定的排序方法。最低位優(yōu)先（LSD）法：先對(duì)最低位關(guān)鍵字Kd1進(jìn)行排序，然后對(duì)高一級(jí)關(guān)鍵字Kd2進(jìn)行排序，依次重復(fù)，直至對(duì)最高位關(guān)鍵字K0排序后便成為一個(gè)有序序列。（36，25，48，12，65，20），寫(xiě)出用直接插入排序法每次向前面有序表插入一個(gè)元素后的排列結(jié)果。(1)希爾排序(第一趟排序的增量為5)(2)快速排序(選第一個(gè)記錄為樞軸(分隔))(3)鏈?zhǔn)交鶖?shù)排序(基數(shù)為10)：28，07，39，10，65，14，61，17，50，21，寫(xiě)出按起泡排序方法進(jìn)行排序的過(guò)程。 R[j]= R[j+1]。 for(j=0。i11。[high].key=pivotdey) –high。 7分}答案二：（）int Part
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1