[理工] 100中央(DS&ALGO)

看板Grad-ProbAsk作者justbelieve (呆)時間14年前 (2012/01/12 18:21)推噓2(2推 0噓 5→)

留言7則, 4人參與討論串1/4 (看更多)

http://ppt.cc/hjRU 因為手頭沒答案想上來跟有寫的or有答案的問一下,順便對 1.1寫得很陽春,大致上想法是 function Search(key x,pointer root) { if(root.key == x) then return found; else if(root的*left不為空){ then root = root的*left; Call function Search(x,root); } else if(root的*right不為空){ then root = root的*right; Call function Search(x,root); } else return Null; } } } 1.2還在想,有類似的考古嗎? 2.completion order:j1,j2,j6,j3,j9,j7,j5,j4,j8 3.2 AVL tree: 5 / \ 3 8 / \ / \ 2 4 6 9 \ 7 5和6有類似的考古or有大大可以分享一下解答嗎? 7.2 最少乘法數:5610 (((A1A2)A3)A4)A5 不知道有沒有計算錯,怎麼感覺越算越小? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.105.52.42 ※ 編輯: justbelieve 來自: 112.105.52.42 (01/12 19:32) 2.因為題目說a system consists of two identical machines,X和Y ......for parallel execution 所以我的想法是這2個machine是可以同時處理job的且一次只能處理一個job 題目規定:這個系統使用"一個"stack來裝RSTime <= 4s的job, 使用"一個"queue來裝RSTime > 4s的job 當2個工作同時間輪到他們執行時,在stack等待的會先被選去執行 start: AT = t Job1到,沒有人搶,隨便選一台假設X來執行 (arrival time) machineX |--J1--|--------- (AT) t t+3 AT = t+1 Job2到,X在執行J1,所以Y來執行J2 machineY |--J2--|--------- t+1 t+5 AT = t+3 此時X處理完J1,在這之前到的Job有J3,J4 因為他們的RST > 4s,所以置入queue中等待 __________________ queue: J3,J4 ,J3移出queue,到X中處理 machineX |--J1--|--J3--|------- t t+3 t+11 AT = t+5 此時Y處理完J2,在這之前的job,除了J4,有J5,J6 因為他們的RST <= 4,所以置入stack中等待, |____| ---- |_J6_| queue: J4, 因為stack優先權高,所以移出J6到Y執行 |_J5_| stack machineY |--J2--|--J6--|------ t+1 t+5 t+9 AT = t+9 Y處理完J6,所有的Job都已進入,且皆在stack or queue中等待如下: |_J9_| ______ |_J7_| queue: J4,J8 |_J5_| stack 依照stack先執行,queue後執行的規則最後的 machineX |--J1--|--J3--|--J7--|--J4--|-- t t+3 t+11 t+15 t+22 machineY |--J2--|--J6--|--J9--|--J5--|--J8--| t+1 t+5 t+9 t+13 t+17 t+24 Ans:completion order = J1,J2,J6,J3,J9,J7,J5,J4,J8 如果哪邊有錯再跟小弟指正一下 ※ 編輯: justbelieve 來自: 112.105.52.42 (01/12 21:38)

→

metalalive

01/12 22:06, , 1^F

01/12 22:06, 1^F

→

metalalive

01/12 22:17, , 2^F

01/12 22:17, 2^F

→

metalalive

01/12 22:18, , 3^F

01/12 22:18, 3^F