普考申論題
114年
[統計] 資料處理概要
第 一 題
📖 題組：
L1為一由小而大排序之資料串列，L2為一由大而小排序之資料串列，其分別含有 N1與 N2筆資料，且 N1, N2≫0：（每小題 10 分，共 40 分）
L1為一由小而大排序之資料串列，L2為一由大而小排序之資料串列，其分別含有 N1與 N2筆資料，且 N1, N2≫0：（每小題 10 分，共 40 分）
📝 此題為申論題，共 3 小題
小題 (一)
請設計出一最佳演算法，以能最快速查詢一資料 D 是否存在於資料串列 L1或 L2內。
思路引導 VIP
看到題目強調資料『已排序』且要求『最快速查詢』，應立即聯想到時間複雜度為 O(log N) 的『二分搜尋法 (Binary Search)』。答題關鍵在於分別針對遞增 (L1) 與遞減 (L2) 串列，寫出邏輯方向相反的搜尋步驟。
小題 (二)
並求出該演算法之時間複雜度（請越精確估算越佳）。
思路引導 VIP
遇到已排序串列合併的題目，應直覺聯想到歸併排序（Merge Sort）中的合併（Merge）程序。特別注意本題 L1 為遞增、L2 為遞減，因此需運用雙指標技巧，將 L2 從尾端往回讀取，即可在最少比較次數下，以 O(N1+N2) 的線性時間內高效完成合併並精確分析複雜度。
小題 (三)
與上面問題同一個數列，利用 MergeSort 進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）
思路引導 VIP
看到合併排序法（Merge Sort），首先聯想「分而治之（Divide and Conquer）」的核心策略。解題時應先將數列不斷對半「分割」至剩單一元素，接著詳細寫出由小到大逐層「合併」的每一循環結果。若遇跨題組但未提供原數列之情形，應自行假設一組標準數列作為示範，並清楚說明推演邏輯。