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

void D2B(int N) {
    if (N == 0 or N == 1) {
        print (N)
    } else {
        D2B(N / 2)
        print (N % 2)
    }
}

100101

$O(\log N)$：每次呼叫把 N 減半，N ≥ 1 時共 $\lfloor {\log }_{2}N\rfloor +1$ 次呼叫，每次常數時間。

$2.625={10.101}_2$

0 1000 010（01000010）

0.125

• 布林函數：$\text{Output}=\text{Input1}+\overline{\text{Input2}}$
• 電路：Input2 接一個 NOT 閘；NOT 閘的輸出與 Input1 接到一個 OR 閘；OR 閘的輸出為 Output。
• 共用 2 個閘（1 個 NOT、1 個 OR），少於 4 個。

（如手寫圖）

要在同一序列搜尋很多次時。設長度 n、搜尋 k 次，循序搜尋共約 $kn$，先排序再二分搜尋共約 $n\log n+k\log n$；k 大於約 $\log n$ 時二分搜尋較快，只搜尋少數幾次則循序搜尋較快。

1. 要找的值位在序列最前端附近（前 $\log n$ 個位置內），循序搜尋比較幾次就找到，二分搜尋仍要比較約 $\log n$ 次。
2. 序列很短時，二分搜尋計算中點與調整邊界的額外運算，抵銷了比較次數的差距。
3. 資料存在 linked list 等不能隨機存取的結構時，二分搜尋每次取中點都要從頭走訪，總時間為 $O(n)$ 且常數較大，循序搜尋較快。

$3nT$

$(n+2)T$

11 條：1 條控制連線（整個工作階段共用）＋10 條資料連線（每個檔案各開一條、傳完關閉）。

1. 連線導向（Connection-oriented）：傳送資料前以三向交握建立連線，結束時以 FIN（finish）區段關閉連線；UDP 不建立連線，直接送出資料報。
2. 可靠傳輸（Reliable Delivery）：以序號、確認（ACK）與逾時重傳確保資料送達且不重複；UDP 遺失的資料報不會重送。
3. 依序遞送（In-order Delivery）：接收端依序號重組，交給應用程式的位元組順序與送出時相同；UDP 不保證到達順序。
4. 流量控制（Flow Control）：接收端以通告視窗（rwnd）限制傳送端未被確認的資料量，避免接收緩衝區溢位；UDP 沒有這項機制。

1. 逾時（Timeout）：重傳計時器到期仍沒收到 ACK，表示區段可能在壅塞的路由器被丟棄。
2. 重複確認（Duplicate ACK）：連續收到 3 個確認同一序號的重複 ACK，表示序號等於該確認號的區段（接收端正在等待的下一個區段）可能遺失，但其後的區段仍送達。
3. 來回時間（RTT）上升：量測到的 RTT 持續增加，表示路由器的佇列變長、封包排隊等待的時間增加。

（一）Job queue：已選定執行、尚未載入記憶體的工作，等待長期排程器載入成為行程。

（二）Process queue（ready queue）：已在記憶體、處於就緒狀態等待 CPU 的行程（PCB），由短期排程器挑選執行。

$H\le n\le 2^H-1$（full binary tree 為 $2^H-1$）

最低高度為 20。

abc+×d+

（如手寫圖）

[!圖文轉錄]- 解答圖上的二元搜尋樹

              62
            /    \
          31      70
         /  \       \
       25    61      91
      /             /
    11            73
   /
  9
 /
6

• A：current
• B：next
• C：next->link
• D：previous
• E：current