二級MSOffice高級應(yīng)用新大綱選擇題題目、解析及答案時間復(fù)雜度

1、二級MSOffice高級應(yīng)用（新大綱）選擇題題目、解析及答案（時間復(fù)雜度）常用排序方法排序方法最好最壞平均冒泡排序O(n)O(n2)O(n2)插入排序O(n)O(n2)O(n2)選擇排序O(n2)O(n2)O(n2)希爾排序O(n)O(n2)O(n1.3)快速排序O(nlog2n)O(n2)O(nlog2n)堆排序O(nlog2n)O(nlog2n)O(nlog2n)常用查找方法查找方法平均時間復(fù)雜度查找條件順序查找O(n)無序或有序隊列二分查找（折半查找）O(logn)有序數(shù)組二叉排序樹查找O(logn)二叉排序樹1 .在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是（）。A

2、）B）0?D)?1/參考答案：C2 .下列排序方法中，最壞情況下比較次數(shù)最少的是（）。A）冒泡排序B）簡單選擇排序C）直接插入排序D）堆排序參考答案：D解析：最壞情況下：冒泡排序、簡單選擇排序、簡單插入排序比較n（n-1）/2次；堆排序比較的次數(shù)是nlog2n次。3 .對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n（n-1）/2的排序方法是（）。A）快速排序B）冒泡排序C）直接插入排序D）堆排序參考答案：D解析：堆排序的時間復(fù)雜度是nlog2n；4 .下列排序法中，最壞情況下時間復(fù)雜度最小的是（）。A）希爾排序B）堆排序C）快速排序D）冒泡排序參考答案：B解析：快速排序、冒泡排序、希爾排

3、序最壞情況時間下的時間復(fù)雜度為O（n2）,堆排序最壞情況下的時間復(fù)雜度為O（nlog2n）。5 .設(shè)順序表的長度為n0下列算法中，最壞情況下比較次數(shù)小于n的是（）。A）快速排序B）堆排序C）尋找最大項D）順序查找法參考答案：C解析：最壞情況下比較次數(shù)：快速排序：n（n-1）/2堆排序：nlog2n查找最大項：先設(shè)第一個數(shù)是最大數(shù)，然后逐次和后面的（n-1）個數(shù)比較，需要比較次數(shù)為n-1；順序查找法：最壞情況下從第一個數(shù)開始找到最后一個，比較次數(shù)為n06 .下列排序法中，每經(jīng)過一次元素的交換會產(chǎn)生新的逆序的是（）。A）冒泡排序B）快速排序C）簡單插入排序D）簡單選擇排序參考答案：B解析：在一個排

4、列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序?？焖倥判颍和ㄟ^一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列7 .在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn)在表中每個位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為（）。A） nB） （n+1）/2C） 3n/4D） n/4參考答案：B解析：在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1;在最壞情

5、況下，最后一個元素才是要找的元素，則比較次數(shù)為n0則n個數(shù)總的比較次數(shù)為(1+2+-+(n-1)+n)=(1+n)xn)/2,平均為：(n+1)/28 .設(shè)順序表的長度為n。下列排序方法中，最壞情況下比較次數(shù)小于n(n-1)/2的是()。A)堆排序B)快速排序C)簡單插入排序D)冒泡排序參考答案：A解析：堆排序最壞情況下比較次數(shù)為O(nlog2n)。9 .下列各排序法中，最壞情況下的時間復(fù)雜度最低的是()。A)希爾排序B)快速排序C)堆排序D)冒泡排序參考答案：C解析：堆排序最壞情況時間下的時間復(fù)雜度為O(nlog2n)。10 .設(shè)順序表的長度為40,對該表進行冒泡排序。在最壞情況下需要的比較

6、次數(shù)為()。A) 820B) 780C) 40D) 41參考答案：B解析：冒泡排序在最壞情況下需要比較的次數(shù)為n(n-1)/2。11 .在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后（A）只能消除一個逆序B）能消除多個逆序C）不會產(chǎn)生新的逆序D）消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多參考答案：B解析：在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。希爾排序是把記錄按下標(biāo)的一定增量分組,對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。12 .設(shè)順序表的長度為16,對該表進行簡單插入排序。在最壞情況下需要的比較次數(shù)為（）。A） 15B） 60C） 30D） 120參考答案：D解析：簡單插入排序在最壞情況下比較次數(shù)為n（n-1）/2013 .下列敘述中正確的是（）。A）快速排序法適用于順序存儲的線性表B）快速排序適用于鏈?zhǔn)酱鎯Φ木€性表C）鏈?zhǔn)酱鎯Φ木€性表不可能排序D）堆排序適用于非線性結(jié)構(gòu)參考答案：A14 .在最壞情況下比較次數(shù)相同的是（）。A）冒泡排序與快速排序B）簡單插入排序與希爾排序C)簡單選擇排序與堆排序D)快速排序與希爾排序參考答案：A解析：