200706180122期末考-考前複習和解題

資料結構:不上機、不翻書
1.二元數(考前、中、後排序)
2.3程式片斷,寫出執行結果(將二元樹的圖形畫出)
4.5老師給指定數字依考題要求將排序法寫出(氣泡排序、插入排序、選擇排序),用表格顯示

 


首先老師出的五題中,滿分 100分,一題算20分好了,你能實拿多少分數?

陳老師的課基本上出席和小考都有的話,老實說老師的學分反而很輕鬆過關到手。期末考的多點努力不放棄的話,應該 OK,不然多弄點軍用品投其所好,應該很好講話。

等待答案和作幣兩條路,不如給自已熟習題型,再褡配無懈可擊的完美作幣方式。例如在一次數學考試中,答案 pass 給同學,對方看了答案抄了後算了一算,回頭和我說,那一題的某部份有錯,要我再算算看。對方沒有全抄,而且有用頭腦的抄,這算是聰明的作幣方法之一吧。

第一大題

前中後排序。

藍字是讓自已加強記憶方法,先左再右,就是左右(有點廢話)。

前序:左右。

中序:左右。

後序:左右

範例:

前序解法:中左右

首先 A 就是『中』第一個遇到了,所以答案第一個字母便是 A。口訣àà,開始第二個字母遇到 B,不要馬上停止就唸下一步『右』,先把所有的『左』全找完為止。

一直左下去…

Ans: A、B、C、E、I (未完)

直到最後一個字母,再來處理『中、左、右』最後一個『右』字。

I 的上頭是 E,並沒有右子樹。

再往上走到 C 。

C 有完整的左右樹,剛走完左子樹,現在才要走右邊的 F。

Ans: A、B、C、E、I 、F (未完)

第一輪的口訣『中、左、右』結束。邁入第兩輪。

F 只有左子樹並沒有右子樹,而 F 為於『中』,它的左是 J。而這是最末端的節點,它並沒有『右』。

所以,第二輪的口訣『中、左、』也結束。

Ans: A、B、C、E、I 、F、J (未完)

用過後的字母請點過做記號,免的重復使用

Ans: A、B、C、E、I 、F、J、D、G、H、K、L

 


 

中序解法:左中右

第一輪口訣:àà

在(E、C、F)節點中,E 之下還有個左子樹I 所以 I 字母才是開始。

Ans: I、E、C、 (未完) 

F 是 (E、C、F)的右子樹,在它之下還有個 J,所以先將下層的處理好再回到上層 。

Ans: I、E、C、JF (未完)

有一個特別要注意的地方是,當右邊有路可以走下去時,不要急的填下右邊的字母,如上圖 (C、B、D) 基本上我們寫了 C 和 B 了,但是 D 又是另一的節點的頭。而是把 (G、D、H)看成未完成的任務,必需再往下走。

D在 (C、B、D) 這個節點它的確是右。但是

D在 (G、D、H) 在這個節點它卻是中。

全部正確的答案就是

Ans: I、E、C、J 、F、B、G、D、K、H、L、A

 

特別注意,如果 I 是 E 的右子樹,則解答將有變動

Ans: E、I、C、J、F、B、G、D、K、H、L、A

 最後的後序排法和中序的觀念是一樣的,一層層的節點往上做。

Ans: I、E、J、F、C、G、K、L、H、D、B、A

 

考試前五分鐘不必看這題,圖片和說明只會把自已的思緒弄的更亂,少了這一題你還可以把握剩下的 80 分。如果非要得個幾分的話,我建議把握一下前序排法:中左右。

如果,三小題全出,每一小題少說可得 6-8分。而前序排法是最容易得分的小題,二元樹必定會有 A 起頭,不然出不了題目。 

附上小考出過的題目和解答

前序排法:+ y * + - 2 * 3 y 4 - * + 4 y 2 y

中序排法:y + 2 - 3 * y + 4 * 4 + y * 2 - y

後序排法:y 2 3 y * - 4 + 4 y + 2 * y - * +

 


 

第二大題,能出的程式片段,只有0507那個教學目錄的前中後序追蹤。程式解說對我來說,有點難度,只能大概猜測它的變化?需要真的看的懂,又有說明能力的同學幫忙解說。以下是我的猜測。

ko5_1.java  -->歪斜樹的數狀結構,所輸入的數字不能有 0 。

ko5_2.java  --> 不會解說。

從上到下,由左到右的排列 22數字在第2層第3個節點,33數字在第3層第7個節點,感覺起來它是個右歪斜樹。能力有限看不懂會怎樣出題。

ko5_3.java  -->二元樹中序追蹤

ko5_4.java  -->二元樹後序追蹤

ko5_5.java -->二元樹前序追蹤

程式片斷,寫出執行結果(將二元樹的圖形畫出) 。有一點要把握,首先出題者並沒有將改過程式片斷。

第一個視破的方法是:

看第一行的提示

 public static void inorder(int node)

 public static void postorder(int node)

 public static void preorder(int node)

inorder 是中序

postorder 是後序

preorder 是前序

記不起來嗎?怎辦?還有聰明的辦法嗎?當然,這是要拿分的題目,我們從程式中,找出簡單的辦法。

第二個辨視的方法: 

public static void inorder(int node)
 {
 if (tree[node]!=0)
     {
      inorder(2*node);
      if (tree[node]!=0)
  System.out.print(tree[node]+"  ");
      inorder(2*node+1);
     }
 }

 

看到上面的程式片斷嗎?我所標紅色的 print (印出)那個部分,它是不是被上下兩行藍字包在中間。

是的,上方的程式就告訴你,這是個中序排列。

準不準?自已試試看

public static void postorder(int node)
 {
 if (tree[node]!=0)
     {
      postorder(2*node);
      postorder(2*node+1);

      if (tree[node]!=0)
  System.out.print(tree[node]+"  ");
     }
 }

管他變數取啥名子,反正紅色在最後一行,它就是後序排序。

public static void preorder(int node)
 {
 if (tree[node]!=0)
     {
      if (tree[node]!=0)
  System.out.print(tree[node]+"  ");
      preorder(2*node);
      preorder(2*node+1);
     }
 }

管他變數取啥名子,反正紅色在最後一行,它就是前序排序。

 再來是畫出二元樹的方法。

先用剛剛第一大題的範例,我們把英文字母換成數字1、2、3、4。

A

B

C

D

E

F

G

H

I

J

K

L

1

2

3

4

5

6

7

8

9

10

11

12

它們是二元樹的結構,第2層的 B 右方缺右子樹,就補 0 替代。

一共有五層,n為層級,就是  2n-1。

25-1 = 32-1 = 31 。就會有 31 個 節點。就會得到下方的圖。

中序: I、E、C、J 、F、B、G、D、K、H、L、A

換算的數字就是 9、5、3、10、6、2、7、4、11、8、12、1

 


 

前置作業完成,現在來猜猜老師會怎樣出題‧

2.3程式片斷,寫出執行結果(將二元樹的圖形畫出) 

從字面上看來將會出兩小題,分數會有 40分。

我猜可能會這樣的出題方式,並且層級只會到第三層 7個節點,最多到第四層15個節點,太少層級及太多層級就不太可能,例如第五層就會到31個節點又太多了。

例如出

請問用那種排法?排列為 2、4、1、5、3、6畫出它的排列二元樹。

答案為:中序排序,畫法如下。

 

 

經過 Java 程式跑出解答會如下圖

 


 

第三大題

(從氣泡排序、插入排序、選擇排序),用表格顯示。此題可得20分。

氣泡排序:

氣泡排序法(Bubble Sort)又稱為交換排序法,是最簡單的排序法之一。將資料放在同一陣列中,由第一個元素開始,比較相鄰的陣列元素大小,若大小順序有誤,則對調後再進行下個元素的比較。如此掃瞄過一次之後就可確保最後一個元素是正確的。接著再進行第二次掃瞄,直到完成排序。

逐次比較兩個相鄰的資料,按照排序的條件交換位置,直到全部資料依序排好為止。資料移動的過程,好像氣泡上升的現象,故取名氣泡排序法。 

由於氣泡排序為相鄰兩者相互比較對調,並不會更改其原本排列的順序。此排序法適用於資料量小或有部份資料已經過排序。

插入排序:

插入排序法(Insert Sort)是將陣列中的元素,逐一與已排序好的資料作比較,再將該陣列元素插入適當的位置。

此排序法適用於大部份資料已經過排序或已排序資料庫新增資料後進行排序。插入排序法會造成資料的大量搬移,所以建議在鏈結串列上使用。

選擇排序:

選擇排序法(Selection Sort)是從所有待排序的資料中找出最小鍵值,將該筆記錄與第一筆記錄對調後,再從第二筆以後的資料中重覆做一樣的動作,直到完成排序為止。

此排序法適用於資料量小或有部份資料已經過排序。  

可以參考

http://blog.xuite.net/x_3kkk/java/11663179


氣泡排序:

 

加強記憶的方法:

用位置來比對誰大誰小,當我比你小我永遠不做變動。當你比我大時,我們來交換位置。

第一個位置比完後它就固定在第一個位置不再比對,再換第二個位置再重覆做比大小的動作,一直比到最後。

 舉例如下:

第1個位置是 38

用第1個位置去和後面的數字逐一比對。

第1位置對第2位置  38對93 後者沒前者小,不變。

再來第1位置去比第3位置 38對84 後者沒前者小,不變。

第1位置對第4位置 38對27 後者比前者小,兩兩交換。

再來還是用第1位置去和第5位置比大小。

27對62後者沒前者小,不變。

這樣第一輪的比大小活動結束,換第二輪開始。這時第一位置永遠不用到它了,它就停留在第一位置上,第二輪就從第二位置開始和第三位置比大小,一直到最後。所以有多少數字 n 就是比 n-1 輪(次)。舉例,五個數字就會有四輪,換句換說,放上100個數字,氣泡排序就要做上99輪(次)。

氣泡排序程式寫作可以參考 http://blog.xuite.net/x_3kkk/java/11663179

 

 


 

插入排序:

加強記憶的方法:

從第一個位置不斷往後找,每找一次就插隊進來。

 


 

選擇排序:

加強記憶的方法:

在還沒開始排序時,自已從頭往後找到最小的數字。像這種排序就像人類用肉眼在比大小,全班考試卷在你手上,分數有高有低沒排過,自已不斷找出最低分放在最前頭,心中盤算那一個是最小的就放在第一格子中,再挑次低的數字,不停放好。

 


 

最後

有人和我討論過插入法和選擇法兩個方法好相似,用考卷分數排列的例子套用在插入法中好像也可以,我的例子亂餚了他。

我想說,插入法你可以想像全班同學在排身高,大家先在教室外等,一個個進來比身高,然後插入最適當的位置。

最後補充就是兩者的差別在,選擇法是每次都在一堆未排序的數字中,找出最低的數字。

 

校稿第11

平均分數:0 顆星    投票人數:0
我要評分:
回應
Flagcounter.com
free counters
Java 在線人數


    沒有新回應!
關鍵字
累積 | 今日
loading......
部落格觀察

HOTRANK
2007.12.11啟用Hotrank
觀看訪客統計報表