數(shù)據(jù)結(jié)構(gòu)單元練習(xí)10

1、單元測(cè)驗(yàn)單元測(cè)驗(yàn)1010一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打√；錯(cuò)誤的打；錯(cuò)誤的打╳）（ㄨ）（1）如果某種排序算法不穩(wěn)定，則該排序方法就沒(méi)有實(shí)用價(jià)值。（√）（2）希爾排序是不穩(wěn)定的排序。（ㄨ）（3）冒泡排序是不穩(wěn)定的排序。（√）（4）對(duì)n個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog2n)。（ㄨ）（5）堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。（√）（6）當(dāng)待排序的元素個(gè)數(shù)很多時(shí)，

2、為了交換元素的位置要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（ㄨ）（7）快速排序在任何情況下都比其它排序方法速度快。（√）（8）對(duì)快速排序來(lái)說(shuō)，初始序列為正序或反序都是最壞情況。（√）（9）采用歸并排序可以實(shí)現(xiàn)外排序。（√）（10）采用希爾方法排序時(shí)，若關(guān)鍵字的排列雜亂無(wú)序，則效率最高。二填空題二填空題（1）大多數(shù)排序算法都有兩個(gè)基本的操作：比較和移動(dòng)。（2）評(píng)價(jià)排序算法優(yōu)劣的主要標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和算法所需的附加空間。（3）根據(jù)被

3、處理的數(shù)據(jù)在計(jì)算機(jī)中使用不同的存儲(chǔ)設(shè)備，排序可分為：內(nèi)排序和外排序。（4）外排序是指在排序過(guò)程中，數(shù)據(jù)的主要部分存放在計(jì)算機(jī)的外存中。（5）對(duì)n個(gè)關(guān)鍵字進(jìn)行冒泡排序，其可能的最小比較次數(shù)為：n1次。（6）在最壞情況下，在第i趟直接插入排序中，要進(jìn)行i1次關(guān)鍵字的比較。（7）對(duì)n個(gè)關(guān)鍵字進(jìn)行冒泡排序，時(shí)間復(fù)雜度為O(n2)。（8）快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n2)。（9）對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間為：O(l

4、og2n)。（10）對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的附加空間是O(n)。（11）若原始數(shù)據(jù)接近無(wú)序，則選用快速排序最好。（12）在排序前，關(guān)鍵字值相等的不同記錄，排序后相對(duì)位置保持不變的排序方法，稱(chēng)為穩(wěn)定排序方法。（13）在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序較好。（14）當(dāng)增量為1時(shí)，該趟希爾排序與直接插入排序基本一致。（15）第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。（16）依次將

5、每個(gè)記錄插入到一個(gè)有序的子文件中的排序方法稱(chēng)為直接插入排序。（17）在插入排序、選擇排序和歸并排序中，排序是不穩(wěn)定的為：選擇排序。（18）在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較3次。（19）兩個(gè)序列分別為：L1=25，57，48，37，92，86，12，33（15）對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（B）。A

6、O(n)BO(n2)CO(nlog2n)DO(n3)（16）冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（C）次。A1B2Cn1Dn（17）對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡（遞增）排序，在下列（B）情況比較的次數(shù)最多。A從小到大排列好的B從大到小排列好的C元素?zé)o序D元素基本有序（18）用直接插入排序法對(duì)下面的四個(gè)序列進(jìn)行由小到大的排序，元素比較次數(shù)最少的是（B）。A，94，32，40，90，80，46，21，69B21，32，46，

7、40，80，69，90，94C32，40，21，46，69，94，90，80D90，69，80，46，21，32，94，40（19）一組記錄的排序碼為(25，48，16，35，79，82，23，40)，其中含有4個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為：（A）。A，16253548234079823672B16253548798223364072C16254835798223364072D16253548792

8、336407282（20）一個(gè)數(shù)據(jù)序列的關(guān)鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個(gè)數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為：（C）A（38，40，46，56，79，84）B（40，38，46，79，56，84）C（40，38，46，56，79，84）D（40，38，46，79，56，84）四排序過(guò)程分析四排序過(guò)程分析1已知數(shù)據(jù)序列10，8，18，15，7，16，寫(xiě)出采用直接插入算法排序時(shí)，每一趟排序的結(jié)果。解：10

9、81815716第一趟結(jié)束時(shí)結(jié)果：[810]1815716第二趟結(jié)束時(shí)結(jié)果：[81018]15716第三趟結(jié)束時(shí)結(jié)果：[8101518]716第四趟結(jié)束時(shí)結(jié)果：[78101518]16第五趟結(jié)束時(shí)結(jié)果：[7810151618]2已知數(shù)據(jù)序列18，17，60，40，07，32，73，65，寫(xiě)出采用直接插入算法排序時(shí)，每一趟排序的結(jié)果。解：1817604007327365第一趟結(jié)束時(shí)結(jié)果：[1718]604007327365第二趟結(jié)束時(shí)結(jié)果