申論 1N為問題大小，K為大於1 的常數。請以Big-O方式比較以下時間複雜度（Timecomplexity）的大小：㈠log(N)K ㈡Klog(N) ㈢log(N)*log(log(N)K) ㈣Nlog(N)㈤log(NN) ㈥log(N)N（10 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2輸入運算式（expression）為-A-(B+C)*D^E，請畫出其對應之運算樹（expressiontree）。（10 分）
申論 3輸入中序(in-order)表示之運算式A*(B+C)，可以根據運算元優先次序關係，使用堆疊(stack)來產生其後序(post-order)表示之運算式。請依演算法追蹤其執行情形，完成如下表格。（10 分）輸入 堆疊內容 輸出A*
申論 4我們可以使用KMP（Knuth, Morris, Pratt）快速字串比對演算法找出字串裡面是否包含有某子字串。輸入字串datedadatete與子字串datdadatdatt，請完成此演算法所需之failure function F(i)如下表格。（10 分）i 0F(i) -1
申論 5外部排序（external sorting）最常使用的是2-way合併排序法（merge sorting）。假設檔案裡面包含18000 筆資料，而記憶體最多只能容許3000 筆資料。假設每次I/O block大小為1000 筆資料，則需讀多少次I/O block才能完成排序？（10 分）
申論 6已知二元樹可以用一維陣列來儲存。請依此概念設計一方法，儲存以下三元樹於如下之一維陣列中。（10 分）Aindex 0B CDdata AE F GHIJ年公務人員高等考試三級考試試題代號：類 科： 資訊處理科 目： 資料結構
申論 7將數字25,5,75,0,60,10,55,15,45,15 依序存入一維陣列如下，以heap sort 方式進行由小到大的排序。請顯示其在第一次執行完initial heap 步驟後的一維陣列內容。（10 分）index 0 1 2 3 4 5 6 7 8 9data 25 5 75 0 60 10 55 15 45 15
申論 8輸入10000 個字元，其中字元出現次數：#(A)=1400，#(B)=800，#(C)=3000，#(D)=2700，#(E)=600，#(F)=1500，#(其他字母)=0。使用霍夫曼（Huffman）編碼進行壓縮，其壓縮結果不含編碼簿（codebook）需要多少bits？（10 分）
申論 9計畫中各項工作的關係如以下的AOE（Activity On Edge）網路圖所示。㈠整個計畫至少需多少天才能完工？（10 分）㈡找出會提前或延後工期的關鍵路徑（critical path）。（10 分）V1V5E1=2天E4=16天E8=2天E3=2天E7=6天V0 V2E5=8V6天E2=4天 E9=10E6=6天天V3V4