高考申論題
114年
[資訊處理] 資料結構
第 五 題
五、下列虛擬碼是利用某演算法對陣列 A 的元素進行處理，請說明該法是進行何種處理並請寫出其名稱和在最壞情況下時間複雜度為何？（10 分）
若陣列 A = [29, 10, 14, 37, 13]，請寫出該虛擬碼的處理過程：請列出陣列在每一輪（每次外層迴圈執行完後）的內容變化情形。請特別標示出最終結果為何？（10 分）
doingSomething(A)
begin
n ←陣列 A 的元素個數
for i ← 0 to n − 2 do
theIndex ← i
for j ← i + 1 to n − 1 do
if A[j] < A[theIndex] then
theIndex ← j
end for
if theIndex <> i then
temp = A[i]
A[i] = A[theIndex]
A[theIndex] = temp
end if
end for
end
若陣列 A = [29, 10, 14, 37, 13]，請寫出該虛擬碼的處理過程：請列出陣列在每一輪（每次外層迴圈執行完後）的內容變化情形。請特別標示出最終結果為何？（10 分）
doingSomething(A)
begin
n ←陣列 A 的元素個數
for i ← 0 to n − 2 do
theIndex ← i
for j ← i + 1 to n − 1 do
if A[j] < A[theIndex] then
theIndex ← j
end for
if theIndex <> i then
temp = A[i]
A[i] = A[theIndex]
A[theIndex] = temp
end if
end for
end
📝 此題為申論題
思路引導 VIP
看到此虛擬碼，先觀察雙層迴圈的結構與內部邏輯。外層迴圈控制排序位置，內層迴圈則在未排序的剩餘元素中尋找『最小值』的索引（theIndex），最後進行位置交換，由此可一眼判定為『選擇排序法（Selection Sort）』。接著依循迴圈變數逐步追蹤陣列元素的變化即可得解。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】辨識虛擬碼為選擇排序法（Selection Sort），核心邏輯為每次從未排序區段中找出最小值，並與該區段的起始元素進行交換。 【解答】 一、 演算法說明、名稱與時間複雜度
▼ 還有更多解析內容
選擇排序法解析
💡 選擇排序透過每輪選取未排序區間的最小值與起始位置交換。
🔗 選擇排序法單輪運作邏輯
- 1 設定基準 — 將外層迴圈索引 i 設為初始最小值索引 theIndex。
- 2 掃描尋找 — 內層迴圈從 i+1 掃描至末尾，更新最小值索引。
- 3 判斷交換 — 若 theIndex 不等於 i，則將兩位置元素對調。
- 4 鎖定位置 — 第 i 個位置已達最終排序狀態，移動至下一輪。
↓
↓
↓
🔄 延伸學習：延伸學習：選擇排序在資料移動次數（Swap）上優於氣泡排序。
