108 年 國立中央大學企業管理學系碩士班戊組《資料結構》

核心觀念

本題考驗「運算式（Expressions）的表示法轉換」，特別是將中序表達式（Infix Expression）轉換為後序表達式（Postfix Expression / 逆波蘭表示法 RPN）與前序表達式（Prefix Expression / 波蘭表示法 PN）。

轉譯的核心根據為以下兩大原則：

1. 運算子優先順序（Operator Precedence）：
   • 括號 () 擁有最高優先權。
   • 乘法 * 與除法 / 次之。
   • 加法 + 與減法 - 最低。
2. 運算子結合律（Associativity）：
   • 當運算子優先權相同時（如 + 與 -，或 * 與 /），採**由左至右（Left-to-Right）**結合。

轉換定義：

• 中序 (Infix)：$\text{Operand}_1 \quad \text{Operator} \quad \text{Operand}_2$
• 後序 (Postfix)：$\text{Operand}_1 \quad \text{Operand}_2 \quad \text{Operator}$
• 前序 (Prefix)：$\text{Operator} \quad \text{Operand}_1 \quad \text{Operand}_2$

---

解題方法

在研究所考試的手算解題中，最精準且不易犯錯的方法為完全加括號法（Parenthesis Method），其步驟如下：

1. 完全加括號：依據運算子的優先順序與結合律，為表達式中的每一個二元運算加上適當括號。
2. 運算子移動：
   • 轉後序 (Postfix)：將括號內的運算子移至該括號的右括號外側。
   • 轉前序 (Prefix)：將括號內的運算子移至該括號的左括號外側。
3. 消除括號：將所有括號去除，所得結果即為目標表達式。

---

選項分析

本題包含兩個非選擇題之獨立計算子題，以下進行完整結構拆解與逐步推導：

子題 (1) $p/q-x+y*z-p*q$

步驟一：依優先順序與結合律完全加括號

• 同優先權之乘除由左至右：$(p / q)$、$y * z$、$p * q$
• 同優先權之加減由左至右：
  $((((p / q) - x) + (y * z)) - (p * q))$

步驟二：轉後序表達式 (Postfix)

1. $(p / q) \to (p \ q /)$
2. $((p / q) - x) \to ((p \ q /) \ x -)$
3. $(y * z) \to (y \ z *)$
4. $(((p / q) - x) + (y * z)) \to (((p \ q /) \ x -) \ (y \ z *) +)$
5. $(p * q) \to (p \ q *)$
6. $((((p / q) - x) + (y * z)) - (p * q)) \to ((((p \ q /) \ x -) \ (y \ z *) +) \ (p \ q *) -)$
7. 消除括號：$p q / x - y z * + p q * -$

核心觀念

本題的核心在於多屬性檢索（Multi-Attribute Retrieval / Secondary Key Retrieval）與海量資料索引架構設計。主要涵蓋以下資料結構與系統設計觀念：

1. 主資料表與次要索引（Master Record Table & Secondary Index / Inverted Index）：
   • 為滿足「員工資料不重複儲存（No duplicate storage）」的條件，實際的完整紀錄（Record）僅能儲存於單一「主資料表（Master Table）」。
   • 為滿足「能透過任一屬性快速檢索（Quick access using any attribute）」，必須針對所有可查詢屬性（ID Number、Name、Occupation、Location）分別建立倒排索引（Inverted Index / Secondary Index）。索引項目僅儲存「屬性值（Key）」與「指向主表紀錄的指標或識別碼（Pointer / Record ID, RID）」。
2. 底層索引結構選型（B+ Tree / Hash Table）：
   • 為了能「擴充至海量資料（Scale up to huge number of records）」，索引結構應採用支援外部記憶體（Disk-based I/O）高度平衡的 $\text{B}^+$ 樹（$\text{B}^+$ Tree） 或 可延伸雜湊（Extendible Hashing）。以 $\text{B}^+$ 樹為例，兼具 $O(\log N)$ 點查詢、範圍查詢與高效磁區分頁管理能力。

---

解題方法

1. 資料結構架構設計

本設計由一個**主資料表（Master Table）與四個次要倒排索引表（Secondary Inverted Indices）**組成：

• 主資料表（Master Table / Primary Storage）：
  以連續區塊或堆積檔（Heap File）儲存每位員工的完整實體資料。每筆紀錄配發唯一的實體記憶體指標或紀錄識別碼（RID / Pointer，如 $\&A, \&B, \&C$）。
• 次要倒排索引（Secondary Indices）：
  針對 ID Number、Name、Occupation、Location 四個欄位各建構一棵 $\text{B}^+$ 樹或雜湊表。索引節點結構為：
  $\text{Index Entry} = \langle \text{Attribute Value (Key)}, \text{Pointer List to Master Record} \rangle$
  當多位員工具有相同屬性值時（例如多位工程師位於同城市），指標串列（Posting List）串接多個指向主表的指標。

---

2. 範例資料結構圖解（Example Data Representation）

針對題目給定的三筆員工資料（A, B, C），資料結構的配置與指標指向關係如下：

(1) 主資料表（Master Record Table）

RID / Pointer	ID Number	Name	Occupation	Location
&A	10	Mary	Accountant	Taipei
&B	20	Kathy	Consultant	Taichung
&C	30	Maria	Programmer	Tainan

(2) 倒排次要索引表（Secondary Inverted Indices）

• ID Number Index：
  • 10 $\to [\&A]$
  • 20 $\to [\&B]$
  • 30 $\to [\&C]$
• Name Index：
  • "Kathy" $\to [\&B]$
  • "Maria" $\to [\&C]$
  • "Mary" $\to [\&A]$
• Occupation Index：
  • "Accountant" $\to [\&A]$
  • "Consultant" $\to [\&B]$
  • "Programmer" $\to [\&C]$
• Location Index：
  • "Taichung" $\to [\&B]$
  • "Tainan" $\to [\&C]$
  • "Taipei" $\to [\&A]$

---

3. 基本操作（Operations）流程與複雜度

概念
設鏈結串列長度為 $n$，欲在一次遍歷中找出第 $\left\lfloor \frac{n}{3}\right\rfloor$ 個節點開始，往後共 $r+1$ 個節點，其中 $r=n\bmod 3$。
使用「快指針」一次前進 3 步，「慢指針」一次前進 1 步。當快指針不能再走滿 3 步時，慢指針即指向 $\left\lfloor \frac{n}{3}\right\rfloor$ 處；快指針剩餘可走的步數即為 $r$，再沿慢指針往後走 $r$ 步即可取得所有答案節點。

程式（C++）