115 年 國立政治大學資訊管理學系碩士班科技組《計算機概論》

本題主要在考驗對網路位址轉換 (NAT) 的理解，特別是雙重 NAT (Double NAT) 的環境下封包的轉換過程，以及如何處理多個主機的連線與 IP 位址配置。

核心觀念：
NAT 的主要目的是將私有 IP 位址轉換為公有 IP 位址，以便在公共網路上進行通訊。雙重 NAT 意指封包會經過兩次 NAT 轉換。

1.1. 封包標頭翻譯與 NAT Translation Table

當你的私有網路中的筆記型電腦 (IP: 10.20.30.50) 發送請求到公網伺服器 (IP: 1.1.1.1) 時，封包會經過兩層 NAT 轉換。

第一次 NAT (你的 AP)：

• 原始封包 (從筆記型電腦發出)：
  • 來源 IP: 10.20.30.50
  • 目的 IP: 1.1.1.1
  • 來源 Port: (例如：Port A，由筆記型電腦隨機指定)
  • 目的 Port: (例如：Port 80，HTTP 預設 Port)
• 經過你的 AP 的 NAT 轉換後：
  • 你的 AP 的 WAN IP 是 192.168.50.11。
  • 你的 AP 會將來源 IP 10.20.30.50 轉換為自己的 WAN IP 192.168.50.11。
  • 同時，為了區分同一個私有 IP 發出的不同連線，它也會修改來源 Port。假設它將 Port A 轉換為 Port B。
  • 轉換後的封包 (發往 Office AP)：
    • 來源 IP: 192.168.50.11
    • 目的 IP: 1.1.1.1
    • 來源 Port: Port B
    • 目的 Port: Port 80

第二次 NAT (Office AP)：

• Office AP 接收到的封包：
  • 來源 IP: 192.168.50.11
  • 目的 IP: 1.1.1.1
  • 來源 Port: Port B
  • 目的 Port: Port 80
• Office AP 的 IP 是 34.56.34.11。
  • Office AP 會將來源 IP 192.168.50.11 轉換為其公網 IP 34.56.34.11。
  • 它也需要修改來源 Port，假設將 Port B 轉換為 Port C。
  • 轉換後的封包 (發往 Internet)：
    • 來源 IP: 34.56.34.11
    • 目的 IP: 1.1.1.1
    • 來源 Port: Port C
    • 目的 Port: Port 80

NAT Translation Table 範例：

你的 AP (192.168.50.11) 的 NAT Table：

內部 IP	內部 Port	外部 IP	外部 Port	目的 IP	目的 Port	狀態
10.20.30.50	Port A	192.168.50.11	Port B	1.1.1.1	Port 80	ESTABLISHED

Office AP (34.56.34.11) 的 NAT Table：

內部 IP	內部 Port	外部 IP	外部 Port	目的 IP	目的 Port	狀態
192.168.50.11	Port B	34.56.34.11	Port C	1.1.1.1	Port 80	ESTABLISHED

1.2. 回應封包的路由

當公網伺服器 (1.1.1.1) 回應時，封包會先到達 Office AP (34.56.34.11)，然後 Office AP 再轉發給你的 AP (192.168.50.11)，最後你的 AP 再轉

本題主要在考驗對 Linux 系統記憶體管理、記憶體洩漏 (memory leak) 的診斷與處理，以及 OOM killer 的機制。

核心觀念：
Linux 系統使用虛擬記憶體管理，VIRT 和 RES 是衡量行程記憶體使用的兩個重要指標。記憶體洩漏會導致系統效能下降，OOM killer 是系統在記憶體不足時保護系統的機制。

2.1. VIRT vs. RES 作為記憶體洩漏指標

• VIRT (Virtual Memory Size): 指行程總共使用的虛擬記憶體大小。這包括行程實際使用的記憶體、共享函式庫、以及已交換到磁碟的記憶體 (swap space)。VIRT 是一個較大的數字，它並不能直接反映行程實際佔用的實體記憶體 (RAM)。
• RES (Resident Memory Size): 指行程實際佔用的實體記憶體 (RAM) 大小。這部分記憶體是行程目前載入到 RAM 中，且尚未被換出的部分。

哪個是更準確的指標？
RES (Resident Memory Size) 是判斷記憶體洩漏更準確的指標。

原因：
記憶體洩漏是指程式佔用的記憶體資源無法被正確釋放，導致記憶體使用量不斷增加。

• 如果一個行程的 RES 持續穩定地上升，並且不會下降，即使系統負載不高，這就強烈暗示該行程存在記憶體洩漏。它佔用的實體記憶體越來越多，最終可能導致系統記憶體耗盡。
• VIRT 雖然也會隨著記憶體洩漏而上升，但它包含了許多其他部分的記憶體（如共享函式庫、swap），因此 VIRT 的上升不一定完全是記憶體洩漏造成的。程式的 VIRT 可能因為載入更多函式庫或使用更多記憶體映射檔案而增加，但如果 RES 沒有同時穩定上升，那麼這可能不是記憶體洩漏。

2.2. 處理記憶體洩漏的行程

當發現一個行程有記憶體洩漏時，處理方式有兩種：

1. 優雅地停止 (Gracefully Stop)：

   • 方法： 發送 SIGTERM 訊號給該行程。
   • 指令： kill <PID> (預設發送 SIGTERM) 或 kill -15 <PID>。
   • 說明： SIGTERM 訊號會通知行程嘗試正常終止。行程可以捕捉這個訊號，進行清理工作（例如儲存資料、釋放資源），然後再自行退出。這是最推薦的方式，因為它能避免資料遺失或系統狀態損壞。

2. 強制停止 (Force Quit)：

   • 方法： 發送 SIGKILL 訊號給該行程。
   • 指令： kill -9 <PID>。
   • 說明： SIGKILL 訊號會立即終止行程，作業系統不會給行程任何清理的機會。這是一種「硬殺」，應作為最後手段，因為它可能導致資料遺失或系統處於不一致的狀態。

處理步驟建議：
首先嘗試使用 kill <PID> (SIGTERM) 讓行程優雅地退出。

本題主要在考驗對程式除錯 (debugging) 技術的理解，特別是中斷點 (breakpoint) 的使用以及程式碼步進 (stepping) 的操作。

核心觀念：
除錯是找出和修正程式錯誤的過程。中斷點允許程式在特定位置暫停執行，以便檢查程式狀態。程式碼步進則允許開發者逐行或逐函數地執行程式碼。

3.1. 條件式中斷點 (Conditional Breakpoint)

• 定義： 條件式中斷點是一種特殊的中斷點，它只會在滿足預設的特定條件時，才會暫停程式的執行。

• 與一般中斷點的區別：

  • 一般中斷點 (Regular Breakpoint)： 程式執行到該行程式碼時，無論任何情況都會暫停。
  • 條件式中斷點： 程式執行到該行程式碼時，會先檢查設定的條件。只有當條件評估為真 (True) 時，程式才會暫停；否則，程式會繼續執行，直到遇到下一個中斷點或程式結束。

• 使用時機：
  在處理複雜程式碼、特別是包含迴圈 (loop) 或需要檢查特定狀態的場景時，條件式中斷點非常有用。例如：

  1. 處理大量資料時： 在一個處理數千筆資料的迴圈中，你可能只想在處理某個特定 ID 的資料、或當某個變數的值達到特定門檻時才暫停，以便觀察該筆資料的處理細節。這時，如果使用一般中斷點，程式會在每一次迴圈迭代時都暫停，這會極大地拖慢除錯速度，甚至難以忍受。
  2. 特定錯誤條件的重現： 當一個 bug 只在某些特定條件下發生（例如，當使用者名稱為 "admin" 且密碼錯誤時），你可以設定一個條件式中斷點，只在這些情況下暫停，從而更容易定位問題。
  3. 觀察變數的變化趨勢： 你可以設定一個條件，當某個變數的值超過或低於某個閾值時暫停，以觀察其變化的趨勢或異常。

  在題目情境中：
  在這個 e-commerce 應用程式的 bug 調査中，程式碼「處理數千 items 的迴圈」是使用條件式中斷點最理想的場景。例如，如果 bug 只發生在處理 item_id = 12345 的時候，或者當 total_price > 10000 的時候，你就可以設定這樣的條件式中斷點。這樣，除錯器只會在真正需要檢查的迭代中暫停，極大地提高除錯效率。

本題主要在考驗對資料庫交易 (Database Transaction) 的 ACID 特性的理解，以及如何舉例說明。

核心觀念：
資料庫交易是一系列對資料庫進行的讀寫操作，這些操作被視為一個單一的邏輯工作單元。ACID 是確保交易可靠執行的四個基本屬性。

ACID 屬性：

1. 原子性 (Atomicity)

• 定義： 交易中的所有操作必須是不可分割的單元。要麼所有操作都成功執行，要麼所有操作都不執行（回滾）。不存在部分成功的交易。
• 目的： 確保資料庫的一致性。
• 舉例說明：
  假設有一個銀行轉帳交易，需要從帳戶 A 扣款 1000 元，並向帳戶 B 存款 1000 元。
  • 成功情況： 如果從帳戶 A 扣款 1000 元的操作成功，那麼向帳戶 B 存款 1000 元的操作也必須成功。
  • 失敗情況： 如果從帳戶 A 扣款 1000 元的操作成功，但在嘗試向帳戶 B 存款時發生錯誤（例如，帳戶 B 不存在或磁碟空間不足），那麼整個交易必須被回滾，帳戶 A 的扣款必須被撤銷，恢復到交易前的狀態。

2. 一致性 (Consistency)

• 定義： 交易執行前後，資料庫必須從一個有效狀態轉換到另一個有效狀態。換句話說，交易不能破壞資料庫的完整性約束（例如，主鍵約束、外鍵約束、欄位值範圍約束等）。
• 目的： 維護資料的正確性和完整性。
• 舉例說明：
  延續上述銀行轉帳的例子。
  • 有效狀態： 在交易開始前，帳戶 A 的餘額是 5000 元，帳戶 B 的餘額是 2000 元。
  • 交易執行： 從 A 扣款 1000，向 B 存款 1000。
  • 交易後有效狀態： 帳戶 A 餘額變為 4000 元，帳戶 B 餘額變為 3000 元。總餘額 (5000+2000=7000) 保持不變。
  • 無效狀態 (違反一致性)： 如果交易執行後，帳戶 A 餘額變為 4000 元，但帳戶 B 餘額卻變成了 2500 元（總餘額變為 6500 元），這就違反了一致性。或者，如果 A 扣款後，B 的餘額變為負數（如果 B 的餘額有非負約束），這也違反了一致性。

3. 隔離性 (Isolation)

• 定義： 併發執行的交易之間不會互相影響。每個交易都感覺像是在獨立執行，不會看到其他交易正在進行中的、未提交 (uncommitted) 的修改。
• 目的： 避免併發交易導致的數據不一致問題（如髒讀、不可重複讀、幻讀）。
• 舉例說明：
  假設有兩個交易 T1 和 T2 同時進行。
  • T1： 從帳戶 A 轉帳 1000 元到帳戶 B。
  • T2： 查詢帳戶 A 的餘額。
  • 隔離性保證：
    • 如果 T1 先執行了扣款操作（A 餘額減少 1000），但尚未提交。此時 T2 查詢 A 的餘額，隔離性會保證 T2 看到的是 T1 執行前的 A 的餘額（因為 T1 的修改尚未提交），或者 T2 必須等待 T1 完成並提交後，才能看到 T1 修改後的餘額。T2 不會看到 A 餘額減少了 1000 但 B 餘額還未增加的「中間狀態」。
    • 如果 T2 先查詢了 A 的餘額，然後 T1 開始執行。

本題主要在考驗對二元分類器 (Binary Classifier) 評估指標的理解，特別是閾值 (threshold) 對誤判率 (False Positive Rate, FPR) 和漏判率 (False Negative Rate, FNR) 的影響。

核心觀念：
二元分類器根據輸入 $x$ 的某個函數值 $f(x)$ 與閾值 $c$ 的比較來決定分類結果。

• 如果 $f(x) > c$，則判斷為「陽性」(Positive)。
• 如果 $f(x) \le c$，則判斷為「陰性」(Negative)。

我們需要分析當閾值 $c$ 增加時，FPR 和 FNR 如何變化。

定義：

• 真陽性 (True Positive, TP): 實際為陽性，預測也為陽性。

• 偽陽性 (False Positive, FP): 實際為陰性，預測為陽性。(誤判率的基礎)

• 真陰性 (True Negative, TN): 實際為陰性，預測也為陰性。

• 偽陰性 (False Negative, FN): 實際為陽性，預測為陰性。(漏判率的基礎)

• 誤判率 (False Positive Rate, FPR):
  $FPR = \frac{FP}{FP + TN}$
  這是所有實際為陰性的樣本中，被錯誤判斷為陽性的比例。

• 漏判率 (False Negative Rate, FNR):
  $FNR = \frac{FN}{FN + TP}$
  這是所有實際為陽性的樣本中，被錯誤判斷為陰性的比例。

分析閾值 $c$ 的影響：

當我們增加閾值 $c$ 時：

• 要讓分類器判斷為「陽性」(Positive)，即 $f(x) > c$ 的條件變得更難滿足。因為 $c$ 變大了，只有當 $f(x)$ 的值非常高時，這個條件才會成立。
• 反之，判斷為「陰性」(Negative)，即 $f(x) \le c$ 的條件變得更容易滿足。

現在我們來看 FPR 和 FNR 的變化：

1. 對誤判率 (FPR) 的影響：

• FPR = FP / (FP + TN)
• 當 $c$ 增加時，判斷為「陽性」的門檻提高了。

本題主要在考驗對作業系統記憶體管理中「分頁 (paging)」、「分頁錯誤 (page fault)」以及「換頁 (thrashing)」等概念的理解，以及分頁置換演算法的影響。

核心觀念：
虛擬記憶體是現代作業系統的重要機制，它允許程式使用的記憶體空間超過實體記憶體 (RAM) 的大小。當程式需要存取的記憶體頁面不在 RAM 中時，就會發生分頁錯誤。

6.1. 分頁錯誤 (Page Fault) 及作業系統處理方式

• 定義：
  當 CPU 嘗試存取一個程式的虛擬記憶體位址，但該位址對應的記憶體頁面 (page) 並不存在於實體記憶體 (RAM) 中時，就會發生一個「分頁錯誤」(Page Fault)。這通常是因為該頁面被換出 (swapped out) 到硬碟的交換空間 (swap space) 或磁碟檔案中，或者該頁面根本還未被載入記憶體（例如，第一次存取程式碼或資料）。

• 作業系統 (OS) 的處理流程：
  當分頁錯誤發生時，CPU 會產生一個中斷 (interrupt)，將控制權交給作業系統。OS 的分頁錯誤處理器會執行以下步驟：

  1. 檢查位址的有效性： OS 檢查 CPU 嘗試存取的虛擬位址是否合法。如果位址無效（例如，存取了不屬於該行程的記憶體），則行程會被終止（通常是 Segmentation Fault）。
  2. 定位頁面： 如果位址有效，OS 會在交換空間或磁碟檔案中找到所需的記憶體頁面。
  3. 分配物理頁框 (Frame)： OS 在實體記憶體 (RAM) 中尋找一個可用的頁框 (page frame)。
  4. 讀取頁面： OS 將所需的頁面從硬碟讀取到分配到的物理頁框中。
  5. 更新頁表 (Page Table)： OS 更新該行程的頁表，將虛擬頁面與新的物理頁框關聯起來，並標記該頁面為「已載入」(present in RAM)。
  6. 恢復執行： OS 將控制權交還給 CPU，CPU 會重新執行導致分頁錯誤的那條指令。這次，CPU 應該能夠成功存取該記憶體頁面。

  注意： 讀取硬碟的 I/O 操作是相對緩慢的，因此分頁錯誤的處理會顯著影響程式的執行速度。

6.2. 換頁 (Thrashing) 的概念及其影響

• 定義：
  「換頁」(Thrashing) 是指系統花費了絕大部分時間在頁面交換 (page swapping) 上，而不是在實際執行程式碼。當系統中的總記憶體需求（所有行程所需的實體記憶體）遠遠超過實際可用的實體記憶體時，就可能發生換頁。
• 發生原因：
  當記憶體不足時，OS 不得不頻繁地將 RAM 中的頁面換出到硬碟，然後再將需要的頁面換入。如果系統中的行程都處於「活躍」狀態，並且它們所需的頁面集合之間有很大的重疊，但總體所需的頁面數量又很大，那麼 OS 就會不斷地在不同頁面之間進行交換，導致 CPU 大部分時間都在等待硬碟 I/O，而不是執行計算。
• 對系統效能的影響：

核心觀念

本題考查：

• Fibonacci sequence 的遞迴定義
• 以迭代法取代遞迴法
• 時間複雜度與空間複雜度分析
• 變數不隨輸入規模增加的常數記憶體使用方式

題目給定：

$$a_0=0,\qquad a_1=1$$

且對所有 $n\ge 2$：

$$a_n=a_{n-1}+a_{n-2}$$

若直接使用遞迴，會重複計算大量相同子問題，時間複雜度為指數級，且遞迴呼叫堆疊也不符合最佳的空間要求。因此應依序由 $a_0$、$a_1$ 往後計算。

解題方法

只需保存最近兩項：

• prev：目前的 $a_{i-1}$
• curr：目前的 $a_i$

計算下一項時：

$$a_{i+1}=a_i+a_{i-1}$$

計算後同步更新兩個變數：

$$(a_{i-1},a_i)\leftarrow(a_i,a_{i-1}+a_i)$$

初始狀態為：

$$(prev,curr)=(a_0,a_1)=(0,1)$$

每次迴圈將目前位置向後推進一項，共需執行 $n-1$ 次，最後 curr 即為 $a_n$。

關鍵程式碼

以下使用 C++：

long long fibonacci(int n) {
    if (n == 0) {
        return 0;
    }

    long long prev = 0;  // a_0
    long long curr = 1;  // a_1

    for (int i = 2; i <= n; ++i) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }

    return curr;
}

此程式假設輸入滿足 $n\ge 0$。若題目允許負整數，則必須另外定義負索引 Fibonacci 數列，題目目前未提供此定義。

正確性說明

迴圈開始前，變數滿足：

$$prev=a_0,\qquad curr=a_1$$

假設某次迴圈開始時：

$$prev=a_{i-1},\qquad curr=a_i$$

計算：

本題主要在考驗對遞迴結構、二元樹 (Binary Tree) 的生成與特性（特別是高度），以及如何避免重複生成相同結構的問題。題目要求生成所有高度小於等於 $n$ 的二元樹，並估計時間複雜度。

核心觀念：

• 二元樹的遞迴定義： 一棵二元樹由一個節點（根節點）以及其左子樹和右子樹組成。左子樹和右子樹本身也是二元樹（或為空）。
• 樹的高度： 從根節點到最遠葉節點的最長路徑長度。單一節點樹的高度為 1。
• 無重複生成： 需要確保每棵生成的樹都是獨一無二的。

8.1. 生成所有高度 $\le n$ 的二元樹的演算法

這個問題可以透過遞迴來解決。一棵高度小於等於 $n$ 的二元樹，其根節點可以有：

• 一個空左子樹和一個高度小於等於 $n-1$ 的右子樹。
• 一個高度小於等於 $n-1$ 的左子樹和一個空右子樹。
• 一個高度小於等於 $n-1$ 的左子樹和一個高度小於等於 $n-1$ 的右子樹。
• 以及一個只有根節點（高度為 1）的樹。

為了避免重複，我們可以定義一個函數 generate_trees(h)，它返回一個包含所有高度恰好為 h 的二元樹的列表。然後，我們就可以遍歷所有高度從 1 到 $n$，並將生成的樹收集起來。

演算法步驟：

1. 基本情況：

   • 如果需要生成高度為 0 的樹，則返回包含一個空樹 (null) 的列表。
   • 如果需要生成高度為 1 的樹，則返回包含一個只有根節點（沒有子節點）的樹的列表。

2. 遞迴步驟 (生成高度為 h 的樹)：

   • 假設我們有一個函數 generate_trees_exactly(h)，它返回所有高度恰好為 h 的二元樹的列表。
   • 為了生成高度為 h 的樹：
     • 遍歷所有可能的高度 left_h 從 0 到 h-1。
     • 對於每一個 left_h，遍歷所有可能的高度 right_h 從 0 到 h-1。
     • 條件： 必須滿足 max(left_h, right_h) + 1 = h。這意味著至少有一個子樹的高度必須是 h-1，而另一個子樹的高度可以從 0 到 h-1。
     • 從 generate_trees_exactly(left_h) 獲取所有左子樹。
     • 從 generate_trees_exactly(right_h) 獲取所有右子樹。
     • 對於每一對 (左子樹, 右子樹)，創建一個新的根節點，將其左子樹設為當前左子樹，右子樹設為當前右子樹。將這個新創建的樹加入結果列表。

3. 主函數 generate_trees_le(n)：

   • 初始化一個空的結果列表 all_trees。
   • 如果 $n \ge 1$，創建一個只有根節點的樹，並加入 all_trees。
   • 遍歷高度 h 從 2 到 $n$：
     • 呼叫 generate_trees_exactly(h)，並將返回的所有樹加入 all_trees。
   • 最後，為了處理空樹（高度為 0），如果 $n \ge 0$，可以選擇性地將 null 加入 all_trees，這取決於題目對「高度 $\le n$」的解釋是否包含空樹。通常，單一節點高度為 1，所以空樹高度為 0。如果題目要求生成所有非空樹，則從 $n \ge 1$ 開始。根據題目註解「A tree with a single node has height = 1」，這意味著空樹的高度是 0。所以我們要生成高度從 0 到 $n$ 的樹。

優化與避免重複：
上述方法可能會生成重複的樹結構，特別是當左右子樹的結構相同但位置不同時。一個更常見且有效的遞迴方法是：

遞迴函數 generate_trees_with_height(h)：
此函數生成所有高度恰好為 h 的二元樹。

• Base Case:
  • h = 0: 返回包含 null (代表空樹) 的列表。
  • h = 1: 返回包含一個只有根節點 (Node with null left and null right) 的列表。
• Recursive Step:
  • 初始化一個空列表 result_trees。
  • 遍歷所有可能的左子樹高度 left_h 從 0 到 h-1。
  • 遍歷所有可能的右子樹高度 right_h 從 0 到 h-1。
  • 條件判斷： 為了確保總高度恰好是 h，必須滿足 max(left_h, right_h) + 1 == h。
  • 獲取所有左子樹：left_subtrees = generate_trees_with_height(left_h)
  • 獲取所有右子樹：right_subtrees = generate_trees_with_height(right_h)
  • 對於 left_subtrees 中的每一個左子樹 l：
    • 對於 right_subtrees 中的每一個右子樹 r：
      • 創建一個新的節點 root。
      • root.left = l
      • root.right = r
      • 將 root 加入 result_trees。
  • 返回 result_trees。

主調用函數 generate_all_trees_le_n(n)：

• 初始化一個空列表 all_generated_trees。
• 遍歷所有高度 h 從 0 到 $n$：
  • 呼叫 generate_trees_with_height(h)。
  • 將返回的樹列表中的所有樹加入 all_generated_trees。
• 最後，遍歷 all_generated_trees，對每一棵樹呼叫 print(tree)。

範例程式碼 (Python 概念性)：