阿摩線上測驗 登入

100年 - 100年司法官考三等資料結構#45540

科目：公職◆資料結構 | 年份：100年 | 選擇題數：0 | 申論題數：9

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (9)

⑴請將中序運算式(8× 3-6/2)+5/(1+4)轉換成後序運算式（postfix expression）。（10 分）
⑵請使用堆疊（stack）說明算出後序運算式 1,2,3,*,4,6,+,5,/,/,+的過程與結果。（10 分）
⑴使用基數排序法 （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代表有兩個子節點的節點個 數，請證明 N0 = 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 分）