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

最大 $+63$（0111111），最小 $-64$（1000000）。

${0000010}_2$，即十進位 $2$。

最小 Hamming Distance 為 3，最多可偵測 2 個錯誤、更正 1 個錯誤。

ACBD。

6 個位元。

F3。

1. File Manager（檔案管理程式）：記錄大容量儲存裝置上的檔案位置與目錄結構，管理檔案的建立、刪除、存取權限，並配置儲存空間。
2. Device Driver（裝置驅動程式）：與特定周邊裝置的控制器溝通，把 OS 的一般性要求轉成該裝置能執行的操作。
3. Memory Manager（記憶體管理程式）：配置與回收主記憶體，記錄各行程使用的區域，並以分頁等方式提供虛擬記憶體。
4. Scheduler（排程程式）與 Dispatcher（分派程式）：Scheduler 維護行程表，把新行程加入、移除已完成的行程；Dispatcher 依時間片把 CPU 分配給就緒的行程並做上下文交換（Context Switch）。

例子：時間片用完需要切換行程；程式發生除以零、非法記憶體存取等例外。機制：中斷，由硬體計時器發出計時器中斷強制把控制權交回 kernel。

(1) 陣列：依 level-order 存放，root 在索引 1，節點 $i$ 的左右子節點在 $2i$、$2i+1$，空節點留空格；走訪時以索引計算子節點，例如前序先處理 $i$ 再走 $2i$、$2i+1$。

(2) 指標：節點含資料與 left、right 指標，空子樹為 NULL；從 root 沿指標遞迴走訪（或以 stack、queue 改寫成迴圈）。

陣列需 $(2^L-1)A$ bytes，指標結構需 $N(A+2B)$ bytes；當 $(2^L-1)A<N(A+2B)$ 時陣列較省，也就是空格少（樹接近 full binary tree），且資料欄位 $A$ 相對指標 $B$ 越小越容易成立。

正確。取 $c_1=4$、$c_2=5$、$n_0=6$：$n\ge 6$ 時 $4n^2\le 5n^2-6n\le 5n^2$，故 $5n^2-6n=\Theta (n^2)$。

錯誤。若 $n^2\log n\le c_2{n}^2$ 對所有 $n\ge n_0$ 成立，則 $\log n\le c_2$；但取 $n=max(\lceil n_0\rceil ,\lceil 2^{c_2+1}\rceil )$ 時 $\log n>c_2$，矛盾，故不是 $\Theta (n^2)$。

int fact (int N){
  int result = 1;
  for (int i = 2; i <= N; i++)
    result = result * i;
  return result;
}

i = 0;
while (i < 100) {
  if (i % 2 == 0){
    print (i)
  }
  i++;
}

假設：tape 上以二進位存放數值，左右兩端各有一個 *；machine 從 START 狀態開始，讀寫頭位於右端的 *。

例：*101*（5）執行後為 *100*（4）；*100*（4）執行後為 *011*（3）。