110 年國立中山大學資訊工程學系碩士班甲組《作業系統與資料結構》考古題與詳解

Question 1

What would be the output of the following C program? (Note that the line numbers are for reference only.) 1. #include <stdio.h 2. #include <unistd.h 3. #include <sys/types.h 4. #include <sys/wait.h 5. int main() 6. { 7. int fd[2]; 8. pipe(fd); 9. pidt pid = fork(); 10. if (pid 0) { 11. close(fd[1]); 12. close(0); 13. dup(fd[0]); 14. close(fd[0]); 15. int status; 16. waitpid(-1, &status, 0); 17. char buf[128]; 18. int n = scanf("%s", buf); 19. printf("%d:%s
", n, buf); 20. } 21. else if (pid == 0) { 22. close(fd[0]); 23. close(1); 24. dup(fd[1]); 25. close(fd[1]); 26. execl("/bin/echo", "echo", "hello", "world!", (void) 0); 27. } 28. else { 29. return 1; 30. } 31. return 0; 32. }

Accepted Answer

核心觀念 這題考察 pipe、fork、檔案描述符重導向、waitpid，以及 scanf("%s", ...) 的讀取規則。 pipe(fd) 建立單向管線：fd[0] 是讀取端，fd[1] 是寫入端。fork() 後，父子程序各自持有這兩個描述符的副本。dup(fd) 會把描述符複製到目前可用編號最小的描述符。 解題方法 先追蹤父子程序各自的標準輸入與標準輸出，再沿著資料流判斷輸出內容。假設 pipe、fork、dup、execl 等呼叫都成功，且原本的標準輸入、標準輸出均有效。 子程序執行： 1. 關閉管線讀取端 fd[0]。 2. 關閉標準輸出 1。 3. dup(fd[1]) 將管線寫入端複製到描述符 1，因此子程序的標準輸出改接到管線。 4. execl 執行 /bin/echo，寫入 hello world!
。文字進入管線，不會直接顯示在終端機。 父程序執行：

Question 2

FCFS

Accepted Answer

核心觀念 FCFS（先到先服務）依照請求進入佇列的先後順序處理，不重新排序。磁臂移動距離是每次服務前後磁柱編號差的絕對值；總移動距離為各段距離的總和。 解題方法 目前磁頭位於第 $175$ 號磁柱，依 FIFO 順序處理請求： $$ 175 \rightarrow 50 \rightarrow 500 \rightarrow 225 \rightarrow 825 \rightarrow 350 \rightarrow 550 \rightarrow 400 \rightarrow 600 \rightarrow 100 $$ 逐段計算移動距離：

Question 3

LOOK

Accepted Answer

核心觀念

LOOK 排程會依磁頭目前的移動方向，先服務該方向上的請求；到達該方向最遠的待處理請求後，再反向服務另一側的請求。與 SCAN 不同，LOOK 不會為了到達磁碟邊界而多移動一段距離。

目前磁頭位於第 $175$ 柱面，前一次位於第 $125$ 柱面，因此磁頭正朝柱面編號增加的方向移動。

解題方法

先將請求依磁頭方向排序。從 $175$ 往上依序服務：

225 \rightarrow 350 \rightarrow 400 \rightarrow 500 \rightarrow 550 \rightarrow 600 \rightarrow 825

$825$ 是這個方向上最遠的待處理請求，因此磁頭在此反向，再依序服務 $100$ 、 $50$ 。

完整服務順序為：

Question 4

C-LOOK

Accepted Answer

核心觀念

C-LOOK 是 LOOK 的循環版本：磁頭依目前方向服務請求，直到該方向最遠的待處理請求；接著直接移到另一端尚未服務的請求，再沿原方向繼續服務。它不會為了到達磁碟邊界而移動。

題目中磁頭由 $125$ 移到目前的 $175$ ，方向為往較大的柱面前進，因此先由小到大服務。

解題方法

將待處理請求依柱面位置排序：

50,\ 100,\ 225,\ 350,\ 400,\ 500,\ 550,\ 600,\ 825

先服務目前位置 $175$ 以上的請求，再從最高請求 $825$ 循環移至最低請求 $50$ ，最後繼續往上服務 $100$ 。

磁頭移動距離為：

Question 5

SCAN

Accepted Answer

核心觀念

SCAN（電梯演算法）讓磁頭沿目前方向依序服務沿途請求，直到磁碟端點，再反向服務另一側的請求。磁頭目前位於 175，前一次請求位於 125，因此磁頭正朝較大的柱面號碼移動；SCAN 會先朝 1000 前進，再反向移動。

總移動距離只計算磁頭實際經過的柱面距離，不是請求數量。

解題方法

先將請求依柱面號碼排序：

50,\ 100,\ 225,\ 350,\ 400,\ 500,\ 550,\ 600,\ 825

磁頭由 175 向上移動，依序服務 225、350、400、500、550、600、825，接著繼續到柱面端點 1000。之後反向移動，依序服務 100、50。

路徑可表示為：

Question 6

C-SCAN

Accepted Answer

核心觀念

循環掃描（C-SCAN）讓磁頭固定朝同一方向服務請求。磁頭由目前位置往較大柱面號碼移動，途中依序服務請求；到達磁碟末端後，直接回到另一端，再繼續朝原方向服務剩餘請求。

前一次請求在 125，目前在 175，因此磁頭正朝柱面號碼增加的方向移動。柱面範圍為 0 至 1000。

解題方法

先將待處理請求依目前磁頭方向分成兩組：

大於 175：225、350、400、500、550、600、825
小於 175：50、100

Question 7

A computer whose processes have 2048 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 500 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (page, frame) pairs and can do a lookup in 50 nsec. What hit rate is needed to reduce the mean overhead to 150 nsec or less, assuming that the TLB is looked up first before the page table is read?

Accepted Answer

核心觀念 本題考 快取命中率與平均存取時間。TLB（快取轉譯旁查緩衝區）先查詢： - 命中：只花 $50$ nsec 查 TLB。 - 未命中：先花 $50$ nsec 查 TLB，再花 $500$ nsec 讀取記憶體中的頁表，總開銷為 $550$ nsec。 平均開銷依命中與未命中的機率加權計算。 解題方法 令 TLB 命中率為 $h$，則未命中率為 $1-h$。平均開銷為： $$ 50h + 550(1-h) $$ 題目要求平均開銷不超過 $150$ nsec，因此：

Question 8

What would be the size of the smallest file allowed in bytes?

Accepted Answer

核心觀念 題目問的是檔案的邏輯大小，也就是檔案內容的位元組數。i-node 的直接與間接區塊指標決定檔案可使用的區塊範圍，區塊大小則影響磁碟空間的配置；這些資訊不會讓檔案必須至少包含一個資料位元組。 在 UNIX 中，檔案可以是空檔案，i-node 儲存檔案的中繼資料，不必配置資料區塊。因此，空檔案的邏輯大小可以是 $0$ 位元組。 解題方法 直接判斷檔案內容所占的位元組數。若檔案沒有任何內容，其大小為：

Question 9

What would be the size of the largest file allowed in bytes?

Accepted Answer

核心觀念

i-node 可用直接區塊與多層間接區塊指向檔案資料。間接區塊本身用來存放指標，不算入檔案資料大小。

每個間接區塊可容納的指標數為：

\frac{\text{區塊大小}}{\text{指標大小}} = \frac{8 \times 1024}{8} = 1024

解題方法

直接區塊可指向 $16$ 個資料區塊；單、雙、三、四層間接區塊分別可指向 $1024$ 、 $1024^2$ 、 $1024^3$ 、 $1024^4$ 個資料區塊。因此，最多可容納的資料區塊數為：

Question 10

for (int j = 0; j < 400; j++) for (int i = 0; i < 400; i++) a[i][j] = 0;

Accepted Answer

核心觀念 本題考查分頁系統的位址換算、矩陣的 row-major 儲存，以及 LRU 頁面置換。 頁面大小為 $400$ bytes，因此位址 $x$ 所在頁號為： $$ \left\lfloor \frac{x}{400} ightfloor $$ 每個 double 佔 $8$ bytes，一列有 $400$ 個元素，所以每列佔： $$ 400 	imes 8 = 3200	ext{ bytes} = 8	ext{ pages} $$ 指令都在第 $0$ 頁，且該頁已放在 frame 0。總共只有兩個 frame 可供陣列資料頁使用。 解題方法 陣列採 row-major 儲存，元素 $a[i][j]$ 的位址是： $$ 400 + (400i+j)	imes 8 $$ 因此頁號為： $$ \left\lfloor\frac{400+(400i+j)	imes 8}{400}ightfloor = 1+8i+\left\lfloor\frac{j}{50}ightfloor $$ 固定一個欄索引 $j$，令 $k=\lfloor j/50floor$。內層迴圈依序存取 $i=0,1,\ldots,399$，對應頁號為：

Question 11

for (int i = 0; i < 400; i++) for (int j = 0; j < 400; j++) a[i][j] = 0;

Accepted Answer

核心觀念 分頁系統以「頁」為單位載入資料。當程式存取的頁不在記憶體中時，會發生一次 page fault。題目給定 3 個頁框，其中 1 個固定放置程式指令所在的第 0 頁，因此只有 2 個頁框可供陣列資料使用。 陣列採 row-major 儲存，元素依序排列。每個元素占 8 bytes，每頁大小為 400 bytes，因此每頁可容納： $$ \frac{400}{8}=50 $$ 個 double 元素。 解題方法 題目中的雙層迴圈依序寫入 a[0][0]、a[0][1]，直到 a[399][399]，也就是依照 row-major 順序連續存取所有元素。 陣列共有： $$ 400 	imes 400=160{,}000 $$ 個元素。每頁容納 50 個元素，因此陣列占用的頁數為： $$ \frac{160{,}000}{50}=3{,}200 $$

Question 12

int a = 48; printf("%d 
", (a & (-a)) 2);

Accepted Answer

核心觀念 這題考的是位元運算中的「取出最低位的 $1$」。對正整數 $a$，在二補數表示法下： $$ a \mathbin{\&} (-a) $$ 會保留 $a$ 最右邊的 $1$，並將其他位元清為 $0$。接著右移 2 位，相當於將結果除以 $2^2=4$。 解題方法 將 $48$ 轉成二進位： $$ 48 = 001100002 $$ 其負數 $-48$ 的二補數表示，低 8 位為： $$ -48 = 110100002 $$ 因此：

Question 13

int a = 68, b = 34, c = 25; printf("%d %d 
", a ^ a ^ a ^ b ^ a, (a ^ b ^ c ^ b ^ a ^ c ^ a) + 17); // ^: XOR

Accepted Answer

核心觀念

位元 XOR（互斥或）具有交換律與結合律，因此可以調整運算順序。常用性質為：

x \oplus x = 0,\qquad x \oplus 0 = x

所以同一個值出現偶數次會互相抵消；出現奇數次則保留一次。

解題方法

第一個參數中， $a$ 出現 4 次、 $b$ 出現 1 次：

a \oplus a \oplus a \oplus b \oplus a = (a \oplus a) \oplus (a \oplus a) \oplus b = b = 34

第二個參數中， $a$ 出現 3 次， $b$ 和 $c$ 各出現 2 次：

Question 14

Suppose that the preorder sequence of a binary tree is ABCDEFGH, and the inorder sequence is ABDAFGHE. What is the postorder sequence of the binary tree?

Accepted Answer

核心觀念 前序走訪依序為「根、左子樹、右子樹」；中序走訪依序為「左子樹、根、右子樹」。同一棵二元樹的前序與中序序列必須包含完全相同的節點，且每個節點出現次數相同。 解題方法 比較題目給的兩個序列： - 前序：ABCDEFGH，節點 A 至 H 各出現一次。 - 中序：ABDAFGHE，其中 A 出現兩次，且沒有 C。

Question 15

In the hash method, suppose that a rehash function $hi(x)=(5i+x)\bmod 13$ is applied sequentially when a new element is inserted into the hash table, but a hash collision occurs. In other words, $h1()$ is applied for the first time; $h2()$ is applied if a hash collision occurs; $h3()$ is applied if a hash collision occurs again; and so on. What is the content of the hash table after the elements 35, 22, 9, 24, 16, 19, 3 are inserted sequentially into an empty hash table of size 13, indexed as 0 through 12?

Accepted Answer

核心觀念 這題考查雜湊表的開放定址法。插入元素 $x$ 時，依序檢查 $$ hi(x)=(5i+x)\bmod 13,\qquad i=1,2,3,\ldots $$ 第一次檢查使用 $h1(x)$；若該位置已被占用，就使用下一個 $hi(x)$，直到找到空格。每插入一個元素後，該位置便固定占用。 解題方法 依題目給定順序逐一插入，並記下每個元素檢查的位置： | 插入元素 | 依序檢查的位置 | 放入位置 | |---:|---|---:| | $35$ | $h1(35)=(5+35)\bmod 13=1$ | $1$ | | $22$ | $h1(22)=1$（碰撞）；$h2(22)=(10+22)\bmod 13=6$ | $6$ | | $9$ | $h1(9)=1$（碰撞）；$h2(9)=6$（碰撞）；$h3(9)=(15+9)\bmod 13=11$ | $11$ | | $24$ | $h1(24)=(5+24)\bmod 13=3$ | $3$ | | $16$ | $h1(16)=(5+16)\bmod 13=8$ | $8$ | | $19$ | $h1(19)=11$（碰撞）；$h2(19)=3$（碰撞）；$h3(19)=8$（碰撞）；$h4(19)=(20+19)\bmod 13=0$ | $0$ |

Question 16

Please give the definition of an AVL binary search tree.

Accepted Answer

核心觀念 AVL 樹是一種自平衡二元搜尋樹。它同時符合兩項條件： 1. 二元搜尋樹性質：對每個節點 $v$，其左子樹中所有鍵值小於 $v$ 的鍵值，右子樹中所有鍵值大於 $v$ 的鍵值。 2. 高度平衡性質：對每個節點 $v$，左右子樹的高度差至多為 $1$： $$ \left|h(v.	ext{left})-h(v.	ext{right})ight|\leq 1 $$ 其中 $h(T)$ 表示子樹 $T$ 的高度。這項限制必須對樹中的每個節點成立，不能只檢查根節點。 解題方法 題目要求定義 AVL 二元搜尋樹，因此先說明它保有二元搜尋樹的鍵值順序，再補上 AVL 特有的平衡條件。 也可定義節點 $v$ 的平衡因子為：

Question 17

Assume that the initial AVL tree is empty. Please draw the AVL tree after the numbers 8, 9, 6, 3, and 2 are inserted into the tree sequentially. Then, please draw the AVL tree after the number 5 is inserted into the AVL tree obtained above.

Accepted Answer

核心觀念

AVL 樹是每個節點左右子樹高度差至多為 $1$ 的二元搜尋樹。定義平衡因子為：

BF(v)=h(\text{左子樹})-h(\text{右子樹})

每個節點都必須滿足 $|BF(v)|\le 1$ 。插入新值時，先依二元搜尋樹規則找到位置，再從插入位置往上檢查平衡因子；若有節點失衡，依插入方向進行旋轉。

以下以空樹高度為 $0$ 、葉節點高度為 $1$ 。

解題方法

依序插入 $8,9,6,3,2$ 。插入 $8,9,6,3$ 後，樹仍符合 AVL 平衡條件：

接著插入 $2$ 。依二元搜尋樹規則， $2$ 成為 $3$ 的左子節點：

節點 $6$ 的左子樹高度為 $2$ 、右子樹高度為 $0$ ，因此 $BF(6)=2$ ，是第一個失衡節點。新節點位於 $6$ 的左子節點 $3$ 的左側，屬於 LL 型，對節點 $6$ 做一次右旋：

這就是依序插入前五個數字後的 AVL 樹。

110 年 國立中山大學資訊工程學系碩士班甲組《作業系統與資料結構》

第 1 題10 分

核心觀念

解題方法

第 2-(a) 題2 分

第 2-(b) 題2 分

核心觀念

解題方法

第 2-(c) 題2 分

核心觀念

解題方法

第 2-(d) 題2 分

核心觀念

解題方法

第 2-(e) 題2 分

核心觀念

解題方法

第 3 題10 分

核心觀念

解題方法

第 4-(a) 題5 分

核心觀念

解題方法

第 4-(b) 題5 分

核心觀念

解題方法

第 5-(a) 題5 分

核心觀念

解題方法

第 5-(b) 題5 分

第 6-(a) 題5 分

第 6-(b) 題5 分

核心觀念

解題方法

第 7 題10 分

第 8 題15 分

核心觀念

解題方法

第 9-(a) 題5 分

核心觀念

解題方法

第 9-(b) 題10 分

核心觀念

解題方法

插入 5

其他考古題

110 年中山大學的其他科目

中山大學《作業系統與資料結構》其他年度

其他學校的資工系考古題

110 年國立中山大學資訊工程學系碩士班甲組《作業系統與資料結構》