加載中. ..
PDF
101年公務人員特種考試警察人員考試、
101年公務人員特種考試一般警察人員考試及
101年特種考試交通事業鐵路人員考試試題
代號：71340
等 別： 高員三級鐵路人員考試
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、
假設 a為一個整數陣列（array of integers），請寫一個遞迴函式（recursive
function）以求出陣列中之最大元素值。（10 分）
請寫一個遞迴函式（recursive function）依序列印出完成河內塔（Towers of Hanoi）
要求所需要的移動。（10 分）
二、請問下面各題所列的二種走訪結果是否定義唯一的二元樹？
（假設二元樹上的每一節點只包含單一字母的資訊而已。）
前序走訪： A B D G C E H F
中序走訪： D G B A H E C F
中序走訪： E G L M P Q R X
後序走訪： E L G Q P X R M
前序走訪： A B D F H C E G
後序走訪： H F D B G E C A
如果是唯一的話，請畫出具該二種走訪結果的二元樹。（20 分）
三、假設我們有以下的鍵值（key）：7、16、49、82、5、31、6、2、44。
請畫出每個值插入堆積後的最大堆積（max heap）。（10 分）
請畫出每個值插入堆積後的最小堆積（min heap）。（10 分）
四、假設有一組資料 35、51、54、60、71、83、85、97、107、117、127，
請分別列出使用二元搜尋（binary search）與費氏搜尋（Fibonacci search）該組資
料時的搜尋軌跡（可用二元樹表示之）。（7分）
若尋找 83 與117 二個數字，請分別求出上列兩種搜尋所需的搜尋次數。（7分）
請說明費氏搜尋優於二元搜尋之處。（6分）
101年公務人員特種考試警察人員考試、
101年公務人員特種考試一般警察人員考試及
101年特種考試交通事業鐵路人員考試試題
代號：71340
等 別： 高員三級鐵路人員考試
類 科： 資訊處理
科 目： 資料結構
全一張
（
背面
）
五、針對下圖之邊活動（Activity-on-Edge；AOE）網路，計算它每個活動的最早與最
晚開始時間。利用前向－後向方法（forward-backward approach）。（4分）
這個計畫的最早完成時間為何？（4分）
那些活動是臨界（critical）活動？（4分）
請畫出其臨界網路。（4分）
是否存在一個活動，當我們加速它的工作時間時會造成整個計畫時程縮短？（4分）
0
1 3 5
2 4 7
6 8 9
start finish
a3=3
a5=3
a7=4
a10=4
a12=5 a14=2
a6=3
a11=2
a13=4
a8=4
a1=5
a2=6 a9=1
a4=6