N 為問題大小、K 為大於1 的常數。請以Big-O 方式比較以下時間複雜度
(Time complexity)的大小:
輸入運算式(expression)為−A − (B+ C) ∗D∧ E ,請畫出其對應之運算樹
(expression tree)。
輸入中序(in-order)表示之運算式A∗(B+ C),可以根據運算元優先次序關
係,使用堆疊(stack)來產生其後序(post-order)表示之運算式。請依演算法
追蹤其執行情形,完成如下表格。
我們可以使用KMP (Knuth, Morris, Pratt)快速字串比對演算法找出字串裡
面是否包含有某子字串。輸入字串datedadatete 與子字串datdadatdatt,請
完成此演算法所需之failure function F(i)如下表格。
外部排序(external sorting) 最常使用的是2-way 合併排序法(merge
sorting)。假設檔案裡面包含18000 筆資料,而記憶體最多只能容許3000
筆資料。假設每次I/O block 大小為1000 筆資料,則需讀多少次I/O block
才能完成排序?
已知二元樹可以用一維陣列來儲存。請依此概念設計一方法,儲存以下
三元樹於如下之一維陣列中。
將數字25, 5, 75, 0, 60, 10, 55, 15, 45, 15 依序存入一維陣列如下,以heap
sort 方式進行由小到大的排序。請顯示其在第一次執行完initial heap 步驟
後的一維陣列內容。
輸入 10000 個字元,其中字元出現次數:#(A) =1400,#(B) = 800,
#(C) = 3000,#(D) = 2700,#(E) = 600,#(F) =1500,#(其他字母) = 0。
使用霍夫曼(Huffman)編碼進行壓縮,其壓縮結果不含編碼簿(codebook)
需要多少bits?
計畫中各項工作的關係如以下的AOE (Activity On Edge)網路圖所示。
(1) 整個計畫至少需多少天才能完工?
(2) 找出會提前或延後工期的關鍵路徑(critical path)。
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)