100年 - 100年警察鐵路高員三級資料結構#45957

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

試卷資訊

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

選擇題 (0)

申論題 (13)

⑴請畫出該圖。
⑵請列出該圖長度為 2 之路徑矩陣（path matrix of length 2）。
⑶何謂遞移封閉矩陣（transitive closure matrix）？請以該圖為例說明如何求其遞移 封閉矩陣。
⑷何謂反射遞移封閉矩陣（reflexive transitive closure matrix）？請列出該圖之反射 遞移封閉矩陣。
⑴列出霍夫曼樹（the Huffman tree：產生該樹時請以字母順序較前者列於左子樹為 原則）。
⑵列出各字母之編碼。
⑶寫出該字串之編碼。
三、從一個空的 AVL 樹（AVL tree）開始依序執行以下的插入：MAR、MAY、NOV、 AUG、APR、JAN、DEC、JULY、FEB。在每次插入後繪出 AVL 樹，並註明每一 次插入時所使用的旋轉類型（如果有的話）。（20 分）
⑴由左到右一次抽樣一個字元不限定階數。
⑵由右到左一次抽樣一個字元限定階數為 3。
⑶利用單一字元抽樣法找出一個階數最少的查找樹。
⑴計算階層函數 n!的值：在 n＝0 或 1 時的值是 1；在 n > 1 時，它的值為 n*(n-1)! 。
⑵使用二元搜尋（binary search），在排序好的整數陣列 list[0] ≦ list[1] ≦ … ≦ list[n-1]中找出一個要找的整數（searchnum），若有找到則傳回它的位置，不然 就傳回 -1。