作者boy5548 (小YO)
看板Grad-ProbAsk
標題[理工] [OS] 99中山資工
時間Sun Jan 30 22:10:20 2011
Consider a file system on a disk that has both logical and physical block sizes
of 512 bytes.Assume that the information about each file is already in memory.
For each of the three allocation strategies(Contiguous,linked,indexed),answer
the questions:
(a)How is the logical-to-physical address mapping accomplished in this system?
(For the indexed allcation,assume that a file is always less than 512 blocks
long.)
這題該怎麼答..?
(b)If we are currently at logical block 10(the last block accessed was block
10) and want to access logical boldk4,how many physycal blocks must be read
from the disk?
這題想問的是index allcation，解答給的答案是2，為什麼不是1呢?
謝謝!!
--
另外是台大資工97年的軟體設計
題目在此
http://www.lib.ntu.edu.tw/exam/graduate/97/97420.pdf
想問一下第7題，題目簡單來講，就是問Longest common substring problem
可以在O(nlgn)下解決嗎?
正常應該是O(mn)吧 (m,n為字串A,B之長度)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.2.216
※ 編輯: boy5548 來自: 114.39.2.216 (01/30 22:19)
→ skyevolution:(b)1.read index block 2.read block4 01/30 22:15
→ boy5548:那如果題目說index block已存在memory裡了，就不用算了嗎 01/30 22:25
→ boy5548:因為之前看過一題是改變index node 如果index node已經存 01/30 22:25
→ skyevolution:恩 01/30 22:26
→ boy5548:在memory裡，則不用做I/O operarion 01/30 22:26
→ boy5548:嗯嗯 謝謝!! 01/30 22:26
→ dy957:所以不管剛存取了什麼 還是要把index block抓進來囉@@? 01/30 22:27
→ skyevolution:不確定，如果是非選擇題 就把假設寫上吧 01/30 22:31
推 tureday:97台大那題我也覺得是要在O(mn)才能完成，你要證明它無法 01/31 00:13
→ tureday:在O(nlgn)下解決 01/31 00:14
推 cksh3300110:使用suffix tree 01/31 01:21
推 jameschou:可是LCS我記得有一種轉換成類似LIS的方法 就可以nlogn 01/31 02:02
→ boy5548:樓上記得怎麼解嗎?? 01/31 09:09