P2(TAB)小考2參考

 3/24、3/25 小考2

段1考前上課需備課本頁數如下 {另Ch1可不印 2~17,43~45}
Ch2：2,3,4,7,8,14,15,16,18,19,22,23,24,25,26,27,28,29
Ch3：2,3,4,5,6,10,11,14,15,16,17,19,20,21,22,23,24,25,26,27,28,29

小考2的選擇題範圍：
    Ch2:  6(C), 8(C), 9(C), 10(A), 11(D), 13(D), 14(A)
    Ch3:  1(C), 2(A), 6C), 9(D), 11(C), 12(A), 13(D), 14(B)

小考2的課內填充題範圍：

p.2-14：排序常使用___陣列___資料結構，因為能使___程式___更精簡。
排序是將資料___由小到大(遞增)___或___由大到小(遞減)___排列好。
___氣泡排序法___是基本排序法中的一種，其基本原理是：反複走訪陣列中元素，兩兩比較___相鄰___的資料，若尚未排列好，___交換___這兩個資料。

p.2-16：遞增的氣泡排序，每次循環後，已排序的___最大___元素會被移到最後。
遞減的氣泡排序，每次循環後，已排序的___最小___元素會被移到最後。
氣泡排序法若要排 n 筆資料，需要 ___ n-1 ___個循環可完成排序
          且第 i 次循環需要比較 ___ n – i ___ 次

p.2-22：從 n 筆資料中循序搜尋，最佳情形會比較___1___次，最差情形會比較___n___次。

p.2-24：二分搜尋是除了循序搜尋外的另一種資料搜尋法，搜尋前資料需預先___排序___好。其基本原理如下
將鍵值或___中間位置___的資料比較，若鍵值較小，往___前半部___搜尋；若鍵值較大，
往___後半部___搜尋。直到搜尋到資料或沒有資料可搜尋為止。
二分搜尋法若有 n 筆資料，只需___log2(n)___ 次比較就能完成。{註：嚴謹的話最多需int(log2(n))+1 }

p.3-19：____分而治之__演算法是不斷將問題___分割___成__性質__相同或相近的較小問題，直到所有小問題都很容易解決。最後再一一___解決___小問題，並將各個子問題的解答，___組合(合併)___成較大問題的解答，以解決原來的問題。所以___遞迴___是這種演算法很重要的方法。

p.3-20：排序演算法有很多種，合併演算法是其中的一種，它是應用____分而治之___算法
若有8筆資料，需__3__層的分割，第1層各分為4個，第2層各分為2個，第3層分為1個
接著需__3__層的合併，第1層各合為2個，第2層各否為4個，第3層合成8個，完成合併。

三、進階填充題：考7題(14%)

1、河內塔4個環，由A柱移至C柱，請問第12步為？____3BC_____

2、河內塔5個環，由A柱移至C柱，請問第22步為？____2CA_____

3、河內塔6個環，由A柱移至C柱，請問第24步為？____3CA____

4、a陣列為由小到大已排序如右宣告，int a[9]={11,23,45,66,72,79,83,88,93,99};

   請問以二分搜尋法找 key=23，問與哪幾個數值比較後才確定找到？____72,23_____________(依序列出)

5、b陣列為由大到小已排序如右宣告，int b[7]={91,83,75,66,45,33,18};

   請問以二分搜尋法找 key=33，問與哪幾個數值比較後才確定找到？____66,33_________(依序列出)

6、c陣列如右宣告，int c[8]={53,33,18,83,75,66,91,45};

   以合併(遞增)排序，請問第2層合併後陣列內容應為 { _18_,_33_,_53_,_83_,_45_,_66_,_75_,_91_ }

7、d陣列如右宣告，int d[8]={ 18,53,33,83,75,91,45,66};

   以合併(遞減)排序，請問第1層合併後陣列內容應為 { _53_,_18_,_83_,_33_,_91_,_75_,_66_,_45_ }

小考2範例檔下載