高考申論題
109年
[資訊處理] 資料結構
第 二 題
📖 題組：
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
我們使用一個未排序的陣列（Unsorted Array）來管理鍵值以實現一個優先佇列，請回答下列問題：（10分）
⑴若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者（Delete_Min））的時間複雜度。
⑵請判斷下面的敘述是否為真，並請說明原因：
若以此優先佇列進行排序（Sorting），其所對應的排序原理為插入排序（Insertion Sort）。
⑴若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者（Delete_Min））的時間複雜度。
⑵請判斷下面的敘述是否為真，並請說明原因：
若以此優先佇列進行排序（Sorting），其所對應的排序原理為插入排序（Insertion Sort）。
📝 此題為申論題
思路引導 VIP
針對第⑴題：若底層結構是「未排序陣列」，Insert 時直接放在陣列尾端最快；但 Delete_Min 因為沒排序，就得找遍全陣列。 針對第⑵題：從無序池中反覆挑選最小值的行為，符合哪一種經典排序法？是選擇排序（Selection Sort）還是插入排序（Insertion Sort）？釐清兩者的原理差異即可判斷。