109 年 國立中正大學資訊管理學系碩士班乙組《資料結構》

核心觀念

本題考查無向圖的表示法與頂點度數。社交網絡中的每個人是頂點，每條連線是邊；某頂點的度數，就是與它相連的邊數。題目所稱的 hub，是度數最大的頂點。

依圖中連線，頂點順序採 Bob、Charles、Justin、Jack、Mary、Tom。線段交叉處有跨線記號，表示交叉點不構成頂點，也不代表兩人相連。

解題方法

(a) 鄰接矩陣與鄰接串列

圖中邊為 Bob–Charles、Bob–Justin、Bob–Jack、Bob–Mary、Charles–Justin、Jack–Mary、Jack–Tom。因為是無向圖，鄰接矩陣沿主對角線對稱；相連填 $1$，不相連填 $0$。

	Bob	Charles	Justin	Jack	Mary	Tom
Bob	0	1	1	1	1	0
Charles	1	0	1	0	0	0
Justin	1	1	0	0	0	0
Jack	1	0	0	0	1	1
Mary	1	0	0	1	0	0
Tom	0	0	0	1	0	0

相同的圖也可用鄰接串列表示：

• Bob：Charles、Justin、Jack、Mary
• Charles：Bob、Justin
• Justin：Bob、Charles

核心觀念

AVL 樹是每個節點都符合平衡條件的二元搜尋樹。每個節點的平衡因子定義為：

$$BF=\text{左子樹高度}-\text{右子樹高度}$$

AVL 樹要求每個節點的 $BF$ 都是 $-1、0、1$。插入或刪除後若有節點失衡，便依失衡型態旋轉：

• LL 型：對失衡節點右旋。
• RR 型：對失衡節點左旋。
• LR 型：先對左子節點左旋，再對失衡節點右旋。
• RL 型：先對右子節點右旋，再對失衡節點左旋。

解題方法

依序按二元搜尋樹規則插入資料，每次插入後由下往上檢查平衡因子；若失衡，找出第一個失衡節點並旋轉修正。刪除時同樣先按二元搜尋樹規則刪除，再由下往上檢查 AVL 平衡條件。

(a) 依序插入六筆資料

插入 15：

15

插入 4：

  15
 /
4

插入 26：

  15
 /  \
4    26

插入 1：

    15
   /  \
  4    26
 /
1

插入 8：

    15
   /  \
  4    26
 / \
1   8

插入 14：

核心觀念

本題考查**雙向環狀鏈結串列（Double Circularly Linked List）**的基本操作與指標操作能力：

1. 結構定義：每個節點包含三個欄位：data（資料）、Rlink（指向右/下一個節點的指標）與 Llink（指向左/前一個節點的指標）。
2. 環狀特徵（Circular Property）：若串列非空，任一節點沿著 Rlink 最終都會繞回自身；終止遍歷的條件不是遇到 NULL，而是指針再次等於起始節點（例如 curr == Top）。
3. 節點計數（Counting）：需要注意串列是否為空（Top == NULL）的邊界情況；若非空，以 Top 為起點遍歷一圈回到 Top 即可統計節點總數。
4. 節點刪除（Deletion）：雙向環狀串列刪除節點需維護前驅與後繼節點的雙向指標。特別需處理邊界條件：
   • 串列為空串列（無節點）。
   • 串列僅剩單一節點（刪除後串列變為空串列）。
   • 欲刪除的節點恰好為指標變數 Top 所指的節點（刪除後需更新 Top）。
   • 找不到欲刪除的資料（資料不存在）。

---

解題方法

(a) 計算雙向環狀鏈結串列之節點數

1. 處理空串列：若 Top == NULL，直接回傳 0。
2. 走訪計數：設指標變數 curr = Top，計數器 count = 0。
3. 迴圈終止條件：採用 do-while 迴圈或先前進再判斷，每造訪一個節點 count++ 並將 curr = curr->Rlink，直到 curr == Top 為止，回傳 count。

(b) 刪除值為 'CCU' 的節點

1. 處理空串列：若 Top == NULL，串列為空，直接結束。
2. 搜尋目標節點：以 curr = Top 出發走訪環狀串列，比對 curr->data == "CCU"。若遍歷一整圈皆未找到，表示資料不存在，直接返回。
3. 刪除與指標重串接（Re-linking）：
   • 情況一：串列只有一個節點（curr->Rlink == curr）：釋放該節點記憶體，並將外部指標變數更新為 Top = NULL。
   • 情況二：串列有多個節點：
     • 若刪除的剛好是 Top 所指節點，需先將 Top 指向鄰近節點（例如 Top = curr->Rlink）。
     • 調整雙向鏈結：
       $curr\to Llink\to Rlink = curr\to Rlink$
       $curr\to Rlink\to Llink = curr\to Llink$
     • 釋放 curr 所佔用的記憶體。

---

程式實作

以 C/C++ 語法實作對應副程式（Subroutine）：

題目辨識

題目文字與附圖內容不一致；附圖實際顯示的是「八面骰子擲 100 次」的 C++ 題，以下依附圖中的第 B-4 題作答。

核心觀念

本題考查：

• 陣列索引與陣列大小的關係
• rand() 產生指定範圍亂數
• 頻率統計陣列
• 二維陣列的使用
• C++ 輸出欄位寬度 setw()

八面骰子的點數範圍為 $1$ 至 $8$，因此亂數應寫成：

$$1+\operatorname{rand}()\%8$$

頻率陣列至少需要索引 $0$ 至 $8$，其中索引 $0$ 不使用，因此大小應為 $9$。

（a）找出錯誤並修正

第 3 行錯誤

原程式：

int size = 7;

題目為八面骰子，骰面應為 $1$ 至 $8$，因此應改為：

int size = 8;

第 4 行

修正後：

int freq[size] = {};

此時陣列索引為 $0$ 至 $7$，無法存放骰面 $8$，因此必須配合索引方式改成：

int freq[size + 1] = {};

第 8 行錯誤

原程式只有存取陣列：

freq[1 + rand() % 7];

沒有將對應頻率加一，且亂數只會產生 $1$ 至 $7$。應改為：

freq[1 + rand() % 8]++;

修正後完整程式

int main()
{
    int size = 8;
    int freq[size + 1] = {};

    srand(time(0));

    for (int roll = 1; roll <= 100; roll++)
        freq[1 + rand() % size]++;

    cout << "Dice Face" << setw(13) << "Frequency" << endl;

    for (int face = 1; face <= size; face++)
        cout << setw(9) << face
             << setw(13) << freq[face] << endl;
}

複雜度

• 時間複雜度：$O(100)$，一般化為擲骰子 $m$ 次時為 $O(m)$
• 空間複雜度：$O(8)$，一般化為 $O(k)$，其中 $k$ 為骰面數

（b）統計兩顆八面骰子的結果

第一維表示第一顆骰子的點數，第二維表示第二顆骰子的點數，因此使用：

freq[firstFace][secondFace]

兩顆骰子的點數皆為 $1$ 至 $8$，所以二維陣列大小設為 $9 \times 9`，索引$0

核心觀念

本題考查深度優先搜尋（DFS）與廣度優先搜尋（BFS）的邊標記、頂點探索狀態，以及依指定順序追蹤演算法行號。DFS 遇到已探索的邊，只執行第 1、2 行；遇到尚未探索的邊，再檢查另一端頂點是否已探索。BFS 則將新發現的頂點排入下一層，並把連到已發現頂點的邊標記為交叉邊。

解題方法

圖 3(c) 是無向圖，頂點為 $1,2,3,4$，邊為 $a=(1,4)$、$b=(1,2)$、$c=(4,2)$、$d=(4,3)$、$e=(2,3)$，起點是頂點 $3$。各頂點依相連邊的字母順序掃描；以下只列有編號的敘述行。

(a) DFS

從頂點 $3$ 出發，先沿 $d$ 到 $4$，再沿 $a$ 到 $1$，再沿 $b$ 到 $2$。在頂點 $2$，邊 $c$、$e$ 尚未探索，但另一端頂點已探索，因此各執行第 7、8 行，標記為回邊。返回上層後，已標記的邊只會執行第 1、2 行。

目前頂點	掃描邊	處理情形	行號
3	d	發現頂點 4	1, 2, 3, 4, 5, 6
4	a	發現頂點 1	1, 2, 3, 4, 5, 6
1	a	邊已探索	1, 2
1	b	發現頂點 2	1, 2, 3, 4, 5, 6
2	b	邊已探索	1, 2
2	c	頂點 4 已探索，標記回邊	1, 2, 3, 4, 7, 8
2	e	頂點 3 已探索，標記回邊	1, 2, 3, 4, 7, 8
4	c	邊已探索	1, 2
4	d	邊已探索	1, 2
3	e	邊已探索	1, 2

(b) BFS

初始化後，先處理第 0 層 $\{3\}$，發現頂點 $4$、$2$。接著依序處理第 1 層 $\{4,2\}$：頂點 $4$ 經由 $a$ 發現頂點 $1$；