111 年 國立中正大學電機工程學系碩士班計算機工程組《資料結構》

核心觀念

本題考查以陣列儲存佇列時，如何分開表示「佇列管理資訊」與「元素儲存區」。佇列頭記錄元素數量、隊首與隊尾索引、陣列容量，以及指向陣列的指標；佇列元素則存放在整數陣列中。

解題方法

依圖中的欄位順序定義佇列結構，並以動態配置的整數陣列作為儲存區。圖中元素數量為 $3$，front 為索引 $1$、rear 為索引 $3$；元素分別位於 Q[1]、Q[2]、Q[3]。

typedef struct {
    int count;       // 目前元素數量
    int front;       // 隊首元素的索引
    int rear;        // 隊尾元素的索引
    int maxSize;     // 陣列容量
    int *store;      // 指向佇列元素陣列
} Queue;

核心觀念

本題考查以陣列實作先進先出佇列（FIFO）。front 指向目前最早進入、下一個要取出的元素；rear 指向目前最後進入的元素；count 記錄元素數量；maxSize 是陣列容量。

圖中索引由 $1$ 開始。採用循環陣列時，索引到達 maxSize 後會回到 $1$：

以 count 區分空佇列與滿佇列，因此陣列的 maxSize 個位置都能使用。

解題方法

入列時，先檢查是否已滿。若佇列原本為空，將 front、rear 都設為 $1$；否則將 rear 循環前進一格，再存入新元素並增加 count。

出列時，先檢查是否為空。取出 front 所指元素後，若原本只有一個元素，將佇列清空並重設索引；否則將 front 循環前進一格，並減少 count。

以下程式以回傳值表示操作是否成功，出列的元素透過 out 傳回。

核心觀念

一般佇列遵守先進先出；優先佇列則依優先權決定取出順序。本題要求「數值越大，優先權越高」，因此每次取出時都要回傳目前最大的元素。

採用遞減排序陣列：佇列中的元素由 front 到 rear 依數值遞減排列，也就是 front 永遠指向最大值。

解題方法

插入新元素時，從 rear 往 front 找到適當位置，將較小的元素往後移，再插入新值。取出時直接回傳 front 的元素，並將 front 往後移一格。

以下程式假設陣列索引從 $0$ 開始，佇列不保存優先權相同元素的先後規則；插入相同值時，新元素會排在既有相同值之後。

核心觀念

本題考查堆積排序（Heap Sort）。要將陣列由小到大排序，使用最大堆積：每個父節點的值都不小於其子節點，因此根節點是堆積中的最大值。

以 0 起算的陣列索引表示二元堆積時，索引為 $i$ 的節點，其左子節點索引為 $2i+1$，右子節點索引為 $2i+2$。先將陣列整理成最大堆積，再反覆將根節點與未排序區間最後一個元素交換，並重新調整剩餘的堆積。每輪取出的最大值放到陣列尾端，最後得到升冪排列。

解題方法

以下採用原地排序，排序結果直接寫回輸入陣列。輔助函式 siftDown 將指定節點向下調整，使該節點為根的子樹恢復最大堆積性質。

題目資訊與假設

題目提到的「上述函式」程式碼未附上，因此無法依特定實作逐行計算。以下依標準 Heap Sort 分析：使用最大堆積排序成升冪，並以自底向上的方式建堆。

核心觀念

最大堆積中，每個父節點的鍵值都不小於其子節點。將最大值放到陣列末端，再對剩餘元素重新維護最大堆積，重複此步驟即可得到升冪排列。

時間分析分成兩部分：

1. 建立最大堆積。
2. 重複取出堆頂，並對縮小後的堆積執行下沉調整。

解題方法與計算

令陣列有 $n$ 個元素。

一、建立最大堆積：$O(n)$

以自底向上的方式建堆時，靠近葉節點的節點數量多，但下沉距離短；靠近根節點的節點數量少，但下沉距離較長。因此不能直接把每個節點都視為需要 $O(\log n)$，而應依節點高度加總。

高度為 $h$ 的節點數量至多約為 $\frac{n}{2^{h+1}}$，每個這類節點至多下沉 $h$ 層，因此建堆成本上界為：

核心觀念

題目要求儲存位數未知的整數，不能假設它們能放進固定大小的整數型別，例如 int 或 long long。應以多個節點表示一個整數，每個節點存一個十進位數字；整數的位數上限由可用記憶體決定。

解題方法

使用單向鏈結串列儲存每個整數，並讓串列由個位數開始排列。每個節點存一個 $0$ 至 $9$ 的數字：

typedef struct Node {
    int digit;              // 節點代表的十進位數字
    struct Node *next;
} Node;

typedef struct BigInteger {
    Node *head;             // 個位數節點
    size_t length;          // 位數
    int sign;               // 1 代表正數，-1 代表負數
} BigInteger;

例如，整數 $4729$ 表示為：

head → 9 → 2 → 7 → 4 → NULL

核心觀念

題目未附「上述資料結構」的定義。以下假設每個整數以單向鏈結串列表示，每個節點存一個十進位數字，並將個位數放在串列開頭。例如輸入 1234，串列會是 4 → 3 → 2 → 1。

這種順序方便後續由個位數開始逐位相加。由於數字位數未知，讀取時逐字元處理，不使用固定長度字元陣列。

解題方法

每次呼叫 readInteger，讀取輸入檔的一行，直到遇到換行或檔案結尾。遇到數字字元時，將其轉成整數後建立節點，並插入串列開頭。如此一來，讀取 1、2、3、4 後，串列自然成為 4 → 3 → 2 → 1。

以下程式假設輸入為非負整數，且每行只包含數字：

核心觀念

題目考查任意精度整數的加法。整數位數可能超過 C 語言內建整數型別的範圍，因此不能直接用 int 或 long long 儲存整數值；應將輸入視為十進位字串，逐位運算。

加法從個位數開始，令兩位數字為 $a_i$、$b_i$，進位為 $c_i$，則：

以下程式也處理正負整數：同號時相加；異號時比較絕對值，以較大的絕對值減去較小的絕對值，結果符號取絕對值較大的那個數。

解題方法

先動態讀取兩行字串，再分別解析正負號並略過多餘的前導零。如此不會因為數字位數超過固定緩衝區而截斷輸入。

兩數同號時，從字串尾端逐位相加並記錄進位。兩數異號時，先比較正規化後的絕對值：位數較多者較大；位數相同時，字典序較大者的數值較大。接著逐位相減並處理借位。若兩數絕對值相同，結果直接輸出 0。

C 程式碼