阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 100年 - 100年高考三級資料結構#45827
100年 - 100年高考三級資料結構#45827
科目：
公職◆資料結構 |
年份：
100年 |
選擇題數：
0 |
申論題數：
15
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (15)
⑴ log(N)
K
⑵ K
log(N)
⑶ log(N)*log(log(N)
K
)
⑷ N
log(N)
⑸log(N
N
)
⑹log(N)
N
（10 分）
二、輸入運算式（expression）為-A-(B+C)*D^E，請畫出其對應之運算樹（expression tree）。（10 分）
三、輸入中序(in-order)表示之運算式 A*(B+C)，可以根據運算元優先次序關係，使用堆 疊(stack)來產生其後序(post-order)表示之運算式。請依演算法追蹤其執行情形，完 成如下表格。（10 分）
【已刪除】四、我們可以使用KMP（Knuth, Morris, Pratt）快速字串比對演算法找出字串裡面是否包 含有某子字串。輸入字串datedadatete與子字串datdadatdatt，請完成此演算法所需之 failure function F(i)如下表格。（10 分）
五、外部排序（external sorting）最常使用的是 2-way合併排序法（merge sorting）。 假設檔案裡面包含 18000 筆資料，而記憶體最多只能容許 3000 筆資料。假設每次 I/O block大小為 1000 筆資料，則需讀多少次I/O block才能完成排序？（10 分）
【已刪除】六、已知二元樹可以用一維陣列來儲存。請依此概念設計一方法，儲存以下三元樹於如 下之一維陣列中。（10 分）
七、將數字 25,5,75,0,60,10,55,15,45,15 依序存入一維陣列如下，以 heap sort 方式進行由小 到大的排序。請顯示其在第一次執行完 initial heap 步驟後的一維陣列內容。（10 分）
八、輸 入 10000 個 字 元 ， 其 中 字 元 出 現 次 數 ： #(A)=1400 ， #(B)=800 ， #(C)=3000 ， #(D)=2700，#(E)=600，#(F)=1500，#(其他字母)=0。使用霍夫曼（Huffman）編碼 進行壓縮，其壓縮結果不含編碼簿（codebook）需要多少 bits？（10 分）
⑴整個計畫至少需多少天才能完工？（10 分）
⑵找出會提前或延後工期的關鍵路徑（critical path）。（10 分）
阿摩線上測驗
登入
阿摩線上測驗
登入
