政大 115 年資管所（科技組） 計算機概論 參考答案

1.1 目的位址 1.1.1.1:80 全程不變，來源位址被兩層 NAT 改寫（port 為示意）：

NAT#1 轉換表：10.20.30.50:5000 ↔ 192.168.50.11:6000；NAT#2 轉換表：192.168.50.11:6000 ↔ 34.56.34.11:7000。回程依兩表反向逐層還原。

1.2 PAT/NAPT：私有 AP 為每條內部連線（來源 IP＋Port）配一個唯一的 mapped port 記入轉換表，回應封包依目的 port 查表送回對應的主機。

1.3 $2^{32-22}-2=1022$ 個。

2.1 RES。VIRT 含大量已保留但未實際使用的位址空間（如 mmap 保留區、共享函式庫），數字容易虛高；RES 是實際占用的實體 RAM，持續成長不回落才是洩漏的訊號。

2.2 kill <pid> 送 SIGTERM 讓行程自行清理後結束；不回應時用 kill -9 <pid> 送 SIGKILL 強制終止。

2.3 用 dmesg、journalctl -k 或 /var/log/syslog（或 /var/log/messages）查核心訊息，其中 Out of memory: Killed process <pid> (<name>) 紀錄被終止的行程。

3.1 Conditional Breakpoint 是附帶條件式的中斷點，只有條件成立時才暫停。bug 只在特定條件下發生時使用（如迴圈第 3000 筆才出錯，設 i == 2999），免去手動 Continue 數千次。

3.2

• Step Over：執行整個函式呼叫，不進入函式內部。
• Step Into：進入被呼叫的函式逐行執行。
• Step Out：執行完目前函式剩餘部分，返回呼叫者。

以 A 轉帳 1000 元給 B 為例：

1. Atomicity：所有操作同時成功或同時失敗；A 扣款與 B 入帳不能只做一半。
2. Consistency：交易前後滿足完整性限制；A、B 餘額總和不變且不得為負。
3. Isolation：並行交易互不干擾；轉帳進行中查詢不會看到 A 已扣、B 未入的中間狀態。
4. Durability：commit 後結果永久有效；轉帳成功後斷電，重啟仍保留結果。

FPR 下降、FNR 上升。$c$ 提高使判為 positive 的門檻變嚴，接受的樣本變少：分數落在新舊門檻之間的 negative 改判 negative，$FP$ 減少；同區間的 positive 也被拒絕，$FN$ 增加。

6.1 Page fault：行程存取的 page 不在實體記憶體（valid bit 為 0）時觸發的例外。OS 處理：trap 進核心、檢查存取是否合法、在磁碟定位該 page、無空閒 frame 時以 Page Replacement 選 victim 換出（dirty 才寫回）、載入 page 並更新 Page Table、重新執行該指令。

6.2 Thrashing：系統花在換頁的時間遠大於實際執行的時間；行程的 working set 總和超過實體記憶體所致，CPU 使用率驟降、磁碟 I/O 爆增、throughput 崩潰。

6.3 LRU 換出最久未被存取的頁，利用時間區域性，保留的頁較常被再用到，page fault 頻率較低；越接近 OPT 的演算法 page fault 越少，選得不好則增加，FIFO 甚至有 Belady's Anomaly。

def fib(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

8.1

List<Node> gen(int h) {
    List<Node> res = new ArrayList<>();
    res.add(null);                       // 空樹，高度 0
    if (h == 0) return res;
    List<Node> sub = gen(h - 1);
    for (Node L : sub)
        for (Node R : sub) {
            Node t = new Node();
            t.left = L; t.right = R;
            res.add(t);                  // 高度 <= h
        }
    return res;
}

void printAll(int n) {
    for (Node t : gen(n)) print(t);
}

時間複雜度 $\Theta (N_n)=2^{\Theta (2^n)}$，其中 $N_h=1+N_{h-1}^2$，$N_0=1$。

8.2

• 不遺漏：任一非空二元樹唯一分解為左、右子樹，兩者高度皆 $\le h-1$，必在 sub 中，故必被生成。
• 不重複：不同的 $(L,R)$ 配對產生不同形狀，且 sub 依歸納假設無重複。
• 邊界：$h=0$ 只回傳空樹。