加載中. ..
PDF
100年公務人員特種考試司法人員考試試題 代號：
等 別： 三等考試
類 科： 檢察事務官電子資訊組
科 目： 資料結構
考試時間： 2 小時 座號：
※注意： 禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
30760
一、
請將中序運算式(8×3-6/2)+5/(1+4)轉換成後序運算式（postfix expression）。（10 分）
請使用堆疊（stack）說明算出後序運算式 1,2,3,*,4,6,+,5,/,/,+的過程與結果。（10 分）
二、有一陣列 A＝（163, 231, 356, 93, 869, 987, 58, 349, 271, 33）要由小排到大。
使用基數排序法 （radix sort）需要三個回合（pass）排序 A陣列，請寫出前兩個
回合結束時 A陣列的內容。（10 分）
使用堆積排序法 （heap sort）需要先將 A陣列整理成 maxheap，然後再經過九個
回合（pass）的 reheap 才能將資料由小排到大，請寫出整理成 maxheap 後與第一
個回合 reheap 結束時 A陣列的內容。（10 分）
使用快速排序法 （quick sort）將 A陣列排序，每一回合（pass）選擇待排序子
陣列（sub-array）最左邊那筆資料做為比較基準，且左邊子陣列會比右半子陣列
先處理，請寫出前兩個回合結束時 A陣列的內容。（10 分）
三、
有一N個節點（node）的二元樹（binary tree），令N0代表沒有子節點的樹葉（leaf
node）個數，N1代表只有一個子節點的節點個數，N2代表有兩個子節點的節點個
數，請證明 N
0 = N2 + 1。（10 分）
請填入下面 C程式中三個空格以完成 ptr 指向樹根的二元樹中序追蹤（inorder
traversal）程式並將追蹤結果顯示在螢幕上。（15 分）
struct node {
struct node *left;
int data;
struct node *right;};
void inorder(struct node *ptr)
{ if( ptr != NULL ) {
_____(1)_____;
_____(2)_____;
_____(3)_____;
}
}
四、
請寫出在無向圖中找出 Minimum Cost Spanning Tree 的Kruskal 演算法。（15 分）
請說明 heap （除了 heap sort 外）與 disjoint set 這兩種資料結構在這個演算法中
有何作用？（10 分）