【選擇題】
【B】01.若有N個資料存於陣列，使用循序搜尋法，在平均情況(in average case)搜尋一個資料需要多少次資料比較(comparison)？ (A)(N / 2) + 1 (B)(N + 1) / 2 (C)(N - 1) / 2
(D)(N + 2) / 2。[109地方四等電子]
搜尋次數 = (N + 1) / 2次
【A】02.搜尋已排序的串列，使用那種搜尋法較為恰當？ (A)二元搜尋法 (B)插入搜尋法 (C)循序搜尋法 (D)氣泡搜尋法。[109地方四等電子]
二元搜尋法，搜尋前須先將資料排序。
【D】03.給定一串整數{130,
120, 100, 90, 80, 60, 50, 40, 30, 20, 10}，若使用二元搜尋法，則需要做幾次比較(comparisons)才能找到30？ (A)9
(B)4 (C)3 (D)2。[109身心五等]
第1次搜尋，(1 + 11) ÷ 2 =
6，第6個數字60
第2次搜尋，(7 + 11) ÷ 2 =
9，第9個數字30，找到
【B】04.已排序(sorted)的表格資料如下：3, 4, 6, 5, 8, 15, 19, 18, 16,
12, 24, 20，以二元搜尋法(binary
search)取得11，需比較幾次？ (A)3
(B)4 (C)5 (D)11。[109鐵路員級]
(1 + 15) ÷ 2 = 8 → 19
(1 + 7) ÷ 2 = 4 → 9
(5 + 7) ÷ 2 = 6 → 14
(5 + 5) ÷ 2 = 5 → 11
【A】05.以二元搜尋法(Binary
search)在100筆已經排序好的資料中搜尋某筆資料，最差的狀況下會進行x次比較，下列何者正確？ (A)x<10 (B)10<=x<50
(C)50<=x<99 (D)x=99。[110地方四等電子]
log2 100 = 6.643856
【B】06.若採循序搜尋(Sequential
search)，從n個未排序的數字中進行搜尋，平均要進行幾次數字比較，才能成功搜尋到特定的數字？ (A)n
(B)(n+1)/2 (C)(n+1)*n/2 (D)n/2。[110地方四等電子]
循序搜尋之平均搜尋次數=(n+1)/2次
【D】07.關於二元搜索(binary
search)的演算法描述，何者錯誤？ (A)二元搜索的演算法是假設要被搜索的陣列中項目已排序好 (B)每一次的比較後，可以減少一半的陣列不用去尋找 (C)二元搜索的演算法是陣列的中間處開始 (D)二元搜索在第一次的比較後，將陣列切為兩半，隨機選取任意一半繼續尋找。[110身心五等]
採用二分搜尋法，資料須事先排序。
資料由小至大排序，
若目標資料小於中間資料，則繼續搜尋前半段的資料。
若目標資料大於中間資料，則繼續搜尋後半段的資料。
直至找到目標資料或無資料為止。
【D】08.根據下列按字母順序(alphabetical
order)排列的字元數列，若使用二元搜尋法進行搜尋，至少需要幾次的資料比對才可以找到字元L(包含L本身)？L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z (A)1
(B)2 (C)3 (D)4。[110初考資處]
15筆資料，24 = 16＞15
【A】09.下列為對同一個問題的四個不同演算法的時間複雜度(time complexity)，若N趨近於無限大，何者執行的速度最快？ (A)(logN)4
(B)N(logN)3 (C)N2(logN)2 (D)N3logN。[110初考資處]
時間複雜度拆開：
(A)1＜(B)N＜(C)N2＜(D)N3
(A)(logN)4＞(B)(logN)3＞(C)(logN)2＞(D)logN
若N趨近於無限大，N的複雜度＞logN
複雜度(A)＜(B)＜(C)＜(D)
速度(A)＞(B)＞(C)＞(D)
【B】10.若要以二元搜尋(Binary search)從A,B,C,D,E,F,G,H,I,J,K,L,M,N,O中尋找Z，則搜尋過程中檢驗的字母依序為何？ (A)A,B,C,D,E,F,G,H,I,J,K,L,M,N,O
(B)H,L,N,O (C)O (D)H,A,O。[110鐵路員級]
第1次搜尋，(1 + 15) ÷ 2 = 8，第8個字母H
第2次搜尋，(9 + 15) ÷ 2 = 12，第12個字母L
第3次搜尋，(13 + 15) ÷ 2 = 14，第14個字母N
第4次搜尋，(15 + 15) ÷ 2 = 15，第15個字母O
字串中，找不到Z，結束執行
【D】11.對一個存有1999個元素的陣列，進行二進位搜尋(binary search)，若搜尋失敗，請問比較的次數為何？ (A)10 (B)14
(C)12 (D)11。[111身心五等]
210≦1999≦211
【C】12.搜尋未排序的串列，應使用那種搜尋法？ (A)二元搜尋法 (B)插入搜尋法 (C)循序搜尋法 (D)氣泡搜尋法。[111身心四等]
循序搜尋法：從第一個資料開始，依序逐一與目標資料比較，直到找到目標資料或所有資料均搜尋完畢為止。資料不須排序。
【C】13.下列程式片段的時間複雜度為何？for(i=n; i>0; i/=2) x++; (A)O(NlogN) (B)O(N)
(C)O(logN) (D)O(1)。[111初考資處]
|
n |
i |
x |
|
4 |
4 |
1 |
|
|
2 |
2 |
|
|
1 |
3 |
|
|
0 |
跳出迴圈 |
迴圈執行次數=log2 4 + 1 = 3次
【C】14.已知在使用二分搜尋法(Binary Search)對排序過的n個數字陣列(Array)做搜尋時，前4次比對之陣列數值依序為18.5, 12.5, 7.5, 3.5。從以上結果推導，在1至20之整數範圍中，有多少個數字不可能為搜尋值？ (A)2 (B)8 (C)13 (D)17。[111鐵路員級]
會搜尋到的值：3、5、7、10、12、15、17
不會搜尋到的值有20-7=13個
【C】15.在長度為n的串列中進行循序搜尋法，則成功的搜尋(Successful search)平均要做多少次的鍵值比較(Key comparisons)？ (A)n/2 (B)(n–1)/2
(C)(n+1)/2 (D)log n，(log以2為底)。[111鐵路員級]
平均搜尋次數(n+1)/2次
節點2，有3,4,7，選3
節點3，有4,8，選4
節點4，有5,8，選5
節點5，有6,8，選6
節點6，有7，選7
【B】17.若要從一個已經排序好的數列中，進行二元搜尋(Binary search)，目的是從中尋找425這個數字。下列何者不是搜尋過程，可能檢驗的數字序列？ (A)200,300,425
(B)400,951,810,600,395,425 (C)425 (D)200,800,500,425。[112地方四等電子]
二元搜尋法：資料須事先排序。
【D】18.如果資料用下列的資料結構來儲存，那麼我們要搜尋某個資料，下列那一個它的平均時間複雜度跟其他三個不一樣？ (A)線性鏈結串列(linear linked list) (B)堆疊(stack) (C)佇列(queue) (D)二元搜尋樹(binary search tree)。[112國安五等]
(A)線性鏈結串列、(B)堆疊、(C)佇列，皆為循序搜尋法，平均時間複雜度為O(n)
(D)二元搜尋樹，為二分搜尋法，平均時間複雜度為O(log2n)
【A】19.給定一個陣列arr={45,66,78,89,91,95,120}，且欲搜尋的目標鍵值是key=95，則使用二元搜尋法第一次尋找、第二次尋找分別比對那個元素？ (A)89、95 (B)89、91 (C)78、95 (D)78、91。[112普考電子]
第一次尋找：key(95)＞arr[mid](89)
第二次尋找：key(95)＝arr[mid](95)
【D】20.下列何者不是為了加快存取資料而設計的索引結構？ (A)二元搜尋樹(binary search tree)
(B)B+樹(B+ tree) (C)R樹(R tree) (D)語法樹(syntax tree)。[113初考資處]
語法樹是用於程式語言分析的結構，不是為了加快存取資料而設計的索引結構。
【B】21.理論上下列搜尋演算法中何者效率是最佳的？ (A)二元搜尋(binary search) (B)雜湊表搜尋(hash table search) (C)插值搜尋(interpolation search)
(D)循序搜尋(sequential search)。[113初考資處]
雜湊表搜尋：應用資料中某欄位之值代入事先設計之雜湊函數，計算資料儲存位置，應用時以資料鍵值(key value)轉換，搜尋速度最快，資料不須事先排序。
【C】22.下列排序方法中，何者採用分治法(Divide and Conquer)的概念？ (A)氣泡排序法(Bubble Sort) (B)插入排序法(Insertion Sort) (C)快速排序法(Quick Sort) (D)選擇排序法(Selection Sort)。[109地方四等資處]
快速排序法使用分而治之法則，以遞增為例，步驟如下：
1.數列中任意挑選一個數字做為基準點(pivot)。
2.小於此數字移至基準點的左邊，大於此數字移至右邊，相等的任意放。
3.基準點左邊和右邊視為兩個數列，重複上述動作，直到數列剩下一個或零個元素。
【D】23.使用氣泡排序法由大至小排序數列：「6、9、3、2、7」，則總共要比較幾次？ (A)7 (B)8 (C)9 (D)10。[109地方四等電子]
比較次數 = 5 * (5 - 1) / 2 = 10次
【C】24.關於快速排序法(quick sort)的敘述，下列何者錯誤？ (A)在最差情況下(worst case)的時間複雜度為O(n2) (B)在最佳情況下(best case)的時間複雜度為O(n log n) (C)基準值(pivot)的選擇與時間複雜度無關 (D)使用分而治之法則(divide and conquer)。[109地方四等電子]
快速排序法使用分而治之法則，以遞增為例，步驟如下：
1.數列中任意挑選一個數字做為基準點(pivot)。
2.小於此數字移至基準點的左邊，大於此數字移至右邊，相等的任意放。
3.基準點左邊和右邊視為兩個數列，重複上述動作，直到數列剩下一個或零個元素。
【C】25.依時間複雜度來比較，下列那一種排序方法的時間複雜度相較之下是最好的？
(A)氣泡排序法(bubble
sort) (B)插入排序法(insertion
sort) (C)快速排序法(quick
sort) (D)選擇排序法(selection
sort)。[109身心五等]
氣泡排序法時間複雜度為O(n2)
插入排序法時間複雜度為O(n2)
快速排序法最壞情況為O(n2)，通常為O(nlog2n)
選擇排序法時間複雜度為O(n2)
【B】26.合併排序法(Merge Sort)利用合併(Merge)動作對兩個已排序、各有K個數字的陣列融合為一個已排序、有2K個數字的陣列。在最糟情況(Worst Case)下，以上合併動作之時間複雜度(time complexity)為何？ (A)Ɵ(log K) (B)Ɵ(K) (C)Ɵ(K log K) (D)Ɵ(K2)。[109身心四等]
時間複雜度為O(2K)，可忽略常數，故為O(K)。
【D】27.下列排序演算法中，何者是以divide and conquer的方式設計？ (A)Bubble sort
(B)Insertion sort (C)Heap sort (D)Quick sort。[109普考電子]
快速排序法(Quick sort)：使用分而治之(divide and conquer)的方式設計，從數列中挑選一個基準點，大於基準點的放一邊，小於的放另一邊，重複處理，直到完成排序。
【D】28.若有n個數值，用氣泡排序法(Bubble Sort)進行排序，其時間複雜度何者錯誤？ (A)最好情況為O(n) (B)最壞情況為O(n2) (C)平均情況為O(n2) (D)不是穩定排序法。[109普考電子]
氣泡排序法的特性：1.穩定排序：相同數值的元素，排序後相對位置不改變。2.原地排序：不需使用額外儲存空間來排序。
【C】29.以下排序演算法(sorting algorithm)何者使用分而治之(divide-and-conquer)的概念？ (A)氣泡排序法(bubble sort) (B)插入排序法(insertion sort) (C)快速排序法(quick sort) (D)選擇排序法(selection sort)。[109鐵路員級]
快速排序法：使用分而治之的方式設計，從數列中挑選一個基準點，大於基準點的放一邊，小於的放另一邊，重複處理，直到完成排序。
【A】30.下列何種排序演算法，最適合對尚未完整蒐集的資料進行排序，例如：可能來自網路一次送來一個資料？ (A)Insertion sort
(B)Quick sort (C)Merge sort (D)Selection sort。[110地方四等電子]
插入排序：適用於大部分元素已排序
【D】31.如果使用快速排序法(quick sort)進行排序{a1, a2, ..., an}資料，則最壞(worst case)排序時間正比於多少？ (A)log(n) (B)n
(C)n*log(n) (D)n*n。[110身心五等]
快速排序法之時間複雜度：最差時間O(n*n)，平均時間O(n log n)。
【C】32.有一個數列5 39
56 88 9 23 2 44 31 69，若採用選擇排序法(Selection
Sort)將其由左至右，由小到大排序。請問要執行幾次位置互換(Swap)的動作？ (A)7 (B)8 (C)9 (D)10。[110國安五等資處]
|
執行前 |
未排序最小值 |
執行後 |
|
5
39 56 88 9 23 2 44 31 69 |
2 |
2
39 56 88 9 23 5 44 31 69 |
|
2
39 56 88 9 23 5 44 31 69 |
5 |
2 5
56 88 9 23 39 44 31 69 |
|
2
5 56 88 9 23 39 44 31 69 |
9 |
2
5 9 88 56 23 39 44
31 69 |
|
2
5 9 88 56 23 39 44 31 69 |
23 |
2
5 9 23 56 88 39 44 31
69 |
|
2
5 9 23 56 88 39 44 31 69 |
31 |
2
5 9 23 31 88 39 44 56 69 |
|
2
5 9 23 31 88 39 44 56 69 |
36 |
2
5 9 23 31 39 88
44 56 69 |
|
2
5 9 23 31 39 88 44 56 69 |
44 |
2
5 9 23 31 39 44 88 56 69 |
|
2
5 9 23 31 39 44 88 56 69 |
56 |
2
5 9 23 31 39 44 56 88
69 |
|
2
5 9 23 31 39 44 56 88 69 |
69 |
2
5 9 23 31 39 44 56 69 88 |
【B】33.若使用選擇排序法(Selection Sort)，對一個陣列[43,74,36,65,22]由小到大進行排序，則下列何者為進行完兩次交換後的陣列內容？ (A)[22,36,43,65,74]
(B)[22,36,74,65,43] (C)[36,43,22,65,74] (D)[43,36,65,22,74]。[110普考資處]
第一次交換：22,74,36,65,43
第二次交換：22,36,74,65,43
第三次交換：22,36,43,65,74
【C】34.利用比較(Compare)跟交換(Swap)的運算，來設計排序n個資料之演算法，理論上其平均時間複雜度最佳為 (A)O(log n) (B)O(n)
(C)O(n log n) (D)O(n0.5)。[110普考電子]
【B】35.假設使用插入排序法(Insertion
sort)，正要從頭到尾讀取陣列的資料進行排序，對下列那種情況的輸入資料會有最好的效果？ (A)如果陣列資料以相反順序排序 (B)如果陣列資料已經排序好 (C)如果陣列資料是隨機的順序 (D)輸入陣列資料的順序與效果無關。[110普考電子]
插入排序法的最佳時間複雜度，發生在資料已完成排序的狀況。
【C】36.關於將n筆資料進行排序(Sorting)，下列敘述何者正確？ (A)快速排序法(Quick sort)的worst case時間複雜度是O(n log n) (B)插入排序法(Insertion sort)的best case時間複雜度是O(n log n) (C)合併排序法(Merge sort)的時間複雜度是O(n log n) (D)選擇排序法(Selection sort)的時間複雜度是O(n log n)。[110鐵路員級]
(A)最差時間O(n2)，平均時間O(n log n)。(B)最差時間與平均時間O(n2)。(C)最差時間與平均時間O(n log n)。(D)最差時間與平均時間O(n2)
【A】37.若要將兩個各自由小到大排序好的數列(長度分別為5和6)進行合併排序(Merge sort)，使得合併後的數列也能由小到大排列，則合併過程至少需要進行幾次數字比較？ (A)5 (B)6 (C)10 (D)11。[110鐵路員級]
數列A的長度為m，數列B的長度為n，則合併兩個數列：
最少比較次數 = m或n (若將B長度改為m，則為m)
最多比較次數 = m + n - 1次 (若將B長度改為m，則為2m-1)
本題至少需要進行=11\2=5次數字比較
【D】38.對數列(5, 6, 2, 9, 4)進行選擇排序(Selection sort)，下列何者為正確步驟？ (A)(5, 6, 2, 9, 4)→(5, 6,
2, 4, 9)→(2, 5, 6, 4, 9)→(2, 4, 5, 6, 9) (B)(5, 6, 2, 9, 4)→(2, 5, 6, 4, 9)→(2,
4, 5, 6, 9) (C)(5, 6, 2, 9, 4)→(2, 5, 6, 9, 4)→(2, 4, 5, 6, 9)→(2, 4, 5, 6, 9)→(2,
4, 5, 6, 9) (D)(5, 6, 2, 9, 4)→(2, 6, 5, 9, 4)→(2, 4, 5, 9, 6)→(2, 4, 5, 9, 6)→(2,
4, 5, 6, 9)。[110鐵路員級]
|
執行前 |
未排序最小值 |
執行後 |
|
5, 6, 2, 9, 4 |
2 |
2, 6, 5, 9, 4 |
|
2, 6, 5, 9, 4 |
4 |
2, 4, 5, 9, 6 |
|
2, 4, 5, 9, 6 |
5 |
2, 4, 5, 9, 6 |
|
2, 4, 5, 9, 6 |
6 |
2, 4, 5, 6, 9 |
【C】39.用快速排序(Quick sort)來排序，並以第一個元素為基準(Pivot)，下列那個數列所需排序時間最長？ (A)5 4 3 2 1 6 (B)5 6 1
2 3 4 (C)6 5 4 3 2 1 (D)6 1 2 3 4 5。[111地方四等電子]
原始資料：6, 5, 4, 3, 2, 1
第1輪排序結果：1, 6, 5, 4, 3, 2
第2輪排序結果：1, 2, 6, 5, 4, 3
第3輪排序結果：1, 2, 3, 6, 5, 4
第4輪排序結果：1, 2, 3, 4, 6, 5
第5輪排序結果：1, 2, 3, 4, 5, 6
總比較次數 = (n - 1) * n / 2 = (6 - 1) * 6
/ 2 = 15
【D】40.將下列六個整數依下列步驟由小到大排序的演算法為何？
原始資料9 8 6 10 9 3
第一次比序並交換位置後8 6 9 9 3 10
第二次比序並交換位置後6 8 9 3 9 10
第三次比序並交換位置後6 8 3 9 9 10
第四次比序並交換位置後6 3 8 9 9 10
第五次比序並交換位置後3 6 8 9 9 10 (A)合併排序(merge sort) (B)快速排序(quick sort) (C)選擇排序(selection sort) (D)氣泡排序(bubble sort)。[111身心四等]
氣泡排序法：自第一個元素開始，依序將所有元素與次一個元素比較，若順序不對，則互換位置。
【B】41.分治法(Divide and Conquer)是將問題拆分為子問題，對子問題求解、最終合併結果的一種演算法技巧，下列何種排序法使用分治法的概念？ (A)氣泡排序法(Bubble Sort) (B)合併排序法(Merge Sort) (C)選擇排序法(Selection Sort) (D)插入排序法(Insertion Sort)。[111初考資處]
合併排序法採用分而治之(Divide and Conquer)法則
【D】42.假設以泡沫排序法(Bubble sort)，將給定的n個整數由小排到大，則該演算法執行數字比較的時間複雜度為下列何者？(注意：一次「數字比較」會比較兩個數字，譬如：比較5和3何者較大。) (A)O(1) (B)O(n) (C)O(n
log n) (D)O(n2)。[111普考電子]
泡沫排序法之時間複雜度：最差時間與平均時間O(n2)
【A】43.插入排序法(Insertion
Sort)利用陣列中相鄰元素的交換(Swap)動作對n個數字排序。在不同輸入(Input)的情況下，其交換次數以複雜度(Complexity)而言最少及最多者為何？ (A)最少：Θ(n)，最多：Θ(n2) (B)最少：Θ(n2)，最多：Θ(n2)
(C)最少：Θ(n)，最多：Θ(n log n) (D)最少：Θ(n log n)，最多：Θ(n log n)。[111普考電子]
插入排序法之時間複雜度：最差時間與平均時間O(n2)，最佳時間O(n)
【C】44.下列何者為外部排序演算法(External sorting algorithm)？ (A)排序過程中涉及交換的演算法 (B)排序過程中使用主記憶體的演算法 (C)排序過程中使用磁帶或磁碟的演算法 (D)排序過程中只使用原輸入陣列的演算法。[111普考電子]
外部排序演算法：排序過程中使用記憶體以外的空間(磁帶或磁碟)的演算法，適用於資料量大。
【C】45.假設輸入的資料序列為：7，3，6，5，4，2，1，使用選擇排序法(Selection sort)對該序列進行遞增順序(Ascending order)排序，則第一個回合的結果為何？ (A)2，3，6，5，4，7，1 (B)3，7，6，5，4，2，1 (C)1，3，6，5，4，2，7 (D)4，3，6，5，7，2，1。[112地方四等電子]
找出最小元素1和7對換
【A】46.使用選擇排序法(Selection Sort)對資料串列"7 5 4 6"進行遞增排序，第一個回合後的結果是 (A)4 5 7 6 (B)5 4 7 6
(C)6 5 4 7 (D)7 5 4 6。[112身心五等]
7 5 4 6 → 找出最小值4，將4與7對換，第一回合結果為4 5 7 6
4 5 7 6 → 找出4以外的最小值5，不需對換，第二回合結果為4 5 7 6
4 5 7 6 → 找出4、5以外的最小值6，將6與7對換，第三回合結果為4 5 7 6
比較回合數 = 元素數N - 1 = 4 - 1 = 3
【C】47.下列那種排序演算法，無法在原輸入資料的陣列上(in-place)進行排序，需要額外的暫存記憶體空間？ (A)Bubble Sort
(B)Insertion Sort (C)Merge Sort (D)Selection Sort。[112身心五等]
合併(Merge)排序：.採用分而治之(Divide and Conquer)法則，需要額外空間O(n)。
【A】48.如果鍵值相同之資料，在排序後相對位置與排序前相同時，則稱為穩定排序(stable sorting)法，下列何者不屬於穩定排序法？ (A)堆積排序法(Heap sort) (B)氣泡排序法(Bubble sort) (C)插入排序法(Insertion sort) (D)合併排序法(Merge sort)。[112國安五等]
穩定排序法有：氣泡排序法、插入排序法、薛爾排序法、合併排序法、基數排序法。
【C】49.下列何種排序方法其最壞情況時間複雜度為O(nlog2n)？ (A)選擇排序法(selection sort) (B)插入排序法(insertion sort) (C)合併排序法(merge sort) (D)快速排序法(quick sort)。[112國安五等]
選擇排序法、插入排序法、快速排序法的最壞情況時間複雜度皆為O(n2)
【C】50.下列敘述中何者錯誤？ (A)使用二元搜尋法，原本的資料必須是已經排序好的才行 (B)使用合併排序法(merges ort)，是將兩個已經排序好的陣列，來進行合併 (C)氣泡排序法(bubble sort)的平均運算時間複雜度為O(n*log(n)) (D)循序搜尋法(Sequential Search)的平均運算時間複雜度為O(n)。[112國安五等]
氣泡排序法的時間複雜度：最差時間與平均時間O(n2)
【C】51.若要將2個各自由小到大排序好的數列(長度分別為5和6)進行合併排序(Merge
sort)，使得合併後的數列也能由小到大排列，則合併過程最多需要進行幾次數字比較？
(A)5 (B)6 (C)10 (D)11。[112普考電子]
數列A的長度為m，數列B的長度為n，則合併兩個數列：
最少比較次數 = m或n (若將A長度改為n，則為n)
最多比較次數 = m + n - 1次 (若將A長度改為n，則為2n-1)
最多比較次數 = 5 + 6 - 1 = 10
【A】52.下列由C語言程式撰寫的函數sort實作了何種排序法？ (A)快速排序(Quick sort) (B)插入排序(Insertion sort) (C)選擇排序(Selection sort) (D)合併排序(Merge sort)。[112普考電子]
void sort(int a[], int l, int h){
if (l >= h)
return;
int j, i, key;
i = l; j = h;
key = a[i];
while (i <
j){
while (i
< j && a[j] > key) j--;
if (i <
j) a[i++] = a[j];
while (i
< j && a[i] < key) i++;
if (i <
j) a[j--] = a[i];
}
a[i] = key;
if (l < i -
1)
sort (a, l,
i - 1);
if (i
+ 1 < h)
sort (a, i + 1, h);
}
1.採用分而治之(Divide and
Conquer)法則
2.數列中任選一個元素做為基準點(pivot)。
3.小於此元素移至基準點左邊，大於此元素移至右邊，相等的任意放。
4.基準點左邊和右邊視為兩個數列，重複上述動作，直到數列剩下一個或零個元素。
5.時間複雜度：最差時間O(n2)，平均時間O(n log n)
6.平均時間最快之內部排序法
【A】53.若以插入排序(Insertion sort)對數列(7,10,2,5,4)進行排序，下列何者是正確步驟？ (A)(7,10,2,5,4)->(7,10,2,5,4)->(2,7,10,5,4)->(2,5,7,10,4)->(2,4,5,7,10)
(B)(7,10,2,5,4)->(2,7,10,5,4)->(2,4,7,10,5)->(2,4,5,7,10)->(2,4,5,7,10)
(C)(7,10,2,5,4)->(7,10,2,4,5)->(2,4,5,7,10)
(D)(7,10,2,5,4)->(7,2,5,4,10)->(2,4,5,7,10)。[112普考電子]
插入排序：將待排序元素逐一與已排序元素比較，再將元素放入適當位置。
【A】54.若有n個數字欲進行排序，下列關於任何一種基於比較的排序演算法所需要的最少比較次數複雜度的敘述，何者正確？ (A)Ω(n log n) (B)Ω(n2)
(C)Ω(n2
log n) (D)Ω(n3)。[112關務四等]
任何一種基於比較的排序演算法在最好和最壞情況下所需要的最少比較次數的複雜度都是Ω(n log n)。
【C】55.將資料23，78，45，8，32，56，依由小至大順序進行排序，在第二回合(Pass)之後資料順序為23，45，78，8，32，56，最可能用下列那一種演算法？ (A)氣泡排序法(Bubble sort) (B)選擇排序法(Selection sort) (C)插入排序法(Insertion sort) (D)堆積排序法(Heap sort)。[112鐵路員級]
插入排序法：將待排序元素逐一與已排序元素比較，再將元素放入適當位置。
【D】56.穩定(stable)的排序演算法是指該方法保證相同鍵值的資料在排序後保持原本(尚未排序前)的先後次序，下列何者不是穩定的排序演算法？ (A)氣泡排序(bubble sort) (B)插入排序(insertion sort) (C)合併排序(merge sort) (D)選擇排序(selection sort)。[113初考資處]
選擇排序不是穩定排序演算法，因為它可能會改變具有相同鍵值的資料的原本順序。
沒有留言:
張貼留言
注意：只有此網誌的成員可以留言。