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

題面語法註記

題面中的 int v( )、int y( )、int x 與 char a( ) 應為陣列參數 int v[]、int y[]、int x[]、char a[]；(b) 的輸出敘述應補成 cout << a[i] << ' ';。以下依此符合題目意旨的版本作答；若完全依照貼上文字編譯，程式會因型別及字串引號錯誤而無法產生輸出。

(a)

核心觀念

函式參數中的陣列會自動調整成指標，因此：

int v[]
int x[]
int y[]
int z[]

在函式內等價於：

int *v
int *x
int *y
int *z

指標運算規則為：

$$p[i]=*(p+i)$$

以及：

$$\&e[j]+r=\&e[j+r]$$

陣列 e 傳入函式時會衰減為指向第一個元素的指標，即 &e[0]。

解題方法

陣列內容如下：

索引	0	1	2	3	4	5	6	7	8	9	10
e	10	11	12	13	14	15	16	17	18	19	20

各參數的起始位置：

參數	實際傳入	等價位置	函式內取值
v	&e[2] + 4	&e[6]	v[0]=e[6]=16
w	&e[2+4]	&e[6]	w[2]=e[8]
x	e	&e[0]	x[5]=e[5]=15
y	e+4	&e[4]	*(y+3)=e[7]=17
z	&e[2]	&e[2]	z[2]=e[4]=14

先執行：

w[2] += 4;

因為 w 指向 e[6]，所以：

$$w[2]=e[6+2]=e[8]$$

原本 e[8]=18，修改後：

$$e[8]=18+4=22$$

因此 printf 的五個欄位依序為：

$$v[0],\ w[2],\ x[5],\ *(y+3),\ z[2]$$ $$=16,\ 22,\ 15,\ 17,\ 14$$

解題技巧

先把每個指標寫成「指向哪一個 e[i]」，再將下標或位移量加上去，可避免指標偏移的常見錯誤。v 與 w 都指向 e[6]，但 v[0] 取 e[6]，w[2] 取 e[8]。

核心觀念

堆疊（stack）遵守後進先出（LIFO, Last In First Out）。輸入順序固定為

$$A\rightarrow B\rightarrow C\rightarrow D$$

每個符號各執行一次 PUSH，並各執行一次 POP，因此輸出必須是 $A,B,C,D$ 的某個排列。

題目中的：

• AXXX：輸出序列第一個符號是 A
• BXXX：輸出序列第一個符號是 B
• CXXX：輸出序列第一個符號是 C
• DXXX：輸出序列第一個符號是 D

每一組共有

$$3!=6$$

種排列。

合法的堆疊操作序列數為 Catalan number：

$$C_4=\frac{1}{4+1}\binom{8}{4}=14$$

因此全部 $4!=24$ 種排列中，共有

$$24-14=10$$

種是不可能的輸出。

---

解題方法

分別計算以 A、B、C、D 開頭的合法輸出數，再用 $6-$合法數得到不可能數。

1. 以 A 開頭：AXXX

A 可直接 PUSH 後 POP，此時堆疊清空，剩下 B、C、D 可形成 $C_3=5$ 種合法堆疊排列：

$$ABCD,\ ABDC,\ ACBD,\ ACDB,\ ADCB$$

以 A 開頭共有 $6$ 種排列，因此不可能的數量為

$$6-5=1$$

不可能序列為：

$$ADBC$$

---

2. 以 B 開頭：BXXX

要先輸出 B，必須先執行：

$$PUSH(A),\ PUSH(B),\ POP(B)$$

此時 A 仍在堆疊中，C、D 尚未全部處理。合法的完整輸出為：

$$BACD,\ BADC,\ BCAD,\ BCDA,\ BDCA$$

因此合法數為 $5$，不可能數為

$$6-5=1$$

不可能序列為：

$$BDAC$$

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的建立與刪除。

BST 的規則為：

• 每個節點左子樹的鍵值皆小於該節點。
• 每個節點右子樹的鍵值皆大於該節點。
• 對非葉節點進行刪除時，若採用「中序後繼」替代，則以該節點右子樹中的最小值取代它。
• 中序後繼就是右子樹最左側的節點。

解題方法

依序插入 $3,6,4,5,2,7,1$。

1. 插入 $3$，成為根節點。
2. 插入 $6$：$6>3$，放在 $3$ 的右子樹。
3. 插入 $4$：$4>3$ 且 $4<6$，放在 $6$ 的左子樹。
4. 插入 $5$：$5>3$、$5<6$、$5>4$，放在 $4$ 的右子樹。
5. 插入 $2$：$2<3$，放在 $3$ 的左子樹。
6. 插入 $7$：$7>3$ 且 $7>6$，放在 $6$ 的右子樹。
7. 插入 $1$：$1<3$ 且 $1<2$，放在 $2$ 的左子樹。

刪除前的 BST 為：

        3
       / \
      2   6
     /   / \
    1   4   7
         \
          5

現在刪除根節點 $3$。因為 $3$ 有左右兩棵子樹，屬於非葉節點，因此找其中序後繼：

核心觀念

本題使用 heapsort 的標準建堆方法：以 Floyd bottom-up heap construction 從最後一個非葉節點往根節點進行 heapify。

以 1-based 陣列表示 complete binary tree：

$$L(i)=2i,\qquad R(i)=2i+1,\qquad P(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

Max heap 必須符合：

$$A[P(i)]\ge A[i]$$

因此最大值一定位於根節點。若要由小到大排序，使用 max heap，每次將根節點最大值移到陣列尾端，再縮小 heap 範圍並恢復 heap。

---

(a) 建立 maximum heap

原始陣列為：

$$[14,4,19,2,18,7,17,9,16,13]$$

節點數為 $n=10$，最後一個非葉節點為：

$$\left\lfloor\frac{10}{2}\right\rfloor=5$$

因此依序處理節點 $5,4,3,2,1$。

1. 節點 $5$：$18$ 的子節點為 $13$，已符合 max heap。

2. 節點 $4$：$2$ 的子節點為 $9,16$，與較大的 $16$ 交換：

$$[14,4,19,16,18,7,17,9,2,13]$$

3. 節點 $3$：$19$ 的子節點為 $7,17$，已符合 max heap。

4. 節點 $2$：$4$ 的子節點為 $16,18$，先與較大的 $18$ 交換；交換後 $4$ 位於節點 $5$，再與子節點 $13$ 交換：

$$[14,18,19,16,13,7,17,9,2,4]$$

5. 節點 $1$：$14$ 的子節點為 $18,19$，先與 $19$ 交換；下移後的 $14$ 再與子節點中較大的 $17$ 交換：

$$[19,18,17,16,13,7,14,9,2,4]$$

所以第一階段完成後的 max heap 為：

                19
             /      \
           18        17
         /   \      /  \
       16    13    7   14
      /  \   /
     9    2 4

---

題意與假設

題幹未附所稱「以下問題」的後續子題與選項。以下依 Unix inode 的標準定義解答：inode 含有 10 個 direct pointers，以及各 1 個 single indirect、double indirect、triple indirect pointer。

作業系統慣例採 $8\text{ Kbytes}=8\times1024=8192$ bytes。

---

核心觀念

每個 indirect block 用來存放指標，因此一個間接區塊可容納的指標數為

$$P=\frac{\text{block size}}{\text{pointer size}} =\frac{8192}{8}=1024=2^{10}$$

因此：

• 1 層間接：可指向 $P=1024$ 個資料區塊。
• 2 層間接：可指向 $P^2=1024^2=1,048,576$ 個資料區塊。
• 3 層間接：可指向 $P^3=1024^3=1,073,741,824$ 個資料區塊。

間接區塊本身是索引資料，不計入檔案內容容量。

---

解題方法與計算

inode 指標類型	可容納的資料區塊數	可儲存的檔案資料量
10 個 direct blocks	$10$	$10\times8\text{ KiB}=80\text{ KiB}$
Single indirect	$1024$	$1024\times8\text{ KiB}=8\text{ MiB}$
Double indirect	$1024^2=1,048,576$	$8\text{ GiB}$
Triple indirect	$1024^3=1,073,741,824$	$8\text{ TiB}$

最大資料區塊數為

$$10+1024+1024^2+1024^3 =1,074,791,434\text{ 個區塊}$$

最大檔案大小為

$$\begin{aligned} F_{\max} &=1,074,791,434\times8192\\ &=8,804,691,427,328\text{ bytes} \end{aligned}$$

也可表示為

$$F_{\max} =8\text{ TiB}+8\text{ GiB}+8\text{ MiB}+80\text{ KiB}$$

約為 $8.805$ TB，亦即約 $8.008$ TiB。

---

核心觀念

本題考查轉址後備緩衝區（TLB）的命中率與平均記憶體轉址額外成本。

• TLB 查詢時間：$50$ ns。
• TLB 命中時：不需查詢記憶體中的 page table，因此額外成本為 $50$ ns。
• TLB 未命中時：除了已花費的 $50$ ns 查詢時間，還需讀取 page table，增加 $500$ ns。

設 TLB 命中率為 $h$，則未命中率為 $1-h$。

解題方法

平均額外成本為：

$$\begin{aligned} \text{平均成本} &= h(50)+(1-h)(50+500) \\ &= 50h+(1-h)550 \\ &= 550-500h \end{aligned}$$

題目要求平均成本不超過 $100$ ns，因此：

$$550-500h\leq 100$$ $$-500h\leq -450$$ $$h\geq 0.9$$

因此，TLB 命中率至少必須為：

$$h=90\%$$

也可將平均成本寫成「固定的 TLB 查詢成本」加上「未命中時額外的 page table 成本」：

核心觀念

磁碟讀取一個 block 的平均時間由三部分組成：

$$T_{\text{block}} = T_{\text{seek}} + T_{\text{rotational}} + T_{\text{transfer}}$$

其中：

• $T_{\text{seek}}$：磁頭移動至目標 cylinder 的搜尋時間。
• $T_{\text{rotational}}$：等待目標 block 旋轉至磁頭下方的旋轉延遲。
• $T_{\text{transfer}}$：實際傳輸 block 資料的時間。

讀取 100 個 block 時，包含第一個 block 的初始定位，以及後續 99 個邏輯相鄰 block 的定位；依題目提供的平均模型，總共計算 100 次平均 block 讀取成本。

單位換算：

$$20\ \mu s=0.02\ ms$$

題目中的「每個 cylinder 有 10 個 tracks、每個 track 有 512 個 blocks」不需另外代入，因為搜尋時間、旋轉延遲與單一 block 的傳輸時間均已直接給定。

解題方法

情況一：未進行 block clustering

每個 block 的平均讀取時間為：

$$T_{\text{block}} = 5+10+0.02 = 15.02\ ms$$

因此 100 個 block 的總時間為：

$$T_{\text{unclustered}} = 100\times 15.02 = 1502\ ms = 1.502\ 秒$$

分項計算如下：

核心觀念

Bitmap（位元圖）會以「每一個配置單位使用 1 bit」記錄記憶體是否可用。

本題的配置單位為 $4\text{ KB}$，因此：

• 每 $4\text{ KB}$ 記憶體需要 $1$ bit。
• 先計算整體 RAM 可分成多少個 $4\text{ KB}$ 單位。
• 再將所需 bit 數換算成 byte 與 KB。

解題方法

依作業系統慣例：

$$1\text{ GB}=1024\text{ MB}=1024^2\text{ KB}$$

因此，$8\text{ GB}$ RAM 等於：

$$8\times 1024^2\text{ KB} =8,388,608\text{ KB}$$

每個配置單位為 $4\text{ KB}$，可分成：

$$\frac{8,388,608\text{ KB}}{4\text{ KB}} =2,097,152$$

個配置單位。

Bitmap 每個配置單位使用 $1$ bit，所以需要：

$$2,097,152\text{ bits}$$

將 bit 換成 byte：

$$\frac{2,097,152}{8} =262,144\text{ bytes}$$

再換成 KB：

核心觀念

虛擬位址可分為：

$$\text{Virtual Address}=\text{Virtual Page Number}+\text{Page Offset}$$

頁面大小為 $4\text{ KB}=2^{12}$ bytes，因此頁內位移需要 $12$ bits。

每一個虛擬頁面對應頁表中的一個 entry，所以頁表 entry 數量等於虛擬頁面數量。

解題方法

虛擬位址共 $48$ bits，總虛擬位址空間為：

$$2^{48}\text{ bytes}$$

每頁大小為 $2^{12}$ bytes，因此虛擬頁面數為：

$$\frac{2^{48}}{2^{12}} =2^{48-12} =2^{36}$$

所以需要的頁表 entry 數量為：

$$\boxed{2^{36}\text{ entries}}$$