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

重新載圖2 對下列二元樹進行前序走訪（preorder traversal）時，走訪的次序為何？ (A) ABCDFGE (B) ABCDEFG (C)BFGDECA (D) BAFDGCE

3 將一組資料視為 n 筆記錄（Record）所組成且 n>2，每一筆記錄由許多欄位（Field）所組成；則依據 記錄中某一欄位之值（稱為“鍵值＂）調整多筆記錄之大小順序稱為排序（Sorting）。下列有關排 序（Sorting）之敘述，何者正確？ (A)進行排序（Sorting）時，必須將每一筆記錄之鍵值與所有其他記錄之鍵值相比較，以決定各記錄 之排列順序 (B)進行排序（Sorting）時，必須將所有記錄儲存於主記憶體（Main memory）中，以便調整各記錄之 排列順序 (C)進行排序（Sorting）時，若有二筆記錄之鍵值相同，則此二筆記錄之排列順序不影響排序結果之 正確性 (D)進行排序（Sorting）實際所需之時間與記錄（Record）之筆數 n 有關，但與記錄（Record）之長度 無關

4 關於超純量處理器（superscalar processor）的描述，下列何者錯誤？ (A)理論上一次可以派發（issue）多道的指令 (B)理論上一個週期可以完成多道指令的執行 (C)需要複製大量的硬體 (D)又可稱為多核心（multi-core）處理器

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

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)②④⑤錯誤

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

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)