這份有幾題想請教大家,
DS&ALGO
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100418.pdf
1(c) binary tree的delete可以取左子樹最大或右子樹最小來取代,所以這題是要都
畫出來嗎?或是自己假設可選擇時哪種優先在畫出來這樣?
2(b) 想問successful search是要把紅黑樹當作平衡的情況下去算平均搜尋次數嗎?
我的想法是1*1+2*2+3*4....+logn*2^([logn)-1]
(n代表阿發,我不會打XD)
CA&OS
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100417.pdf
1. 這題想討論的是multiprocessor(不是題目中提到的SMT)和multicore的差異,
估狗查到multicore有自己的運算單元跟L1cache而L2cache有可能是共享的,
想問假如都是在同一台電腦,2-core processor跟2顆單core processor執行程式
的能力差在哪呢?
附上估狗參考資料:
![]()
(內容有提及此題SMT的部分)
3(c) 這題要提出兩個解決race condition並且避免polling的方法,
只想到disable interrupt,還有什麼方法方法不會用到spinlock的嗎?
4(a)(b) 爬過文有討論到這題但還是不太清楚,題目所謂200ms in average to
complete its computation是單指CPU time還是包含等待I/O的時間?
然後要如何判斷是否要migrate到別的core上?
感謝看完。