※ 引述《qoojordon (穎川琦)》之銘言：
: 一個觀念 + 政大 102-103 四題
: 截圖網址 http://ppt.cc/PqE0
: Q1觀念:
: Radix sort , bucket sort , counting sort
: 這三種排序法是相同的嗎 ?
: 個人覺得想法上是一樣的 , 只有最後一個使用條件比較嚴苛
: 但政大102年DS問說哪些情況下適合用 Radix sort, 哪些適合用 bucket sort
: 我完全問號 , 這兩個差在哪阿 ?
感覺上 radix sort 與 bucket sort 差異不大，如果真的要說有哪裡不同的話
只能說 radix sort 每一回合都會做"分派 & 合併"
但 bucket sort 只會做一次"分派 & 合併"
另外，假設現在手上有一個 hashing function 的話，那就適合用 bucket sort
個人覺得這不是什麼大問題，所以考這題感覺有點...
: 103 DS
: 不清楚traversal的分離subtree要怎麼作 , 希望能給個例子
: 自己的感覺是level-order , 每隔一個level下面都是子樹 , 不曉得
: 想的對不對
看完這題感覺跟你一樣不清楚XD
我的想法是如果要分離出一個subtree，感覺應該是要跑 inorder traversal
因為每次拜訪都是 LDR → LDR → ...，那每一次的 LDR 就是一個 subtree
以上純屬個人見解，僅供參考
: 103 OS
: 不知道怎麼切入思考 , 題意應該是說系統有兩個雙核心的處理器
: 相當於有四個邏輯上的處理器可以分配
: 依題意 , 1-1 mapping的thread model, 僅有開關檔案的時候會是I/O bound
: thread分配應該是 :
: (1)input/output時建1條thread即可 , 能讓CPU處理完前置工作 , 趕快去作I/O
: (2)開始結束之間是CPU bounded , 所以可以同時建立4條thread在四個邏輯核心上運作
我的想法跟你一樣，感覺上應該是這樣沒錯
: 102 DS 9
: 看不太懂題目再問甚麼 , 是考回文嗎 ?
: 010010 長度k的回文可能個數有幾種 ?
應該就是考回文的個數沒錯
因為第 k 個 bit 一定要跟第 1 個 bit 一樣
所以前面 k/2 個 bits 一定要跟後面 k/2 個 bits 一樣
令 T(k) 表示長度為 k 的回文個數
┌ ┐
=> T(k) = 2^│k/2│，T(1) = 2
: 102 OS IV(b)
: 題目中的 I/O using read() , write() 這種東西是指 I/O instruction嗎 ?
: 印象中計組提到的兩種I/O方式就是 MEM-mapped 和 I/O instruction @@....
應該就是要問 memory mapped I/O 和 I/O instruction 的差異吧
但 OS 好像沒有談到 memory mapped I/O，如果就 I/O instruction 的角度來看
我可能會選擇往特權指令只能在 kernel mode 下執行這個方向去解釋
至於 memory mapped I/O 可能就只能從計組的內容下手了
畢竟配分才 5 分，感覺定義寫一寫應該就差不多了