加載中. ..
PDF
100年公務人員高等考試三級考試試題 代號：35850
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、N為問題大小，K為大於 1的常數。請以Big-O方式比較以下時間複雜度（Time
complexity）的大小：
log(N)K
Klog(N)
log(N)*log(log(N)K)
Nlog(N)
log(NN)
log(N)N（10 分）
二、輸入運算式（expression）為-A-(B+C)*D^E，請畫出其對應之運算樹（expression
tree）。（10 分）
三、輸入中序(in-order)表示之運算式 A*(B+C)，可以根據運算元優先次序關係，使用堆
疊(stack)來產生其後序(post-order)表示之運算式。請依演算法追蹤其執行情形，完
成如下表格。（10 分）
輸入 堆疊內容 輸出
A
*
四、我們可以使用KMP（Knuth, Morris, Pratt）快速字串比對演算法找出字串裡面是否包
含有某子字串。輸入字串datedadatete與子字串datdadatdatt，請完成此演算法所需之
failure function F(i)如下表格。（10 分）
i 0
F(i) -1
五、外部排序（external sorting）最常使用的是 2-way合併排序法（merge sorting）。
假設檔案裡面包含 18000 筆資料，而記憶體最多只能容許 3000 筆資料。假設每次
I/O block大小為 1000 筆資料，則需讀多少次I/O block才能完成排序？（10 分）
六、已知二元樹可以用一維陣列來儲存。請依此概念設計一方法，儲存以下三元樹於如
下之一維陣列中。（10 分）
A
D
C
B
E F
G
HI
J
index 0
data A
100年公務人員高等考試三級考試試題 代號：35850
類 科： 資訊處理
科 目： 資料結構
全一張
（
背面
）
七、將數字 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 9
data 25575060105515 45 15
八、輸入 10000 個字元，其中字元出現次數：#(A)=1400，#(B)=800，#(C)=3000，
#(D)=2700，#(E)=600，#(F)=1500，#(其他字母)=0。使用霍夫曼（Huffman）編碼
進行壓縮，其壓縮結果不含編碼簿（codebook）需要多少 bits？（10 分）
V5
V1
V6
V4
V2
V0
V3
E1=2天 E3=2天
E2=4天
E4=16天
E6=6天
E5=8天E7=6天
E8=2天
E9=10天
九、計畫中各項工作的關係如以下的 AOE（Activity On Edge）網路圖所示。
整個計畫至少需多少天才能完工？（10 分）
找出會提前或延後工期的關鍵路徑（critical path）。（10 分）