阿摩線上測驗 登入

102年 - 102年薦任資料結構#43809

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

試卷資訊

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

選擇題 (0)

申論題 (11)

⑴資料結構（data structure）
⑵資料型態（data type）
⑶陣列（array）
⑷堆積樹（heap tree）
⑴ void push（STACK_TYPE *stack, ITEM_TYPE new_item）; /*將 new_item 加 到堆疊頂端 */
⑵ void pop（STACK_TYPE *stack, ITEM_TYPE *old_item）; /*將堆疊頂端資料 移出，並放在 old_item */ 
 一開始，設定 stack -> top = -1；表示堆疊是空的。（註：符號 stack -> top 指到 堆疊頂端， stack -> item [stack -> top] 是堆疊頂端的資料）
三、⑴給予如下資料: 12, 8, 17, 4, 26, 6, 11, 請將這些資料建成一個二元搜尋樹（Binary Search Tree）；如何利用此 binary search tree 來做資料之排序。（10 分）
⑵有一個二元搜尋樹，其結構不清楚，節點的值為 1 到 10000，當搜尋“2013”的值 時，拜訪的節點值依序為：1396, 7248, k, 1523, 1865, 3152, 2013，請問 k 值的範 圍為何？（10 分）
四、假設一生物 DNA 序列由 a, e, i, s, t, b, 和 n 基本單元所構成。已知某一微生物 DNA 序列之每一基本單元在此序列中出現之頻率如下：a, 10 次; e, 15 次; i, 12 次; s, 3 次; t, 4 次; b, 13 次; n, 1 次。請設計一最佳編碼表編碼此序列，並計算出最小之編碼位 元數。（20 分）
⑴利用 Kruskal’s algorithm 來找最小擴張樹（Minimal spanning tree）。
⑵在演算法中有一動作：選擇一最低成本的邊（edge），加入此邊（edge），如不 形成一迴圈（cycle），則加入此邊至最小擴張樹，請問運用何運算（operations） 或原理可完成此動作？