清大 107 年資應所 計算機概論 參考答案

$1-{\displaystyle \frac{11\times 10\times 9}{{11}^3}}={\displaystyle \frac{31}{121}}\approx 0.256$

5 筆。4 筆時碰撞機率約 0.459，5 筆時約 0.656，首次超過一半。

平面 $y+z=2$；$(0,2,1)$ 對平面的鏡射點為 $(0,1,0)$；光源 $(0,1,2)$ 與 $(0,1,0)$ 的連線交平面於 $P=(0,1,1)$。

1. 狀態：以 (農夫, 狐狸, 鵝, 豆子) 表示四者各在左岸 L 或右岸 R，共 $2^4=16$ 種組合。
2. 合法狀態：不可出現「狐狸與鵝同岸而農夫不在」或「鵝與豆子同岸而農夫不在」。
3. 起始狀態 (L, L, L, L)，目標狀態 (R, R, R, R)。
4. 產生規則（農夫每次必定過河，船上最多再帶一樣與他同岸的東西）：
   • 農夫獨自過河。
   • 農夫帶狐狸過河。
   • 農夫帶鵝過河。
   • 農夫帶豆子過河。 規則套用後的新狀態必須合法才可採用。
5. 控制系統：從起始狀態依規則產生新狀態，以 BFS 等方式搜尋狀態圖，找到通往目標狀態的路徑。

（如手寫圖）

狀態以 (農夫, 狐狸, 鵝, 豆子) 表示，L 為原岸、R 為對岸：

最差情況最少 9 次。剩 $t$ 次、$b$ 艘船可分辨 $F(t,b)={\sum }_{i=1}^b\left(\genfrac{}{}{0ex}{}{t}{i}\right)$ 個值，$F(8,3)=92<99\le F(9,3)=129$。

• 三艘船：依序載 38、67、89、100 塊（每次比上次多 $F(t-1,2)+1$，超過 100 時載 100）。
• 沉一艘後剩兩艘、剩 $t$ 次：每次比已知可載的值多 $t$ 塊，不超過沉船載重減 1。
• 只剩一艘：從已知可載的值加 1 起逐塊測試。

展開得 $T(n)=T(1)+{\displaystyle \frac{n(n+1)}{2}}-1$，$T(n)=O(n^2)$（同時為 $\Theta (n^2)$）。

Master Theorem Case 2：$n^{{\log }_{2}2}=n$，$f(n)=2n=\Theta (n)$，$T(n)=O(n\log n)$（同時為 $\Theta (n\log n)$）。

演算法（任選一點為根，以後序走訪由葉往根處理）：

TreeVertexCover(T, r)
    for each vertex v in postorder of T rooted at r
        inX[v] = false
        for each child c of v
            if inX[c] == false
                inX[v] = true
    return { v | inX[v] == true }

正確性：

1. 是頂點覆蓋：樹的每條邊都是某個節點 $v$ 與其子節點 $c$ 之間的邊；若 $c$ 不在 $X$，演算法就把 $v$ 放進 $X$，所以每條邊至少有一端在 $X$。
2. 大小最小：對任一葉節點 $c$ 與其父節點 $v$，邊 $(v,c)$ 必須被覆蓋。若某最小覆蓋選了 $c$，把 $c$ 換成 $v$ 仍是覆蓋（$c$ 只連到 $v$），大小不變，所以存在包含 $v$ 的最小覆蓋。選定 $v$ 後，與 $v$ 相連的邊都已覆蓋，移除 $v$ 與其子樹中已處理的部分，剩下的森林依同樣理由遞迴，每一步的選擇都可延伸成最小覆蓋。後序走訪正是依序處理「子節點都已決定、自己尚未決定」的節點。

時間：後序走訪每個節點一次、每條邊檢查一次，樹有 $n-1$ 條邊，總時間 $O(n)$。

錯誤。分支度總和 $=2|E|$ 為偶數，奇數分支度頂點的個數必為偶數。

錯誤。比較式排序最差下界為 $\Omega (n\log n)$；Merge Sort 最差 $\Theta (n\log n)$ 為最佳，Quick Sort 最差 $\Theta (n^2)$ 不是。

錯誤。稠密圖 $|E|=\Theta (|V{|}^2)$，Kruskal 為 $O(|V{|}^2\log |V|)$，以陣列實作的 Prim 為 $O(|V{|}^2)$，Prim 較快。

錯誤。SAT 是 NP-complete，但 P 是否等於 NP 尚未解決，「沒有多項式時間演算法」並未被證明；若 P = NP 則存在。

錯誤。上中、左中、右中、下中的分支度皆為 5，奇數分支度頂點有 4 個，超過 2 個，不存在 Euler Path。

（一）開源軟體：原始碼公開，授權允許使用、修改與再散布。例：Linux 核心、Mozilla Firefox。

（二）閉源軟體：原始碼不公開，只能依授權合約使用。例：Microsoft Windows、Adobe Photoshop。

（三）差異：原始碼是否公開、使用者能否修改與再散布、營利方式（開源多靠支援服務，閉源多賣授權或訂閱）。

（一）邊界值分析（Boundary Value Analysis, BVA）是黑箱測試技術：錯誤多發生在輸入範圍的邊界（如 < 誤寫成 <=），所以在每個有效範圍的邊界上、邊界內側與邊界外側取值設計測試案例。

（二）有效範圍為 18～65：

17 與 66 檢查系統是否正確拒絕範圍外的年齡，18 與 65 檢查邊界本身是否被接受，19 與 64 確認邊界附近的有效值也正常。

三個堆疊為 A、B、C，要交換 A 中相鄰的兩筆資料 $x$（較上）與 $y$（緊接在 $x$ 下方），假設 A 中的資料值互不相同：

SwapAdjacent(A, B, C, x)
    count = 0
    while top(A) != x            // 把 x 上方的資料暫存到 B
        move top(A) to B
        count = count + 1
    move top(A) to C             // x 移到 C
    move top(A) to B             // y 移到 B
    move top(C) to A             // x 回到 A，位於原本 y 的位置
    move top(B) to A             // y 放回 A，位於 x 之上
    repeat count times           // 把暫存的資料依原順序放回 A
        move top(B) to A

範例：A 由底到頂為 1, 2, 3, 4, 5，交換 2 與 3（$x=3$、$y=2$）。