高二数位化资料处理讲义.doc

高二數位化資料處理講義 單元：排序/搜尋一、排序選擇排序法(Selection Sort)u 規則：拿第一個元素依序與其餘各元素作比較，若是第一個元素大於後面的元素則兩個元素對調。再拿第二個元素與其餘N-2個元素比較，以此類推。練習：將以下數列由小至大排列(升冪)984237第一輪結果 共比較次，交換次第二輪結果 共比較次，交換次第三輪結果 共比較次，交換次第四輪結果 共比較次，交換次第五輪結果 共比較次，交換次1. 氣泡排序法(Bubble Sort)u 規則：將所有資料與次一筆資料比較大小，如次序不對則交換。練習：將以下數列由小至大排列(升冪)984237第一輪結果 共比較次，交換次第二輪結果 共比較次，交換次第三輪結果 共比較次，交換次第四輪結果 共比較次，交換次第五輪結果 共比較次，交換次2. 假設有N筆資料要排序，請分別計算兩種排序法的比較次數。b.氣泡排序法(Bubble Sort) 共需比較輪 共需比較次a.擇排序法(Selection Sort) 共需比較輪 共需比較次二、搜尋1.循序搜尋法(sequential search)：u 由資料的第一個元素開始，往後逐一和欲尋找的項目相比較，如果比較後的結果相同就表示找到了。最少需比較1次，最多需比較N次，平均搜尋次數為 。範例： 數列 7 , 8 , 4 , 3 , 6 , 2 , 3 請問要搜尋資料 6要比較幾次？ 搜尋資料 3要比較幾次？ 搜尋資料1要比較幾次？2.二分搜尋法(binary search)：u 使用二分搜尋法之前，必須先確定所搜尋的元素已經排序好。u 開始時，先將欲搜尋的數值與中間元素相比較，如果中間元素等於所欲搜尋的數值，則搜尋成功並停止搜尋。否則判斷所欲搜尋的數值如比中間元素小，則搜尋前半部，否則搜尋後半部，一直到找到所搜尋的數值或沒有搜尋範圍為止。u 範例：搜尋目標 34數值註標 12345678數值內容2234456676899699 L=1M=4 U=8第一次搜尋位置=(1+8)/2=4 找到6634，放棄右半部數值註標 12345678數值內容2234456676899699 L=1M=2 U=3第二次搜尋位置=(1+3)/2=2 找到34，停止搜尋u 範例：搜尋目標 100數值註標 12345678數值內容2234456676899699 L=1M=4 U=8第一次搜尋位置=(1+8)/2=4 找到66100，放棄左半部數值註標 12345678數值內容2234456676899699 L=5M=6 U=8第二次搜尋位置=(5+8)/2=6 找到89100，放棄左半部，繼續搜尋數值註標 12345678數值內容2234456676899699 L=M=7 U=8第三次搜尋位置=(7+8)/2=7 找到96100，放棄左半部，繼續搜尋數值註標 12345678數值內容2234456676899699 L=M=U=8第四次搜尋位置=(8+8)/2=8 找到99U時代表此數列並無所欲搜尋的數字，結束搜尋結論：二分搜尋法最佳搜尋次數1，最差(or找不到)次數為logN+1次練習題：01.() 所謂升冪排序是指將資料 (A)由小至大排列 (B)由大至小排列 (C)大小相間排列 (D)隨意排列 02.() 當使用選擇排序法來排序8筆資料時，最多需比較 (A)28 (B)8 (C)3 (D)4 次 03.() 利用氣泡排序法，將以下數列資料30, 50, 20, 60, 40由小至大排序，請問在第一次循環結束後，此數列應是下列那一個？ (A)20, 50, 30, 60, 40 (B)20, 30, 40, 50, 60 (C)30, 20, 50, 40, 60 (D)60, 50, 40, 20, 30 04.() 在N筆資料中，將相鄰的二筆資料兩兩互相比較並調整位置，依此要領直到所有資料由小至大排列，此種方法稱為 (A)選擇排序法 (B)氣泡排序法 (C)循序搜尋法 (D)二分搜尋法 05.() 利用氣泡排序法，將以下數列資料30, 50, 20, 60, 40依遞減順序排列，請問在第一次循環結束後，此數列應是下列那一個？ (A)30, 50, 60, 40, 20 (B)50, 30, 60, 40, 20 (C)20, 30, 40, 50, 60 (D)30, 40, 50, 60, 20 06.() 利用氣泡排序法排列N筆資料的順序，最多做幾次的排序循環？ (A)N / 2次 (B)N次 (C)N 1次 (D)N + 1次 07.() 若使用泡沫排序法，將自小到大排序的數列（5，10，15，20，25）排序成由大到小的順序，共需比較多少次？ (A)0 (B)5 (C)10 (D)15 次 08.() 在一串數列中逐一搜尋直到找到想找的元素，通常使用在資料量較小的資料列是下列那一種搜尋法？ (A)循序搜尋法 (B)合併搜尋法 (C)快速搜尋法 (D)二分搜尋法 09.() 利用循序搜尋法，找尋某一筆已知存在陣列（有15筆資料）中的資料，最好的情況要作比較次數與最壞的情況要作比較次數的平均為 (A)8 (B)7 (C)15 (D)2 10.() 有一整數陣列，內含9個已排序的整數，假設給予一搜尋值a，並利用二分搜尋法找出搜尋值a，請問在最壞的情況下，必須要對此陣列進行幾次搜尋，才能知道搜尋值a是否存在陣列中？ (A)1次 (B)3次 (C)4次 (D)9次 11.() 由資料列1、3、5、7、9、11、13、15、17中搜尋資料20時，若採用二分搜尋法，則經過幾次比較之後才發現該資料並不存在？ (A)2 (B)3 (C)4 (D)5 12.() 二元搜尋法在搜尋升冪排序過後的資料時，是將所欲搜尋的數值與資料中的哪一個元素進行比較？ (A)任意一個 (B)第一個 (C)最後一個 (D)最中間的 13.() 關於選擇排序法（selection sort），若其原始資料排列順序為：24, 57, 48, 37, 12, 92, 86, 34。則其pass 2（第二回合）之排序結果為下列何者？ (A)92 , 86 , 57 , 37 , 12 , 24 , 48 , 34 (B)92 , 86 , 48 , 37 , 12 , 24 , 57 , 34 (C)92 , 86 , 57 , 48 , 37 , 34 , 24 , 12 (D)92 , 86 , 57 , 48 , 12 , 24 , 37 , 34 14.() 在已排序的1000個相異元素之陣列中，欲執行二元搜尋法（Binary Search）以找尋某資料。若要找尋的資料並不在陣列中，則大約要比對多少個元素才能確定它不在陣列中？ (A)4 (B)10 (C)500 (D)1000 15.() 在3000筆已由大至小排序好的資料中，用二元搜尋法（Binary Search）搜尋某一筆特定資料（假定資料存在），最多需要比較幾次可以搜尋到該筆資料？ (A)12 (B)16 (C)20 (D)30 16.() 利用氣泡排序法將以下資料：W、X、Y、Z由大至小排列，需要幾次比較？ (A)0 (B)3 (C)5 (D)6 17.() 所謂降冪排序是指將資料 (A)由小至大排列 (B)由大至小排列 (C)大小相間排列 (D)隨意排列 18.() N個資料作氣泡排序時，須經過幾次比較？ (A)N (N 1) / 2 (B)N / 2 (C)N (D)N (N + 1) / 2 19.() 利用選擇排序法，將以下數列資料 74, 50, 46, 33, 25 由小至大排序，請問共需經過幾次比較？ (A)0次 (B)5次 (C)10次 (D)15次 20.() 在N筆（N 1000）已由大至小排序好的資料中，用二元搜尋法（Binary Search）搜尋某一筆特定資料，最多約要比較幾次才能搜尋到該筆資料？ (A)1 (B)log2 N (C)log10 N (D)N 21.() 將127筆資料排序後再以二分搜尋法去搜尋某一資料時，最多需搜尋幾次即可找到該筆資料？ (A)7次 (B)6次 (C)8次 (D)5次 22.() 下列有關搜尋演算法的敘述何者正確？ (A)逐筆檢查直到找到指定資料為止的方式稱為二分搜尋法 (B)N筆資料若以循序搜尋法搜尋，則平均搜尋次數為N / 2次 (C)使用二分搜尋法之前需先將資料升冪或降冪排序 (D)N筆資料若以二分搜尋法搜尋，則最多需搜尋（N+1）/2次 23.() 以選擇排序法由小到大排序10、2、6、8、3時，請問在第一次循環結束後，此數列應是下列那一個？ (A)2、6、8、3、10 (B)2、10、6、8、3 (C)2、3、6、8、10 (D)2、6、8、3、10 24.() 利用循序搜尋法在31筆已排序資料中尋找指定資料（假設該筆資料存在），請問最少需要比較幾次，才能找到指定資料？ (A)32 (B)31 (C)5 (D)1 25.() 在已排序的1000個相異元素之陣列中，欲執行二元搜尋法（binary search）以找尋某資料。若要找尋的資料並不在陣列中，則大約要比對多少個元素才能確定它不在陣列中？ (A)4 (B)10 (C)500 (D)1000 26.() 對下列7筆已排序的資料（2, 13, 27, 32, 44, 58, 67），以二元搜尋法找尋關鍵值為58的資料