數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題第章答案-文庫(kù)吧
2025-05-23 19:37 本頁(yè)面
【正文】 。答：比較、移動(dòng)。答：免去查找過(guò)程中每一步都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率。、_______、________、________、________。答：插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序、_______、________、________。答：直接插入排序、冒泡排序、歸并排序、基數(shù)排序、折半插入排序、_______、________、________。答：希爾排序、快速排序、簡(jiǎn)單選擇排序（直接選擇排序）、堆排序、樹(shù)形選擇排序、_______ ；不穩(wěn)定的排序方法有________、_______ 。四、簡(jiǎn)答題（共10分）。答：通過(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è)記錄為止。，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？（1）直接插入排序； （2）希爾排序； （3）快速排序；（4）堆排序； （5）歸并排序； （6）基數(shù)排序。答：（1）（5）（6）是穩(wěn)定的排序方法；（2）（3）（4）是不穩(wěn)定的排序方法。、簡(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) 快速排序 { 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 }? 什么是外排序?什么排序方法是穩(wěn)定的?什么排序方法是不穩(wěn)定的?答：內(nèi)排序是排序過(guò)程中參與排序的數(shù)據(jù)全部在內(nèi)存中所做的排序，排序過(guò)程中無(wú)需進(jìn)行內(nèi)外存數(shù)據(jù)傳送，決定排序方法時(shí)間性能的主要是數(shù)據(jù)排序碼的比較次數(shù)和數(shù)據(jù)對(duì)象的移動(dòng)次數(shù)。外排序是在排序的過(guò)程中參與排序的數(shù)據(jù)太多，在內(nèi)存中容納不下，因此在排序過(guò)程中需要不斷進(jìn)行內(nèi)外存的信息傳送的排序。決定外排序時(shí)間性能的主要是讀寫(xiě)磁盤次數(shù)和在內(nèi)存中總的記錄對(duì)象的歸并次數(shù)。不穩(wěn)定的排序方法主要有希爾排序、直接選擇排序、堆排序、快速排序。不穩(wěn)定的排序方法往往是按一定的間隔移動(dòng)或交換記錄對(duì)象的位置，從而可能導(dǎo)致具有相等排序碼的不同對(duì)象的前后相對(duì)位置在排序前后顛倒過(guò)來(lái)。其他排序方法中如果有數(shù)據(jù)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1