三、請設計一個遞迴程式（recursive procedure）。當輸入（input）為一顆有順序性且有固 定根的二元樹（ordered rooted binary tree）T 時，此遞迴程式可依中序追蹤（inorder traversal）方式拜訪 T 的每一個節點（node）恰好一次。（20 分）

一、將四個字母 A、B、C、D 依序放入（push）一個堆疊（stack）內。在放入之過程， 堆疊內之字母可隨機取出（pop）。若此四個字母最終皆被取出，則以下何者可為 此四個字母被取出的順序（例如，D、C、B、A 代表 D 首先被取出，其次為 C，再 其次為 B，A 最後被取出）？（可複選）（20 分) (1) A、B、C、D (2) C、B、D、A (3) B、D、A、C (4)D、C、A、B (5) C、B、A、D

二、如何將以下 15 個英文單字存入陣列（array）A[1]，A[2]，…，A[15]，使得以後搜尋 （search）其中任何一個字，至多只需執行三次字比較（word comparisons）？又搜 尋方法為何？請詳述。（20 分） read，educate，place，touch，fill，calculate，save，increase， gain，print，begin，work，take，derive，operate

四、當輸入（input）為x1, x2, …, xn時，塞入排序（insertion sort）可將此n個輸入值從小 到大排列。塞入排序的執行（execution）可簡略表示如下： For i＝2, 3, …,n, insert xi into x1, x2, …, xi−1 such that these i data items are sorted. 例如，當輸入為 7, 5, 1, 4, 3, 2, 6 時，塞入排序的執行如下： i = 2: 5, 7 i = 3: 1, 5, 7 i = 4: 1, 4, 5, 7 i = 5: 1, 3, 4, 5, 7 i = 6: 1, 2, 3, 4, 5, 7 i = 7: 1, 2, 3, 4, 5, 6, 7 若 T(n) 表示執行塞入排序所需的時間複雜度（time complexity），其中 n 表示輸入 值的個數。請用 O( f(n)) 的符號估算 T(n) 在最佳情況（best case）與最壞情況（worst case）之值，其中 f(n) 表示 n 的一個函數。（20 分）

五、假設 L 是一指標（pointer），指向一個雙鏈結串列（doubly linked list），圖示如下。  請設計一個程式（procedure）：當輸入（input）為 x, y 與 L 時（x 為存在於 L 所 指的串列內之資料，y 為不存在於 L 所指的串列內之資料），此程式可在 L 所指的串 列內增加（insert）y 於 x 之後。增加 y 之後，串列仍必須為雙鏈結結構。（20 分)

(五)若 n = 10，且每一組球生產後放上裝箱輸送帶的     球的大小順序非固定順序     。假設輸送帶上原本配置 n 個機器人，若改成配置 2n 個機器人， 整組球順序排好的速度可以加快多少？請說明。

(四)若每一組球生產後放上裝箱輸送帶的     球的大小順序非固定順序     ，請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小？

(三)若 n = 6，且輸送帶上配有 4 個機器人，請給一組放上裝箱輸送帶的球的大小順序，使得其經過這 4 個機器人後，整組球的順序仍未能排好。

(二)若 n = 20，且生產後放上裝箱輸送帶的球的大小為 11, 12, 20, 16, 3, 1, 7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置幾個機器人才能將球的順序由大排到小？

 (一)若 n = 6，且生產後放上裝箱輸送帶的球的大小為 3, 2, 5, 6, 1, 4。請說明若輸送帶配有 4 個機器人是否足夠將球的順序完全由大排到小？

(四)以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，請列舉可依序插入的五個數值，使得該二元樹成為完整二元樹（full binary tree） 。

114年 - 114 地方政府公務特種考試_三等_資訊處理：資料結構#134706

114年 - 114 公務升官等考試_薦任_資訊處理：資料結構#133251

114年 - 114 高等考試_三級_資訊處理：資料結構#128753

114年 - 114 關務特種考試_三等_資訊處理（選試英文）：資料結構#126563

114年 - 114 身心障礙特種考試_三等_資訊處理：資料結構#126562

113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理：資料結構#124511

113年 - 113 高等考試_三級_資訊處理：資料結構#121217

113年 - 113 關務特種考試_三等_資訊處理（選試英文）：資料結構#119489

112年 - 112 地方政府特種考試_三等_資訊處理：資料結構#118368

112年 - 112 公務升官等考試_薦任_資訊處理：資料結構#117327