調查局三等申論題
114年
[電子科學組] 計算機概論
第 一 題
📖 題組：
請回答下列有關資料結構及時間複雜度計算的問題： 01 n=int(input()) 02 k=0 03 counter=0 04 for i in range(1, n//2): 05 k=k+1 06 for j in range(1, n, pow(2,k)): 07 counter=counter+1 08 print(counter) PROGRAM-1
請回答下列有關資料結構及時間複雜度計算的問題： 01 n=int(input()) 02 k=0 03 counter=0 04 for i in range(1, n//2): 05 k=k+1 06 for j in range(1, n, pow(2,k)): 07 counter=counter+1 08 print(counter) PROGRAM-1
📝 此題為申論題，共 2 小題
小題 (一)
請說明堆疊資料結構的定義與特性；並請說明應用堆疊資料結構完成以下程式的方法，程式功能為：將一個十進制的正整數轉換為二進制。（15 分）
思路引導 VIP
看到此題，應立即聯想堆疊的「後進先出 (LIFO)」特性。接著，連結十進制轉二進制的數學原理「除二取餘法」，指出先算出的餘數為低位元需最後輸出，正好完美契合堆疊的存取邏輯，最後輔以具體數值步驟進行實例演示。
小題 (二)
執行以下 Python 程式 PROGRAM-1，輸入一個正整數 n，則程式的第 07 行（counter = counter + 1）總共會執行多少次？試寫出其時間複雜度（Time Complexity），以及其詳細的推導過程，並使用 Big-O 符號表示之。（10 分）
思路引導 VIP
面對雙層迴圈的時間複雜度計算，先分別列出外層與內層的執行範圍與變數變化。本題的關鍵在於內圈的步進值呈現等比級數遞增（2^k），因此需利用級數求和公式（Sigma）列出總次數，並結合天花板函數（Ceiling）的數學不等式來推導出精確的上限（Big-O）。
資料結構與複雜度分析
💡 掌握堆疊 LIFO 特性應用於進位轉換，並能精確推導非線性迴圈複雜度。
🔗 十進位轉二進位之堆疊處理流程
- 1 連續相除 — 將十進位數連續除以 2 直到商數為 0。
- 2 餘數入棧 — 將每次運算產生的餘數依序 Push 存入堆疊中。
- 3 逆序彈出 — 將堆疊內容依 Pop 順序取出，即得正確二進位結果。
↓
↓
🔄 延伸學習：延伸學習：此邏輯亦可用於處理括號匹配或遞迴呼叫的狀態保存。
