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

數(shù)據(jù)結(jié)構(gòu)單元10練習(xí)參照數(shù)據(jù)結(jié)構(gòu)單元10練習(xí)參照9/9數(shù)據(jù)結(jié)構(gòu)單元10練習(xí)參照O（n2）。單元測(cè)試10一．判斷題（以下各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打√；錯(cuò)誤的打

╳）（ㄨ）（1）若是某種排序算法不牢固，則該排序方法就【沒】有合用價(jià)值。（√）（2）希爾排序是不牢固的排序。（ㄨ）（3）冒泡排序是【不】牢固的排序。（√）（4）對(duì)n個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog2n)。（ㄨ）（5）堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)【無(wú)】相關(guān)。（√）（6）當(dāng)待排序的元素個(gè)數(shù)很多時(shí)，為了交換元素的地址要占用很多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（ㄨ）（7）快速排序不是在任何情況下都比其余排序方法速度快。（√）（8）對(duì)快速排序來(lái)說，初始序列為正序或反序都是最壞情況。（√）（9）采用歸并排序可以實(shí)現(xiàn)外排序。（√）（10）采用希爾方法排序時(shí)，若要點(diǎn)字的排列紛亂無(wú)序，則效率最高（√）（11）快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最后地址上。（√）（12）冒泡排序的時(shí)間復(fù)雜度是二．填空題（1）大多數(shù)排序算法都有兩個(gè)基本的操作：比較和搬動(dòng)。（2）議論排序算法利害的主要標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和算法所需的附加空間。（3）依照被辦理的數(shù)據(jù)在計(jì)算機(jī)中使用不相同的儲(chǔ)藏設(shè)備，排序可分為：內(nèi)排序和外排序。（4）外排序是指在排序過程中，數(shù)據(jù)的主要部分存放在計(jì)算機(jī)的外存中。（5）對(duì)n個(gè)要點(diǎn)字進(jìn)行冒泡排序，其可能的最小比較次數(shù)為：n-1次。（6）在最壞情況下，在第i趟直接插入排序中，要進(jìn)行i-1次要點(diǎn)字的比較。（7）對(duì)n個(gè)要點(diǎn)字進(jìn)行冒泡排序，時(shí)間復(fù)雜度為O(n2)。（8）快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n2)。（9）對(duì)于n個(gè)記錄的會(huì)集進(jìn)行歸并排序，所需要的平均時(shí)間為：O(logn)。2（10）對(duì)于n個(gè)記錄的會(huì)集進(jìn)行歸并排序，所需要的附加空間是O(n)。（11）若原始數(shù)據(jù)湊近無(wú)序，則采用快速排序最好。（12）在排序前，要點(diǎn)字值相等的不相同記錄，排序后相對(duì)地址保持不變的排序方法，稱為穩(wěn)定排序方法。（13）在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則采用插入排序較好。（14）當(dāng)增量為1時(shí)，該趟希爾排序與直接插入排序基本一致。（15）第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。（16）依次將每個(gè)記錄插入到一個(gè)有序的子文件中的排序方法稱為直接插入排序。（17）在插入排序、選擇排序和歸并排序中，排序是不牢固的為：選擇排序。（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}L2={25，37，33，12，48，57，86，92}。用冒泡排序法對(duì)L1和L2進(jìn)行排序，交換次數(shù)較少的是序列：L2。（20）對(duì)一組記錄（54，35，96，21，12，72，60，44，80）進(jìn)行直接選擇排序時(shí)，第四次選擇和交換后，未排序記錄是54，72，60，96，80。三．選擇題（1）排序是依照（A．要點(diǎn)字

AB

）的大小重新安排各元素的次序。．?dāng)?shù)組C．元素件

D

．結(jié)點(diǎn)（2）議論排序算法利害的標(biāo)準(zhǔn)主若是（

D）。A．執(zhí)行時(shí)間

B

．輔助空間C．算法自己的復(fù)雜度

D

．執(zhí)行時(shí)間和所需的輔助空間（3）直接插入排序的方法是（

B）的排序方法。A．不牢固

B

．牢固

C

．外面

D

．選擇（4）直接插入排序的方法要求被排序的數(shù)據(jù)（

B）儲(chǔ)藏。A．必定鏈表

B

．必定次序

C．次序或鏈表

D．可以任意（5）排序方法中，從無(wú)序序列中選擇要點(diǎn)字最小的記錄，將其與無(wú)序區(qū)（初始為空）的第一個(gè)記錄交換的排序方法，稱為(D)。A．希爾排序B．歸并排序C．插入排序D.選擇排序（6）每次把待排序方的區(qū)間劃分為左、右兩個(gè)區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法叫做（

C）。A．冒泡排序

B

．堆排序

C

．快速排序

D.

歸并排序（7）快速排序在（C）情況下最易發(fā)揮其長(zhǎng)處。A．待排序的數(shù)據(jù)中含有多個(gè)相同的要點(diǎn)字B．待排序的數(shù)據(jù)已基本有序C．待排序的數(shù)據(jù)完好無(wú)序D．待排序的數(shù)據(jù)中最大值與最小值相差懸殊（8）下述幾種排序方法中，要求內(nèi)存量最大的是：（D）。A．插入排序B．選擇排序C．快速排序D.歸并排序（9）直接插入排序的方法是從第（B）個(gè)元素開始，插入到前邊合適地址的排序方法。A．1B．2C．3D．n（10）堆的形狀是一棵（C）。A．二叉排序樹B．滿二叉樹C．完好二叉樹D．平衡二叉樹（11）內(nèi)排序是指在排序的整個(gè)過程中，全部數(shù)據(jù)都在計(jì)算機(jī)的（A）中完成的排序。A．內(nèi)存B．外存C．內(nèi)存和外存D．存放器（12）快速排序的方法是（A）的排序方法。A．不牢固B．牢固C．外面D．選擇（13）以下排序方法中，要點(diǎn)字比較次數(shù)與記錄的初始排列次序沒關(guān)的是（A）。A．選擇排序B．希爾排序C．插入排序D．冒泡排序（14）下述幾種排序方法中，平均時(shí)間復(fù)雜度最小的是（A）。A．希爾排序B．插入排序C．冒泡排序D．選擇排序（15）對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（B）。A．O(n)B2C．O(nlog2n)D3．O(n)．O(n)（16）冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（C）次。A．1B．2C．n-1D．n（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，69B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80D．90，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，16253548234079823672B．16253548798223364072C．16254835798223364072D．1625354879233640728220）一個(gè)數(shù)據(jù)序列的要點(diǎ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）四．排序過程解析1．已知數(shù)據(jù)序列{18，17，60，40，07，32，73，65}，寫出采用直接插入算法排序時(shí)，每一趟排序的結(jié)果。解：1817604007327365第一趟結(jié)束時(shí)結(jié)果：[1718]604007327365第二趟結(jié)束時(shí)結(jié)果：[171860]4007327365第三趟結(jié)束時(shí)結(jié)果：[17184060]07327365第四趟結(jié)束時(shí)結(jié)果：[0717184060]327365第五趟結(jié)束時(shí)結(jié)果：[071718324060]7365第六趟結(jié)束時(shí)結(jié)果：[07171832406073]65第七趟結(jié)束時(shí)結(jié)果：[0717183240606573]已知數(shù)據(jù)序列{17，18，60，40，7，32，73，65，85}請(qǐng)寫出采用冒泡排序法對(duì)該序列作升序排序時(shí)每一趟的結(jié)果。解：17186040732736585第一趟排序結(jié)果：17184073260657385第二趟排序結(jié)果：171873240606573第三趟排序結(jié)果：1771832406065第四趟排序結(jié)果：71718324060第五趟排序結(jié)果：717183240第五趟排序過程中已無(wú)記錄交換，排序結(jié)束。3．已知數(shù)據(jù)序列{10，18，4，3，6，12，9，15，8}，寫出希爾排序每一趟（設(shè)d=4、2、1）排序的結(jié)果。解：1018436129158d=46124381891510d=24361281591810d=134689101215184．已知數(shù)據(jù)序列{12，02，16，30，28，10，17，20，06，18}，寫出希爾排序每一趟排序的結(jié)果。（設(shè)d=5、2、1）解：12021630281017200618d=510021606181217203028d=212021606171218203028d=1020610121617182028305．已知數(shù)據(jù)序列{10，18，4，3，6，12，9，15}，寫出二路歸并排序的每一趟排序結(jié)果。[10][18][4][3][6][12][9][15][1018][34][612][915]第一趟排序結(jié)果[341018][691215]第二趟排序結(jié)果[346910121518]第三趟排序結(jié)果6．已知數(shù)據(jù)序列{10，1，15，18，7，15}，試畫出采用快速排序法，第一趟排序的結(jié)果。解1011518715lowhigh交換711518[10]15lowhigh交換第一趟排序結(jié)果：71[10]181515lowhigh7．已知數(shù)據(jù)序列{10，1，15，18，7，15}，試寫出采用快速排序法，第一趟排序的結(jié)果。解：71101815158．已知序列｛50，8，51，6，90，17，89，27，65，46｝，請(qǐng)給出采用堆排序法對(duì)該序列作降序排列時(shí)的每一趟的結(jié)果。采用堆排序法排序的各趟結(jié)果以下列圖，排序結(jié)果為90，89，65，51，50