111 中山資工所軟體考點分析｜國立中山大學

資料結構 55%＋作業系統 45%。前 4 題全是資料結構（指標運算、全排列遞迴、stack 序列、BST、heap sort），後 5 題是 OS 的計算題。

題型與配分

科目名稱「作業系統與資料結構」【資工系碩士班甲組】，題號 434003，考試時間 100 分鐘，不可以使用計算機（問答申論題），全卷 2 頁、9 題、100 分。

資料結構部分（1–4，50%）

第 1 題（15%）｜(a) 5% 一支傳入 &e[2]+4、&e[2+4]、e、e+4、&e[2] 五種不同指標運算式的函式，寫出 printf 的五個值。純指標算術，要非常小心 (b) 10% 一支遞迴產生全排列的函式 g(a, 0, 2)，寫出所有輸出
第 2 題（10%）｜四個符號 A, B, C, D 依序推入 stack，四次 PUSH 與四次 POP 的所有組合中，哪些輸出序列是不可能的，要分別以 AXXX、BXXX、CXXX、DXXX 分類給出個數。答案與 Catalan number 有關（合法序列共 14 種，不可能的有 10 種）
第 3 題（10%）｜依序插入 3, 6, 4, 5, 2, 7, 1 到空 BST，再刪除 3（非葉節點用 inorder successor 取代），畫出結果
第 4 題（15%）｜Heap sort：(a) 10% 對 14, 4, 19, 2, 18, 7, 17, 9, 16, 13 建 max heap，畫出第一階段結束後的樹 (b) 5% 輸出第一個最大值並重整後的樹

作業系統部分（5–9，50%）

第 5 題（10%）｜i-node 有 10 個直接區塊與三層間接，指標 8 bytes、區塊 8 KB：(a) 5% 最小檔案需要幾個區塊 (b) 5% 最大檔案需要幾個區塊
第 6 題（10%）｜4096 個 page、page table 讀取 500 nsec、TLB 128 項、查詢 50 nsec，要讓平均開銷降到 100 nsec 以下需要多少命中率
第 7 題（10%）｜10000 個磁柱的磁碟，比較「不做叢集（平均 seek 5 msec）」與「做叢集（平均 seek 500 μsec）」兩種情況下讀取 100 個區塊的總時間（旋轉延遲 10 msec、傳輸 20 μsec/區塊）
第 8 題（10%）｜8 GB RAM 以 4 KB 為單位配置，用 bit map 追蹤可用記憶體需要幾 KB
第 9 題（10%）｜48-bit 虛擬位址、32-bit 實體位址、page 4 KB，page table 需要幾個項目（2⁴⁸ / 2¹² = 2³⁶）

第 1(a) 的指標算術（5 分）是全卷最容易失手的地方：&e[2]+4、&e[2+4]、e、e+4、&e[2] 五個運算式中有兩對其實指向同一位址，而且函式內還會修改 w[2]，會影響後面印出的值。
第 2 題要分類計數不可能的序列，不能只說「有幾種」，要按首字母分成四組。
第 4(a) 的建堆（10 分）要對 10 個數字完整跑 bottom-up heapify，畫出正確的樹。
第 7 題要算兩種情況的總時間，單位在 msec 與 μsec 之間切換，禁用計算器容易出錯。