9 有一棵二元樹（binary tree）的後序走訪（postorder traversal）結果為 DEBFGCA，中序走訪（inorder traversal）為 DBEAFCG，請問此樹的前序走訪（preorder traversal）結果為何？
(A) ABDECFG
(B) ABCDFEG
(C) ADBECFG
(D) ABDCEGF

5 關於算式樹（Expression Tree）的說明，下列何者錯誤？ (A)算式樹可以用二元樹表示 (B)算式樹的葉（Leaf）節點都是運算元（Operand） (C)算式樹的非葉（Non-Leaf）節點都是運算子（Operator） (D)算式樹在進行廣度優先追蹤（Breadth First Traversal）之後，可得中序表示式（Infix Expression）

6 最小成本擴張樹（Minimal spanning tree）演算法中，可以任意挑選起始節點的是： (A) Dijkstra 演算法 (B) Prim 演算法 (C) Bellman-ford 演算法 (D) Kruskal 演算法

7 以比較和交換為主的排序演算法的時間複雜度的下限（worst-case）是： (A)Ω(n log n) (B)Ω(n2) (C)Ω(n2 log n) (D)Ω(log n)

8 自 n 筆資料中依據指定之鍵值（Key value）尋找資料稱為資料搜尋（Search）或簡稱搜尋。下列為資 料搜尋方法相關敘述： ①循序搜尋（Sequential search）法是所有搜尋方法中，空間複雜度（Space complexity）與時間複雜 度（Time complexity）皆最差之搜尋方法。 ②使用循序搜尋（Sequential search）法、費氏搜尋（Fibonacci search）法、內插搜尋（Interpolation search）法、索引搜尋（Index search）法等方法進行資料搜尋（Searching）時，必須先將資料依據 鍵值（Key value）完成排序（Sort）。 ③使用內插搜尋（Interpolation search）法時，必須先將資料依據鍵值（Key value）完成排序（Sort）， 故資料搜尋實際之時間複雜度（Time complexity）應包含排序所需之時間而表示為O(n2)+O(log2 n) 或O(n. log2 n)+O(log2 n)。 ④使用搜尋樹（Search tree）法進行資料搜尋（Searching）時，必須使用額外之記憶體儲存空間建立 樹（Tree）形結構，故實際之空間複雜度（Space complexity）表示為O(n)+O(log2 n)。 ⑤若某資料搜尋方法之時間複雜度（Time complexity）為O(n. log2 n)，則進行資料搜尋時不應選用此 資料搜尋方法。 請由下列選項中選出最適合者。 (A)③正確；②⑤錯誤 (B)⑤正確；②④錯誤 (C)①正確；③④錯誤 (D)②④⑤錯誤

10 若 G 為一非“多重圖形＂（Multigraph）、無“自身邊線＂（Self edge）之無向圖形（Undirected graph）結 構，並以 V(G)表示 G 之頂點（Vertex）所成之集合（Set），E(G)表示 G 之邊線（Edge）所成之集合（Set）。 下列為有關 G 之敘述： ①使用廣度優先走訪（BFS）可找出 G 之所有連結單元（Connected component）。 ②若 G 不為完整圖形（Complete graph），則 G 之頂點中必存在一關節點（Articulation point）。 ③若H1與H2為G之 2 個連結單元（Connected components），則V(H1)∩V(H2)=φ。 ④若連結 G 之頂點 u 與 v 之邊線（Edge）為 G 之一橋邊（Bridge），則頂點 u 與 v 均為 G 之關節點 （Articulation point）。 ⑤若T1與T2為基於G之生成樹（Spanning tree），則V(T1)∩V(T2)=V(G)且E(T1)∪E(T2)=E(G)。 請選出最適合之選項。 (A)①③正確；②⑤錯誤 (B)③④正確；①⑤錯誤 (C)③⑤正確；②④錯誤 (D)④⑤正確；②③錯誤 

11 假設系統使用最久沒被使用（least-recently-used, LRU）分頁置換演算法（page replacement algorithm）， 且有 3 個分頁框（frame）分配給程序（process）A 使用。若剛開始 3 個分頁框皆為空的，請問程序 A 作一連串分頁存取：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 會使 page 2 被置換出（swap out） 分頁框幾次？ (A)0 (B)1 (C)2 (D)3

12 下圖是利用多工器（Multiplexer）實作布林函數 F 的組合電路圖。下列何者是 F 的布林函式？ (A) F(x, y, z) = Σ(0, 3, 6, 7) 4×1 MUX (B) F(x, y, z) = Σ(1, 2, 4, 5) y S0 (C) F(x, y, z) = Σ(1, 2, 4, 7) x S1 (D) F(x, y, z) = Σ(0, 3, 4, 6) 

13 假設一類似於 IEEE 754 標準的浮點數（floating-point number）表示法有十二位元，格式如下： 11 10 7 6 0 符號 S（sign） 指數 E（exponent） 小數 F（fraction） 其中，S占 1 位元，0 表正數，1 表負數；E占 4 位元，採excess-8（超 8）編碼；F占 7 位元，由高位 元到低位元的權重（weight）依次為 2-1、2-2、...、2-8。則十進位數-3.625 應表示為： (A) 110101110100 (B) 101100110100 (C) 100101110100 (D) 100100011101

14 在多處理機系統（multiprocessor system）上開發平行程式（parallel program）時，開發者必須儘量做 到下列何者？①使用合理的處理機的個數，以配合程式的平行度（parallelism） ②儘可能降低處理 機之間的資料通信量，以減少傳輸與等待的時間 ③儘可能增加處理機之間的同步次數，以增加效能 ④將工作量平均分配到所有的處理機，以避免處理機閒置 (A)①②③④ (B)①②③ (C)②④ (D)①②④

15 下列那些是有特權的指令（privileged instructions）？①關閉中斷（turn off interrupt） ②設定系統計 時器的數值（set value of system timer） ③I/O 的控制命令 ④從使用者模式（user mode）切換成系 統監督模式（monitor mode） ⑤讀取系統時鐘（system clock）的數值 (A)①②③④⑤ (B)①②③④ (C)①②③ (D)①③④