數(shù)據(jù)結(jié)構(gòu)復(fù)習題第章答案(編輯修改稿)
2025-07-04 19:37 本頁面
【文章內(nèi)容簡介】 交換，只是在相鄰的數(shù)據(jù)對象間比較排序碼，如果發(fā)生逆序(與最終排序的順序相反的次序)才交換，因此具有相等排序碼的不同對象的前后相對位置在排序前后不會顛倒，是穩(wěn)定的排序方法。但如果把算法中判斷逆序的比較“(或)”改寫成“≥(或≤)”，也可能造成不穩(wěn)定。參考題：，MSD基數(shù)排序比LSD基數(shù)排序效率更高？答：由于高位優(yōu)先的MSD方法是遞歸的方法，就一般情況來說，不像低位優(yōu)先的LSD方法那樣直觀自然，而且實現(xiàn)的效率較低。但如果待排序的排序碼的大小只取決于高位的少數(shù)幾位而與大多數(shù)低位無關(guān)時，采用MSD方法比LSD方法的效率要高。？為什么？答：堆排序不是一種穩(wěn)定的排序方法。因為在堆調(diào)整的過程中，關(guān)鍵字進行比較和交換的所走路線是沿著根結(jié)點到葉子結(jié)點，因此對于相同的關(guān)鍵字就可能存在后面的先被變換到前面。例如對于初始大J頂堆(2，1，)，第一遍堆調(diào)整為(,1)(2),因而堆排序不是穩(wěn)定的。，LSD和MSD兩種方法的特點是什么？答：最高位優(yōu)先（MSD）法：先對最高位關(guān)鍵字K0進行排序，將序列分成若干子序列，每個子序列中的記錄都具有相同的K0值，然后，分別就每個子序列對關(guān)鍵字K1進行排序，按K1值不同再分成若干更小的子序列，……，依次重復(fù)，直至最后對最低位關(guān)鍵字排序完成，將所有子序列依次連接在一起，成為一個有序子序列。最低位優(yōu)先（LSD）法：先對最低位關(guān)鍵字Kd1進行排序，然后對高一級關(guān)鍵字Kd2進行排序，依次重復(fù)，直至對最高位關(guān)鍵字K0排序后便成為一個有序序列。進行排序時，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序，但對Ki (0=id1)排序時，只能用穩(wěn)定的排序方法。另一方面，按LSD進行排序時，可以不通過關(guān)鍵字比較實現(xiàn)排序，而是通過若干次“分配”和“收集”來實現(xiàn)排序。五、應(yīng)用題（共40分）{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，275，87，897，908 第2趟（按十為排序）：503，908，512，652，61，462，170，275，87，897第3趟（按百為排序）：61，87，170，275，462，503，512，652，897，908，并寫出序列（49，38，65，97，76，13，27，50）第一趟快速排序的過程。（54，38，96，23，15，72，60，45，83）執(zhí)行希爾排序（D=5，3，1），記錄每一趟排序結(jié)果。=(12,2,16,30,8,28,4,10,20,6,18) 執(zhí)行希爾排序（D=6，3，1），記錄每一趟排序結(jié)果。（54，38，96，23，15，72，60，45，83）執(zhí)行冒泡排序，記錄每一趟排序結(jié)果。（36，25，48，12，65，20），寫出用直接插入排序法每次向前面有序表插入一個元素后的排列結(jié)果。（265,301,751,129,937,863,742,694,076,438）執(zhí)行簡單選擇排序方法各趟結(jié)束時的序列狀態(tài)。(29，18，25，47，58，12，51，10)進行排序時，初始堆及以后每挑好一個元素重新調(diào)整后堆的狀態(tài)。（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）。（1）100，85，98，77，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，100, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。11. 已知序列{503，87，512，61，908，170，8
教學教案相關(guān)推薦
鄂ICP備17016276號-1