109 年 國立中正大學資訊工程學系碩士班乙組《計算機概論》

此題主要在測試 C 語言中指標的運算、陣列的記憶體布局，以及 little-endian 架構下多位元組資料的儲存方式。

程式碼首先宣告一個 3x3 的整數陣列 A，並初始化其值。接著，將 A 的起始位址轉換為整數指標 ptr1 和字元指標 ptr2。little-endian 的特性是指最低有效位元組（Least Significant Byte, LSB）儲存在較低的記憶體位址。

1. ptr1 = (int*) A;：ptr1 指向陣列 A 的第一個元素，即 A[0][0]。
2. printf("%d\n", *ptr1);：印出 ptr1 所指向的整數值，也就是 A[0][0]，其值為 1。
3. printf("%d\n", *(ptrl+LOC(1,1)));：LOC(1,1) 會計算出 1*3+1 = 4。因此，此處等於 *(ptr1+4)。由於 ptr1 是指向 int 型別的指標，每個 int 型別通常佔 4 個位元組（假設）。所以 ptr1+4 會指向陣列 A 中第 5 個整數元素（從 0 開始計數），即 A[1][1]，其值為 5。
4. printf("%d\n", ptr1 [LOC(2,1)]);：LOC(2,1) 計算出 2*3+1 = 7。

核心觀念

這題考察 C 語言指標與雙重指標，以及函式透過指標修改呼叫端變數的方式。

• int *p 表示 p 是「指向 int 的指標」。
• int **q 表示 q 是「指向 int * 的指標」。
• *q 會取出 q 指向的指標；**q 再取出該指標所指向的整數。
• 函式參數若是 int **，函式內可透過 *a 修改呼叫端的 int * 變數。

解題方法

題目程式有兩處型別錯誤，因此照原文無法產生有效輸出：

1. 宣告 int **x1, y1, z1, **x2, y2, z2; 中，只有 x1 和 x2 是 int **；y1、z1、y2、z2 都是 int。因此 y1 = &z1 不符合型別，後續 *y1 也無法對整數解參照。
2. 即使將 y1、y2 改宣告為 int *，第二個 printf 仍以 %d 輸出指標 y2，格式指定與引數型別不符，行為未定義。

依程式其餘內容推定，原意是將 y1、y2 宣告為 int *，並在第二個 printf 使用 *y2。以下依此修正推導。

初始狀態：

變數	指向／內容
z1	10
z2	20
y1	指向 z1
y2	指向 z2
x1	指向 y1
x2	指向 y2

第一個 printf：

核心觀念

本題考查動態記憶體管理中的兩類錯誤：

1. Memory leak（記憶體洩漏）
   使用 malloc() 配置記憶體後，沒有保留可存取該區塊的指標，也沒有呼叫 free() 釋放，導致該區塊無法再次使用。

2. Double-free error（重複釋放）
   同一個記憶體區塊已經呼叫過 free()，又再次對相同區塊呼叫 free()。這屬於未定義行為。

3. Invalid free（錯誤位置釋放）
   free() 必須接收 malloc()、calloc() 或 realloc() 回傳的原始指標。若指標經過 ptr++ 移動後再傳給 free()，就不是原始位址，不能直接釋放。

判斷原則是：

• 每一次成功的 malloc()，都必須對應一次且僅一次的 free()。
• free(ptr) 後，ptr 不可再用來存取資料，也不可再次 free(ptr)。
• 覆寫指標前，必須先釋放原本指向的記憶體。

---

(a) Code Fragment (1)

問題分析

L8  ptr = (int*) malloc(10);
L9  *ptr = 2020;
L10 printf("%d\n", *ptr);

L11 ptr = (int*) malloc(20);

在 L8 配置的記憶體原本由 ptr 指向，但到了 L11，ptr 被新的 malloc(20) 回傳值覆寫。

因此，L8 配置的記憶體失去唯一指標，之後無法呼叫 free()，形成 memory leak。

L15 的：

free(ptr);

只會釋放 L11 配置的記憶體，不能釋放 L8 的記憶體。

修正方法

在覆寫 ptr 前釋放原本的記憶體：

L8  ptr = (int*) malloc(10);
L9  *ptr = 2020;
L10 printf("%d\n", *ptr);
L11 free(ptr);

L12 ptr = (int*) malloc(20);
L13 ptr[0] = 10;
L14 ptr[1] = 20;
L15 printf("%d %d\n", *ptr, ptr[1]);
L16 free(ptr);

題目原始行號下，答案可表示為：

在原 L11 前插入 free(ptr);

補充

實務上較安全的寫法是依照資料型別配置空間：

ptr = malloc(10 * sizeof *ptr);

本題重點在記憶體生命週期，不在 malloc() 的配置大小。

---

Code Fragment (2)

問題分析

for (i=0; i<100; i++) {
    ptr = (int*) malloc(10);
    *ptr = i+1;
    printf("%d\n", *ptr);
}
free(ptr);

每次迴圈都會配置一個新的記憶體區塊。

以迴圈前幾次為例：

• 第 0 次：配置區塊 A，ptr 指向 A。
• 第 1 次：配置區塊 B，ptr 改指向 B，A 未釋放。
• 第 2 次：配置區塊 C，ptr 改指向 C，B 未釋放。

迴圈結束後，L13 的 free(ptr) 只會釋放最後一次配置的區塊，前面 $99$ 個區塊全部 memory leak。

本題沒有 double-free，因為每個配置區塊最多只被釋放一次；問題是釋放時機錯誤。

修正方法

每次使用完該次配置的記憶體後立即釋放：

for (i=0; i<100; i++) {
    ptr = (int*) malloc(10);
    *ptr = i+1;
    printf("%d\n", *ptr);
    free(ptr);
}

原本迴圈外的 L13：

free(ptr);

必須刪除，否則最後一次配置的記憶體會在迴圈內被釋放一次，迴圈外又被釋放一次，形成 double-free。

題目要求的修改可表示為：

將原 L13 的 free(ptr); 移到原 L11 後面，也就是每次迴圈中 printf() 後立即釋放。

釋放次數驗證

• malloc() 執行 $100$ 次。
• 迴圈內的 free() 執行 $100$ 次。
• 每一個配置區塊恰好釋放一次。

因此沒有 memory leak，也沒有 double-free。

---

Code Fragment (3)

問題一：覆寫指標造成 memory leak

L7 ptr = (int*) malloc(10);

for (i=0; i<100; i++) {
    L9 ptr = (int*) malloc(10);

L7 先配置一個記憶體區塊，但進入第一次迴圈後，L9 直接將 ptr 覆寫。因此 L7 配置的記憶體失去指標，形成 memory leak。

此外，每次進入下一輪迴圈時，前一輪配置的記憶體也會被新的位址覆寫，形成大量 memory leak。

問題二：ptr++ 後直接 free(ptr)

當 $i$ 為偶數時：

if (i%2 == 0) {
    ptr++;
}
free(ptr);

ptr 已經不再指向 malloc() 回傳的原始位址，而是指向下一個位置。free() 只能釋放原始指標，因此此時的 free(ptr) 是錯誤的。

當 $i$ 為奇數時，ptr 沒有增加，直接 free(ptr) 才是正確的。

修正方法

先釋放 L7 配置的記憶體，避免第一次進入迴圈時洩漏：

ptr = (int*) malloc(10);
free(ptr);

每一輪配置新的記憶體後，若 ptr++，先以 ptr-- 回到原始位址，再呼叫 free()：

此題考查二元樹的基本概念，包括節點的分類（葉節點與非葉節點）以及三種基本的樹狀遍歷方法（中序、前序、後序）。

二元樹的定義：

• 葉節點 (Leaf Node): 沒有子節點的節點。
• 非葉節點 (Non-leaf Node): 至少有一個子節點的節點。
• 根節點 (Root Node): 樹中最高層次的節點。

樹的遍歷方法：
假設一個二元樹節點包含左子節點 L、右子節點 R 和節點本身的值 N。

1. 前序遍歷 (Preorder Traversal): N L R (先訪問根節點，再遍歷左子樹，最後遍歷右子樹)
2. 中序遍歷 (Inorder Traversal): L N R (先遍歷左子樹，再訪問根節點，最後遍歷右子樹)
3. 後序遍歷 (Postorder Traversal): L R N (先遍歷左子樹，再遍歷右子樹，最後訪問根節點)

分析圖示中的兩棵二元樹：

第一棵樹 (左圖):
根節點為 A。
節點結構：

• A -> B (left), C (right)
• B -> D (left), E (right)
• C -> null (left), null (right)
• D -> null (left), null (right)
• E -> null (left), null (right)

第二棵樹 (右圖):
根節點為 A。
節點結構：

• A -> B (left), C (right)
• B -> D (left), E (right)
• C -> F (left), G (right)
• D -> H (left), null (right)
• E -> null (left), null (right)
• F -> null (left), null (right)
• G -> null (left), null (right)
• H -> null (left), null (right)

(a) 葉節點與非葉節點列表

第一棵樹：

• 葉節點 (Leaf Nodes): C, D, E
  • C 沒有子節點。
  • D 沒有子節點。
  • E 沒有子節點。
• 非葉節點 (Non-leaf Nodes): A, B
  • A 是根節點，有子節點 B 和 C。
  • B 有子節點 D 和 E。

第二棵樹：

• 葉節點 (Leaf Nodes): E, F, G, H
  • E 沒有子節點。
  • F 沒有子節點。
  • G 沒有子節點。
  • H 沒有子節點。
• 非葉節點 (Non-leaf Nodes): A, B, C, D
  • A 是根節點，有子節點 B 和 C。
  • B 有子節點 D 和 E。
  • C 有子節點 F 和 G。
  • D 有子節點 H。

(b) 遍歷結果

第一棵樹：

• 中序遍歷 (Inorder Traversal): D B E A C

  1. 從 A 開始，走到左邊的 B。
  2. 從 B 開始，走到左邊的 D。
  3. D 是葉節點，訪問 D。
  4. 回到 B，訪問 B。
  5. 從 B 走到右邊的 E。
  6. E 是葉節點，訪問 E。
  7. 回到 B，B 的左右子樹都已訪問，回到 A。
  8. 從 A 走到右邊的 C。
  9. C 是葉節點，訪問 C。
  10. 回到 A，A 的左右子樹都已訪問。結束。

• 前序遍歷 (Preorder Traversal): A B D E C

  1. 訪問根節點 A。
  2. 訪問 A 的左子樹：訪問 B。
  3. 訪問 B 的左子樹：訪問 D。
  4. D 沒有子節點，回到 B。
  5. 訪問 B 的右子樹：訪問 E。
  6. E 沒有子節點，回到 B。

這題是選擇題，每小題 2 分，答錯倒扣 3 分。考查了 C 語言的資料結構、演算法、樹、圖、雜湊表等計算機概論的核心概念。

(a) C 語言中 union 的記憶體共享

• 說明： 在 C 語言中，union 的所有成員共享同一塊記憶體空間，這塊空間的大小等於其中最大的成員的大小。同一時間，union 只能儲存其中一個成員的值。
• 判斷： True (T)。
• 原因： union 的核心特性就是成員共享記憶體。

(b) 深度為 10 的二元樹的最大節點數

• 說明： 一棵深度為 d 的二元樹，其最大節點數為 $2^{d+1}-1$。此處深度是指根節點為第 0 層，最大層數為 d。如果題目中的「深度 10」是指樹的高度為 10（即從根節點到最深葉節點的最長路徑的邊數為 10，節點數為 11 層，從 0 到 10），那麼最大節點數為 $2^{11}-1 = 2047$。
  如果「深度 10」是指樹的高度為 9（即有 10 層，從 0 到 9），那麼最大節點數為 $2^{10}-1 = 1023$。
  題目中的 1024 是 $2^{10}$。如果樹的「深度」是指層數（從 1 開始計數），那麼深度為 10 的樹有 10 層，最大節點數是 $2^{10}-1 = 1023$。
  常見的定義是： 深度為 $d$ 的樹，最多有 $2^{d+1}-1$ 個節點（如果根節點是第 0 層）。
  另一種定義是： 高度為 $h$ 的樹，最多有 $2^{h+1}-1$ 個節點（如果高度是邊數）。
  如果題目將「深度」理解為「層數」，則深度為 10 的樹有 10 層。
  • 第 1 層：1 個節點 ($2^0$)
  • 第 2 層：2 個節點 ($2^1$)
  • ...
  • 第 10 層：$2^9$ 個節點
    總節點數為 $1 + 2 + 4 + ... + 2^9 = 2^{10}-1 = 1023$。
    如果題目中的「深度 10」是指樹的高度為 10 (即有 11 層，從 0 到 10)，則最大節點數為 $2^{11}-1 = 2047$。
    1024 是 $2^{10}$，這通常是指第 10 層（從 0 開始數）的最大節點數。
    因此，題目說「最大節點數是 1024」是不正確的。
• 判斷： False (F)。
• 原因： 一棵深度為 10 的二元樹（假設根節點為第 0 層，則有 11 層）最多有 $2^{10+1}-1 = 2047$ 個節點。如果深度是指層數（從第 1 層開始），則深度為 10 的樹有 10 層，最多有 $2^{10}-1 = 1023$ 個節點。1024 是第 10 層（從 0 開始計數）的最大節點數，但不是整棵樹的最大節點數。

(c) in-place 反轉鏈結串列

• 說明： 在鏈結串列中，in-place 操作是指在不使用額外記憶體（或只使用常數級別的額外記憶體，例如幾個指標變數）的情況下完成操作。反轉鏈結串列只需要三個指標變數（前一個節點 prev、當前節點 curr、下一個節點 next）即可實現，不需要額外與鏈結串列大小成比例的記憶體。
• 判斷： True (T)。
• 原因： 反轉鏈結串列可以通過迭代或遞迴方式，利用幾個臨時指標變數來修改節點的 next 指標，從而實現 in-place 操作。

(d) heap vs. binary search tree 查詢效率

• 說明：
  • Heap (優先佇列): 主要用於快速找到最大或最小元素（O(1)），插入和刪除操作的時間複雜度為 O(log n)。但查詢任意元素是否存在的時間複雜度是 O(n)，因為需要遍歷整個堆。
  • Binary Search Tree (BST): 查詢、插入、刪除操作的平均時間複雜度為 O(log n)。在平衡的 BST 中，最壞情況時間複雜度也是 O(log n)。
• 判斷： False (F)。

此題考查 Minimum Spanning Tree (MST) 的兩種經典演算法：Kruskal 演算法和 Prim 演算法。題目要求根據給定的加權無向圖，分別寫出這兩種演算法的執行過程，即選取的邊的序列。

圖示分析：
圖中有 9 個節點 (a, b, c, d, e, f, g, h, i) 和若干條加權邊。
邊及其權重如下：

• (a, b): 4
• (a, h): 8
• (b, c): 2
• (b, h): 11
• (c, d): 7
• (c, i): 9
• (d, e): 9
• (d, i): 14
• (e, i): 6
• (f, g): 2
• (f, i): 6
• (g, h): 7
• (g, i): 1
• (h, i): 7

節點總數 N = 9。MST 的邊數應為 N-1 = 8。

演算法回顧：

• Kruskal 演算法：
  1. 將所有邊按權重從小到大排序。
  2. 初始化一個森林，每個節點自成一個連通分量。
  3. 依次檢查排序後的邊，如果一條邊連接的兩個節點屬於不同的連通分量，則選擇這條邊，並將這兩個節點所在的連通分量合併。
  4. 重複步驟 3，直到選取了 N-1 條邊。
• Prim 演算法：
  1. 從任意一個節點開始（本題指定從節點 a 開始），將其加入 MST。
  2. 維護一個集合，包含已加入 MST 的節點。
  3. 在每次迭代中，找到連接 MST 節點集合與非 MST 節點集合之間權重最小的邊。
  4. 將該邊和其連接的非 MST 節點加入 MST。
  5. 重複步驟 3 和 4，直到 MST 包含所有 N 個節點。

---

(a) Kruskal 演算法

1. 邊的權重排序：

   • (g, i): 1
   • (b, c): 2
   • (f, g): 2
   • (b, a): 4 (應為 a,b)
   • (c, d): 7
   • (g, h): 7
   • (e, i): 6
   • (f, i): 6
   • (a, h): 8
   • (c, i): 9
   • (d, e): 9
   • (b, h): 11
   • (d, i): 14
   • (h, i): 7 (這個邊權重是 7，需要重新排序)

   重新排序所有邊：

   1. (g, i): 1
   2. (b, c): 2
   3. (f, g): 2
   4. (a, b): 4
   5. (c, d): 7
   6. (g, h): 7
   7. (h, i): 7
   8. (e, i): 6
   9. (f, i): 6
   10. (a, h): 8
   11. (c, i): 9
   12. (d, e): 9
   13. (d, i): 14
   14. (b, h): 11

   正確排序：

   1. (g, i): 1
   2. (b, c): 2
   3. (f, g): 2
   4. (a, b): 4
   5. (e, i): 6
   6. (f, i): 6
   7. (c, d): 7
   8. (g, h): 7
   9. (h, i): 7
   10. (a, h): 8
   11. (c, i): 9
   12. (d, e): 9
   13. (b, h): 11
   14. (d, i): 14

2. 選擇邊 (共 N-1 = 8 條)：

   • 邊 (g, i), 權重 1: 連接 i 和 g。i, g 屬於不同集合。選擇。集合：{a}, {b}, {c}, {d}, {e}, {f}, {h}, {i, g}。
   • 邊 (b, c), 權重 2: 連接 b 和 c。b, c 屬於不同集合。選擇。集合：{a}, {b, c}, {d}, {e}, {f}, {h}, {i, g}。
   • 邊 (f, g), 權重 2: 連接 f 和 g。f 在 {f}，g 在 {i, g}。屬於不同集合。選擇。集合：{a}, {b, c}, {d}, {e}, {f, i, g}。
   • 邊 (a, b), 權重 4: 連接 a 和 b。a 在 {a}，b 在 {b, c}。屬於不同集合。選擇。集合：{a, b, c}, {d}, {e}, {f, i, g}。
   • 邊 (e, i), 權重 6: 連接 e 和 i。e 在 {e}，i 在 {f, i, g}。屬於不同集合。選擇。集合：{a, b, c}, {d}, {e, f, i, g}。
   • 邊 (f, i), 權重 6: 連接 f 和 i。f 和 i 都在 {e, f, i, g}。屬於同一集合。捨棄。
   • 邊 (c, d), 權重 7: 連接 c 和 d。c 在 {a, b, c}，d 在 {d}。屬於不同集合。選擇。集合：{a, b, c, d}, {e, f, i, g}。
   • 邊 (g, h), 權重 7: 連接 g 和 h。g 在 {e, f, i, g}，h 在 {h}。屬於不同集合。選擇。集合：{a, b, c, d}, {e, f, g, h, i}。
   • 邊 (h, i), 權重 7: 連接 h 和 i。h 和 i 都在 {e, f, g, h, i}。屬於同一集合。捨棄。
   • 邊 (a, h), 權重 8: 連接 a 和 h。a 在 {a, b, c, d}，h 在 {e, f, g, h, i}。屬於不同集合。選擇。集合：{a, b, c, d, e, f, g, h, i}。
   • 已選擇 8 條邊，圖已連通。結束。

   Kruskal 演算法選取的邊序列： (g, i), (b, c), (f, g), (a, b), (e, i), (c, d), (g, h), (a, h)

---

(b) Prim 演算法 (從節點 a 開始)

1. 初始化：

   • MST 節點集合：{a}
   • 邊集合（優先佇列）：{(a, b, 4), (a, h, 8)} (邊連接 MST 節點與非 MST 節點)

2. 迭代 1：

   • 從邊集合中選擇權重最小的邊：(a, b), 權重 4。
   • 將節點 b 加入 MST。
   • MST 節點集合：{a, b}
   • 更新邊集合：移除 (a, b)。加入與 b 相連但未在 MST 中的邊：(b, c, 2), (b, h, 11)。
   • 邊集合：{(a, h, 8), (b, c, 2), (b, h, 11)}

3. 迭代 2：

   • 從邊集合中選擇權重最小的邊：(b, c), 權重 2。
   • 將節點 c 加入 MST。
   • MST 節點集合：{a, b, c}
   • 更新邊集合：移除 (b, c)。加入與 c 相連但未在 MST 中的邊：(c, d, 7), (c, i, 9)。
   • 邊集合：{(a, h, 8), (b, h, 11), (c, d, 7), (c, i, 9)}

4. 迭代 3：

   • 從邊集合中選擇權重最小的邊：(c, d), 權重 7。
   • 將節點 d 加入 MST。
   • MST 節點集合：{a, b, c, d}
   • 更新邊集合：移除 (c, d)。加入與 d 相連但未在 MST 中的邊：(d, e, 9), (d, i, 14)。
   • 邊集合：{(a, h, 8), (b, h, 11), (c, i, 9), (d, e, 9), (d, i, 14)}

5. 迭代 4：

   • 從邊集合中選擇權重最小的邊：(a, h), 權重 8。
   • 將節點 h 加入 MST。
   • MST 節點集合：{a, b, c, d, h}
   • 更新邊集合：移除 (a, h)。加入與 h 相連但未在 MST 中的邊：(h, g, 7)。注意 (b, h) 和 (h, i) 的邊，b 和 h 都在 MST 節點集合中，所以 (b, h) 會被替換或捨棄。
     • 這裡需要仔細處理：當節點 h 加入 MST 後，需要檢查所有連接到 h 的邊。
     • (a, h) 已選。
     • (b, h) 權重 11。b 在 MST，h 在 MST。此邊連接兩個 MST 節點，不加入。
     • (g, h) 權重 7。g 不在 MST，h 在 MST。加入 (g, h, 7)。
     • (h, i) 權重 7。i 不在 MST，h 在 MST。加入 (h, i, 7)。
   • 邊集合：{(b, h, 11), (c, i, 9), (d, e, 9), (d, i, 14), (g, h, 7), (h, i, 7)}