地特四等申論題
107年
[資訊處理] 程式設計概要
第 一 題
📖 題組：
請用下列程式回答下列問題。(每小題5分,共25分) int num [100]={0}; int n=0; void reorder (int k) { int temp; if ( (k != 0) && (books[k] > books[k/2])) { // 假設 books 應為 num temp = books [k]; books[k] = books[k/2]; books [k/2]=temp; reorder (k/2); } } int main () { int i=0; scanf ("%d", &num[i]); while (i != 0) { reorder (i); i = i + 1; scanf (“%d”, &num[i]); } }
請用下列程式回答下列問題。(每小題5分,共25分) int num [100]={0}; int n=0; void reorder (int k) { int temp; if ( (k != 0) && (books[k] > books[k/2])) { // 假設 books 應為 num temp = books [k]; books[k] = books[k/2]; books [k/2]=temp; reorder (k/2); } } int main () { int i=0; scanf ("%d", &num[i]); while (i != 0) { reorder (i); i = i + 1; scanf (“%d”, &num[i]); } }
📝 此題為申論題，共 5 小題
小題 (一)
num[]一維陣列最多可儲存幾個正整數?
思路引導 VIP
觀察程式碼最上方的全域變數宣告 int num [100]={0};。在中括號內的數字代表陣列的元素個數，也就是最大容量。
小題 (二)
若依序輸入1, 2, 3, ..., 99,0,請說明 num[0]值為何。
思路引導 VIP
面對程式追蹤題，務必嚴格遵循「由上而下、逐步變數代入」的原則，切忌一看到遞迴或特定演算法特徵（如 Heapify）就盲目推導結果。本題的關鍵陷阱（或出題瑕疵）在於 main 函式中 while 迴圈的初始進入條件判斷。
小題 (三)
若依序輸入99,98, ..., 2, 1,0,請說明 num[0]值為何。
思路引導 VIP
解答程式追蹤題時，切忌預設立場（例如直接預設它是一個建構 Heap 的過程就開始畫樹），務必嚴格依循變數的初始值與迴圈的進入條件進行逐行手動追蹤。本題的破題關鍵在於 main 函式中 i 的初始值與 while(i != 0) 條件式的交互作用。
小題 (四)
輸入99個亂數產生的正整數後再輸入0,請說明 num[0]值為何。
思路引導 VIP
看到此題，應先辨識出 reorder 函式是經典的「最大堆積樹（Max Heap）」向上浮動（Up-heap / Sift-up）操作。接著分析陣列索引的父子關係 k 與 k/2，即可推導出不斷向上交換的結果，必定會讓全域最大值浮動至陣列最頂端的 num[0]。
小題 (五)
請說明 reorder()遞迴函數的功用為何。
思路引導 VIP
看到陣列索引 k 與 k/2 的比較與交換，應立刻聯想到「二元樹的陣列表示法」中子節點與父節點的關係。接著觀察條件判斷為「子節點大於父節點」時進行交換並向上遞迴，即可確認這是資料結構中維護「最大積堆（Max Heap）」特性的標準操作。