數(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）。單元測試10一．判斷題（以下各題，正確的請在前面的括號內(nèi)打√；錯誤的打

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

AB

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

D

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

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

B

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

D

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

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

B

．牢固

C

．外面

D

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

B）儲藏。A．必定鏈表

B

．必定次序

C．次序或鏈表

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

C）。A．冒泡排序

B

．堆排序

C

．快速排序

D.

歸并排序（7）快速排序在（C）情況下最易發(fā)揮其長處。A．待排序的數(shù)據(jù)中含有多個相同的要點字B．待排序的數(shù)據(jù)已基本有序C．待排序的數(shù)據(jù)完好無序D．待排序的數(shù)據(jù)中最大值與最小值相差懸殊（8）下述幾種排序方法中，要求內(nèi)存量最大的是：（D）。A．插入排序B．選擇排序C．快速排序D.歸并排序（9）直接插入排序的方法是從第（B）個元素開始，插入到前邊合適地址的排序方法。A．1B．2C．3D．n（10）堆的形狀是一棵（C）。A．二叉排序樹B．滿二叉樹C．完好二叉樹D．平衡二叉樹（11）內(nèi)排序是指在排序的整個過程中，全部數(shù)據(jù)都在計算機(jī)的（A）中完成的排序。A．內(nèi)存B．外存C．內(nèi)存和外存D．存放器（12）快速排序的方法是（A）的排序方法。A．不牢固B．牢固C．外面D．選擇（13）以下排序方法中，要點字比較次數(shù)與記錄的初始排列次序沒關(guān)的是（A）。A．選擇排序B．希爾排序C．插入排序D．冒泡排序（14）下述幾種排序方法中，平均時間復(fù)雜度最小的是（A）。A．希爾排序B．插入排序C．冒泡排序D．選擇排序（15）對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是（B）。A．O(n)B2C．O(nlog2n)D3．O(n)．O(n)（16）冒泡排序的方法對n個數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（C）次。A．1B．2C．n-1D．n（17）對ｎ個不相同的排序碼進(jìn)行冒泡（遞加）排序，在以下（B）情況比較的次數(shù)最多。A．從小到大排列好的B．從大到小排列好的C．元素?zé)o序D．元素基本有序（18）用直接插入排序法對下面的四個序列進(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個長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為：（A）。A，16253548234079823672B．16253548798223364072C．16254835798223364072D．1625354879233640728220）一個數(shù)據(jù)序列的要點字為：（46，79，56，38，40，84），采用快速排序，并以第一個數(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}，寫出采用直接插入算法排序時，每一趟排序的結(jié)果。解：1817604007327365第一趟結(jié)束時結(jié)果：[1718]604007327365第二趟結(jié)束時結(jié)果：[171860]4007327365第三趟結(jié)束時結(jié)果：[17184060]07327365第四趟結(jié)束時結(jié)果：[0717184060]327365第五趟結(jié)束時結(jié)果：[071718324060]7365第六趟結(jié)束時結(jié)果：[07171832406073]65第七趟結(jié)束時結(jié)果：[0717183240606573]已知數(shù)據(jù)序列{17，18，60，40，7，32，73，65，85}請寫出采用冒泡排序法對該序列作升序排序時每一趟的結(jié)果。解：17186040732736585第一趟排序結(jié)果：17184073260657385第二趟排序結(jié)果：171873240606573第三趟排序結(jié)果：1771832406065第四趟排序結(jié)果：71718324060第五趟排序結(jié)果：717183240第五趟排序過程中已無記錄交換，排序結(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｝，請給出采用堆排序法對該序列作降序排列時的每一趟的結(jié)果。采用堆排序法排序的各趟結(jié)果以下列圖，排序結(jié)果為90，89，65，51，50