114 地方特考四等 統計類科 資料處理概要 考古題詳解

核心觀念

Dijkstra 演算法用來求解邊權重非負的有向加權圖中，起點到各節點的最短距離。每一步選出尚未確定、目前暫定距離最小的節點，將其距離確定，再用該節點更新相鄰節點的距離。

若目前確定的節點為 $u$，而 $u\to v$ 的邊權重為 $w(u,v)$，則依下式更新：

若距離變短，便把 $v$ 的前接節點（predecessor）改為 $u$。本題所有邊權重皆為正數，符合 Dijkstra 演算法的適用條件。

解題方法與逐步結果

以 $A$ 為起點，起始距離為 $d(A)=0$，其餘節點設為 $\infty$。表中每格依序表示「目前暫定距離／前接節點」；「—」表示沒有前接節點。距離已確定的節點以粗體標示。

$D$ 與 $E$ 的暫定距離同為 $5$，本解依字母順序先確定 $D$；同距離時先確定哪一個都不影響最短距離。

關鍵更新如下：

1. 確定 $A$ 後，沿 $A\to B$、$A\to C$、$A\to D$ 更新，得到 $B=2$、$C=4$、$D=5$。

核心觀念

本題考查排序的穩定性、時間複雜度，以及 QuickSort 與 MergeSort 的基本操作。

• 穩定排序：若兩筆資料的排序鍵相同，排序後仍維持它們原本的先後順序。
• QuickSort：以基準值將資料分區，再遞迴排序各分區；平均時間複雜度為 $O(n\log n)$，但最差為 $O(n^2)$。一般原地 QuickSort 不具穩定性。
• MergeSort：將資料分半、遞迴排序後合併；時間複雜度為 $O(n\log n)$，且可設計為穩定排序，但通常需要 $O(n)$ 額外空間。

（一）選擇排序演算法

應選擇穩定的 MergeSort。

原始資料已依出版年份由大到小排列；重新依作者名稱排序時，若 MergeSort 在合併時遇到作者名稱相同的兩筆資料，優先取自原序列較前面的資料，便能保留同一作者的書籍原有先後順序。因此，同一作者的書仍會依出版年份由大到小排列。

一般 QuickSort 的分區過程可能交換相同作者的資料，破壞原有順序。MergeSort 對 50 萬筆資料仍維持 $O(n\log n)$ 的時間複雜度，適合大量資料排序；代價是需要額外記憶體。

（二）QuickSort 排序

採用以子序列第一個元素為基準的分區法。以下以「每一次循環」表示每次分區完成；掃描期間，將小於基準的元素移到左側，最後將基準放到分界位置，再遞迴處理左右子序列。

初始數列：

$[39,18,61,46,11,2,24,33]$

1. 以 $39$ 為基準：左側放小於 $39$ 的數，右側放大於 $39$ 的數。

$[18,11,2,24,33]\mid39\mid[61,46]$

2. 處理左側，以 $18$ 為基準：$11,2$ 移至左側，$24,33$ 留在右側。

$[11,2]\mid18\mid[24,33]$

3. 處理 $[11,2]$，以 $11$ 為基準：

$[2]\mid11\mid[]$

4. 處理 $[24,33]$，以 $24$ 為基準：

$[]\mid24\mid[33]$

5. 處理右側 $[61,46]$，以 $61$ 為基準：

核心觀念

本題考查 SQL 的條件篩選、子查詢，以及以 JOIN 實作自我關連。

• WHERE 用來篩選資料列。
• IN 用來判斷某欄位的值是否屬於一組查詢結果。
• 自我關連是同一資料表以不同別名各自扮演不同角色，再用 JOIN 連結。

本題沒有涉及法條。

解題方法

（一）找出張曼娟於 2020 年出版的書名與出版社

作者與出版年份都是篩選條件，書名與出版社則是指定的輸出欄位：

SELECT Title, Publisher
FROM Books
WHERE Author = '張曼娟'
 AND PubYear = 2020;

AND 表示兩個條件必須同時成立，亦即作者是張曼娟，且出版年份為 2020。

（二）說明子查詢的過濾條件與輸出欄位

外層查詢：

SELECT Title, Author, Publisher
FROM Books
WHERE PubYear IN (...)

輸出符合外層 WHERE 條件之資料列的 Title、Author、Publisher 三個欄位。外層條件是：該書的 PubYear 必須出現在子查詢所傳回的年份集合中。

子查詢：

SELECT PubYear
FROM Books
WHERE Author = '村上春樹'
 AND Publisher = '時報出版公司'

子查詢會找出作者為「村上春樹」且出版社為「時報出版公司」的資料列，並傳回這些資料列的 PubYear。

因此，整體查詢的結果是：所有出版年份與上述村上春樹作品年份相同的書籍，並列出其書名、作者及出版社。外層沒有再限制作者或出版社，所以符合年份的其他作者作品也會列出。