高考申論題
114年
[資訊處理] 資料結構
第 二 題
📖 題組：
一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出一組 n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後，球的順序就完全由大排到小了。（每小題 5 分，共 25 分）
一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出一組 n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後，球的順序就完全由大排到小了。（每小題 5 分，共 25 分）
📝 此題為申論題，共 5 小題
小題 (二)
若 n = 20，且生產後放上裝箱輸送帶的球的大小為 11, 12, 20, 16, 3, 1, 7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置幾個機器人才能將球的順序由大排到小？
思路引導 VIP
考生看到這題應立刻聯想到「氣泡排序（Bubble Sort）」的演算法特性。機器人比較相鄰兩球並交換的動作，等同於氣泡排序中的一次掃描（Pass）。在降序排序中，每次掃描能讓較大的數字最多「向左前進 1 格」，因此最少需要的機器人數量，就等於所有數字中「初始位置與其目標位置向左差距的最大值」。
小題 (一)
若 n = 6，且生產後放上裝箱輸送帶的球的大小為 3, 2, 5, 6, 1, 4。請說明若輸送帶配有 4 個機器人是否足夠將球的順序完全由大排到小？
思路引導 VIP
看到此題應立刻聯想到「氣泡排序法（Bubble Sort）」的應用，每個機器人代表一次從頭到尾的陣列掃描（Pass）。解題時可透過逐步追蹤（Trace）每次掃描後的陣列變化，或利用氣泡排序中元素逆向移動的最大距離（烏龜現象）來精確計算所需的最少機器人數量。
小題 (三)
若 n = 6，且輸送帶上配有 4 個機器人，請給一組放上裝箱輸送帶的球的大小順序，使得其經過這 4 個機器人後，整組球的順序仍未能排好。
思路引導 VIP
本題核心在於辨識「機器人排序相鄰兩球」的行為等同於氣泡排序（Bubble Sort）的一次掃描（Pass）。要讓序列經過 4 次掃描仍未排好，需利用氣泡排序中「大元素每次只能往前移動一格」的特性（即烏龜元素），設計出由小到大遞增的極端逆向序列。
小題 (四)
若每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序，請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小？
思路引導 VIP
本題的核心在於將工廠自動化排序的情境，映射到資料結構中的「氣泡排序（Bubble Sort）」演算法。考生需思考「相鄰交換」的特性，並評估在最差情況下（數列完全反序），需要多少回合（Passes）或多少次比較交換（Comparisons）才能保證排序完成。
小題 (五)
若 n = 10，且每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序。假設輸送帶上原本配置 n 個機器人，若改成配置 2n 個機器人，整組球順序排好的速度可以加快多少？請說明。
思路引導 VIP
將機器人對連續經過的球進行相鄰交換的動作，映射為演算法中的「氣泡排序法（Bubble Sort）」的單一回合（Pass）。接著分析 n 個元素在氣泡排序中最差情況所需的最大回合數，即可判斷增加機器人是否能提升效率。