所屬科目：公職◆資料結構
一、請以 C, C++, C#, Java 或 Python 撰寫 2 個方法，一個以迴圈方式，一個以遞迴方式，對存在 singular linked list 的資料進行 linearly search。假設 Node 的結構如下：（12 分）
二、請為數列 0, 10, 30, 20, 50, 80, 40, 90, 70, 60 建立 AVL tree, Min/Max heap, 2− 4 tree，並依它們的性質以 yes or no 完成下表。註：所建立的 tree or heap 請以圖示，如果是 Searching Tree，請以左小右大的方式建立。 （24 分）
三、請以如下的 Huffman Tree 所做的數字編碼，解讀 01010111110100100011 編碼對應的數字。（10 分）
四、針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的 cost），依 如下 BFS（配合 queue）與 DFS（配合 stack）演算法，進行所有節點的走訪，多個節點可以走訪時，以連線上 cost 較低者優先，結果請以迴圈 內部的顯示要求，依下表形式填入（stack 垂直表示，開口在上方，queue 水平表示，出口在左，入口在右） 。註：假設節點 S 為起始點。（24 分）
五、請完成下列表格有關排序演算法的 time complexity（假設排序資料有 n 個，資料位數有 d 個）、是否為 In− Space 演算法、是否為 Stable 演算法及範例數列 50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分）
阿摩線上測驗
登入
