試題評析

Size: px

Start display at page:

Download "試題評析"

详尹纪
5 years ago
Views:

1 資料結構高點一請參考圖 : ( 一 ) 由 a 點出發, 做 depth-first traversal( 深度優先拜訪 ), 請問那些節點 (node) 不會被訪問到?(3 分 ) ( 二 ) 由 a 點出發, 做 breadth-first traversal( 寬度優先拜訪 ), 請問那些節點 (node) 不會被訪問到?(2 分 ) ( 三 ) 假設圖代表 heap 上各個節點 (node) 及其相互指向的關係 p q r 三節點代表全域變數 (global variables), 其他的節點代表 heap 上的記憶體區塊如果 p a 的指標被消除, 那些節點會變成無用的垃圾節點? 你必須詳細描述尋找垃圾節點的方法及所需之資料結構你的演算法只能從 a 節點出發, 它必須指出所有的垃圾節點, 並且你的演算法只能在每一個節點儲存很少量的資料請問你的演算法必須在每一個節點儲存那些資料?(5 分 ) p 圖一個有向圖 (a directed graph) 試題評析本題使用圖形的追蹤,DFS 與 BFS 即可解出考點命中高上資料結構, 王致強編撰, 頁 8-22~28 a ( 一 )g,j,q,r ( 二 )g,j,q,r ( 三 ) 如果 p->a 的指標被消除,a b c d x 會變成圾垃節點演算法如下 : 先將全部的節點都作記號 ; For 每一個存在的節點 do 進行追蹤,DFS 或 BFS 皆可, 將追蹤到的節點記號消除 ; 最後, 記號未消除的節點皆為圾垃節點. x c q b 高上d j 二定義如下的函數 F: 如果 x 是偶數, 則 F(x)=x/2; 否則 F(x)=F(F(3x+)) ( 一 ) 請問 F()=?(5 分 ) ( 二 ) 請證明對於任何正整數 w, 我們都可以在有限時間內計算 F(w) ( 提示 : 每個奇數可以寫成 (2i+)2- 的形式, 再採用數學歸納法來證明 )(5 分 ) 試題評析測驗考生的遞迴程式的推演能力, 屬於進階問題考點命中高上資料結構, 王致強編撰, 頁 5-58 精選例題 38 r e l g f m h n -- --

2 ()F()=F(F(34))=F(7)=F(F(52))=F(26)=3 (2) 取 w = (2i+ )2 -, 使用 Induction 証明即可 Basis: 當 = 時,F(x)=F(2i)=i Hypothesis: 當 <n 時, 對任意的 i 值,F(x) 之值皆可以計算出來 Induction: 證明 =n 時, 亦成立 F((2i+)2 n -) =F(F(3(2i+)2 n -3+)) =F(F((3(2i+)2 n- -)2)) =F((6i+3)2 n- -) =F((2(3i+)+)2 n- -) =F((2m+) 2 n- -).... 是可以計算出來的高點三 Knuth,Morris 及 Pratt 發明了一個快速的字串比對方法 (string pattern matching) 他們的方法採用一個失敗函數 (failure function) 失敗函數其實就是一個輔助的資料結構, 用來加速比對請依他們的方法計算下列字串的失敗函數你必須說明失敗函數的定義為何, 以及失敗函數如何加速比對 (5 分 ) index pattern a b b a b c a b b a failure?????????? 試題評析測驗字串比對之 KMP 演算法考點命中高上資料結構, 王致強編撰, 頁 3-72 ~74 失敗函數定義如下 : f(j) = 最大的 i 值 ( 其中, 存在有 j>i, 而且 pp pi=pj-ipj-i+ pj,); f(j) = -, 其他情況失敗函數如下 : index pattern a b b a b c a b b a failure 當比對到 si pj 時, 取 j f(j-)+, 然後繼續比對 si 與 pj 下去, 可避免須從頭比較的時間耗費. 高上四請參考圖 2 每一條線段上的數字代表兩節點間的距離請找出 a 節點到節點的最短路徑的長度並請說明你的方法如何應用在非常大型的圖裡 (5 分 )

3 a 4 g d 7 23 f 3 b 49 7 高點4 26 圖 2 最短路徑試題評析測驗 Dijstra 的單起點最短路徑演算法考點命中高上資料結構, 王致強編撰, 頁 8-6 ~62 c e 27 h 高上使用 Dijstra 最短路徑演算法, 可求得 a 到的最短路徑 :a d b e, 總長度為 46. 在大型的圖裡, 可以用鄰接串列來表示圖形, 再使用 Fibonacci-Heap 的 delete-smallest-ey 找出距離最小的頂點, 利用其 Decrease-ey 的運算來修改各頂點的距離, 可以使得整個 Dijstra algorithm 時間複雜度為 O(nlogn+e). 演算法如下 : ()procedure shortestpath(v, cost, dist, pred); (2) beign (3)S {v}; dist[v] ; prev[v] ; // 設定起點初值 (4)for each u V {v } do // 設定其他頂點的相關初值 (5)begin (6)dist[u] cost[v, u]; // 路徑長度初值 (7)if cost[v, u] then pred[u] v; // 記錄前行節點 (8)else pred[u] ; (9)end; ()while S < V do ()begin (2)u 選出 S 之外 dist 最小的頂點 ; (3)// 用 F-heaps 的 delete-min 運算, 每次 amortized (4)//cost 為 O(log V ), 總時間為 O( V log V ) S {u} (5)S ; (6)for each u,w E(G) do (7)if w Sthen (8)if dist[u]+cost[u,w]<dist[w] then (9)begin (2)pred[w] u; ()dist[w] dist[u]+cost[u,w]; (22)// 使用 F-heaps 的 decrease-ey() (23)// amortized cost O() (24)end; (25)end; (26)end;

4 五請參考圖 3 圖 3 是一個 activity-on-edge 網路在 activity-on-edge 網路中, 一項計畫可以分成很多件工作, 每一件工作由一條線段代表, 線段上的數字代表該工作所需的時間 ( 以工作日為單位 ), 線段的箭頭代表工作的先後關係例如在圖 3 中,ab 及 db 線段代表的工作完成之後, bc be 及 bf 線段代表的工作才可以開始進行, 其他的先後關係依此類推 a 節點是起點, 節點是全部工作的完成點請找出節點的最早完成時間及關鍵路線 (critical path) 並請說明你的方法如何應用在非常大型的圖裡 (5 分 ) a 4 22 d g 3 高點b 9 f 3 高上 2 e 27 7 h 圖 3 Activity-on-edge 網路試題評析測驗 AOE 邊工作網路之計算考點命中高上資料結構, 王致強編撰, 頁 8-89 ~94 ( 一 ) 節點最早完成的時間為 6, 關鍵路線為 ad db bf fe ec c ( 二 ) 在大型的圖裡, 圖形以 Adjacency List 表示, 以 stac 記錄可以輸出的節點, 以 forward 求每個頂點的 ee(earliest Event Occurrence Time) 再用 Reverse Adjacency List,bacward 方向求每個頂點的 le(latest Event Occurrence Time), 其中也是以 stac 記錄可以輸出的節點最後再計算, 每個線段的 e 與 l, 如果 e=l 的線段即為關鍵活動 () 先以 forward 方式由 a 往方向求 ee v a b c d e f g h ee(v) (2) 再以 bacward 方式由往 a 方向求 le v a b c d e f g h le(v) (3) 最後計算每個線段的 e 與 l 線段 e l 關鍵活動 ab 3 ad v ag 6 bc be bf v c v db 4 4 v df 4 4 ec v c 23 23

5 eh e fe v fh gd 5 gf 5 42 gh 5 8 h 六在一個二元樹裡有許多節點 (nodes) 假設每一個節點的資料結構如下圖 : 高點LEFT DATA RIGHT 其中 DATA 欄位為該節點的資料 LEFT 欄位為指向左方子樹的指標變數 RIGHT 欄位為指向右方子樹的指標變數如果節點 p 沒有左方子數, 其 LEFT 欄位為空指標 (null pointer) 同理, 如果節點 p 沒有右方子樹, 其 RIGHT 欄位為空指標 (null pointer) ( 一 ) 如果一個二元樹有 n 個節點, 那麼它有幾個空指標?(5 分 ) ( 二 ) 我們可以利用原本是空指標的欄位來儲存引線 (threads) 二元樹加上引線的結果稱為引線樹 (threaded trees) 當然我們必須在各節點再加上兩個欄位 LTAG 及 RTAG, 共 5 個欄位, 如下圖所示 : LTAG LEFT DATA RIGHT RTAG 如果 LEFT 欄位代表一般的節點指標, 則 LTAG= 如果 LEFT 欄位代表引線指標, 則 LTAG= 同理, 如果 RIGHT 欄位代表一般的節點指標, 則 RTAG= 如果 RIGHT 欄位代表引線指標, 則 RTAG= 請將下圖的二元樹加上適當的引線指標, 讓它變成引線樹, 並請繪圖標出 A 到 I 共 9 個節點中所有引線指標指向的節點 ( 分 ) 高上A B C D E F G H I 試題評析測驗引線二元樹的建置考點命中高上資料結構, 王致強編撰, 頁 6-34 ~

6 中序追蹤.: FDGBACHIE 首節點 B D F G A 引線二元樹 C H 高點E 高上 I

1-1 2

1-1 2 烘焙基礎實務應檢術科考前須知 PART 02 1-1 一般性應檢須知 1-2 專業性應檢須知 1-3 術科指定參考配方表 1-4 術科測驗製作報告表 1-5 術科技能檢定評分表 1-6 術科測試時間配當表 1 1-1 2 應檢術科考前須知十五應檢人有下列情形之一者取消應檢資格其成績以不及格論 1. 冒名頂替者協助他人或託他人代為操作者或作弊者 2. 互換半成品成品或製作報告表 3. 攜出工具