5 對一個堆疊（stack）依序作 push（A）, push（B）, push（C）, pop(), pop(), push（D）, pop(), pop()，則上述四次pop()的結果依序為何？
(A) CBDA
(B) ABCD
(C) ABDC
(D) CBAD.

1 若要將二元搜尋樹（binary search tree）中的元素由小到大依序走訪，可使用何種走訪法？ (A)前序走訪（preorder traversal） (B)中序走訪（inorder traversal） (C)後序走訪（postorder traversal） (D)合併走訪（merge traversal）

2 下列有關 Prim 演算法（Prim’s algorithm）的敘述，何者正確？ (A) Prim 演算法是搜尋二元樹（binary tree）的演算法 (B) Prim 演算法是搜尋二元搜尋樹（binary search tree）的演算法 (C) Prim 演算法是找出最低成本展開樹（minimum-cost spanning tree）的演算法 (D) Prim 演算法是廣度優先搜尋（breadth-first search）的演算法

3 資料個數很少時（例如 10 筆以下），以下那一種排序演算法能得到較佳效能？ (A) Quick sort (B) Insertion sort (C) Heap sort (D) Merge sort

4 假設記憶體中儲存一整數（Integer）資料必須使用 4 位元組（Byte）。今有一整數矩陣（Matrix）T 宣告為 T[n][n]。若 T 為上三角矩陣（Upper triangular matrix），如下所列是有關 T 之敘述：①T 其位於主對 角線（Main diagonal）上之組成元素其值皆為 0，即 T[k][k] = 0，0 ≤ k < n ②T[i][j] = 0，0 ≤ i ≤ j < n ③若矩陣 U = T × T，則 U 亦為上三角矩陣（Upper triangular matrix） ④為節省記憶體儲存空間， 可宣告一維陣列（One dimensional array）A[m]儲存 T 中非 0 之組成元素，則 m ≤ n (n + 1)/2 ⑤將 T 之組成元素存入一維陣列（One dimensional array）A 之順序可選擇依“列為主順序（Row major order）＂ 或“行為主順序（Column major order）＂之方式。請選出最適合之選項： (A)②③正確；④錯誤 (B)①⑤正確；③錯誤 (C)③⑤正確；①錯誤 (D)①②正確；④錯誤

6 下列何者為樹林（forest）資料結構的定義？ (A)由零或零個以上互斥節點（disjoint node）所組成的集合 (B)由零或零個以上互斥葉節點（disjoint leaf node）所組成的集合 (C)由零或零個以上互斥樹（disjoint tree）所組成的集合 (D)由零或零個以上互斥路徑（disjoint path）所組成的集合

7 下列為使用雜湊（Hashing）法有關之敘述：①雜湊（Hashing）法之主要應用為資料搜尋（Searching）， 故搜尋資料效率優於插入（Insertion）與刪除（Deletion）資料之效率 ②雜湊（Hashing）法之要點 為：使用雜湊函式（Hash function）將資料鍵（Key）值對應至雜湊表（Hash table）中之儲存位置 ③使用雜湊（Hashing）法搜尋資料，其最佳情況（Best case）與最糟情況（Worst case）時間複雜 度（Time complexity）皆為 O(1) ④使用雜湊（Hashing）法之優點為：不需要比較鍵值（Key value） 且資料不需要依據鍵值（Key value）排序之順序儲存 ⑤使用雜湊（Hashing）法之缺點為：雜湊表 （Hash table）使用大量之記憶體儲存空間且雜湊函式（Hash function）計算費時。請由下列選項中 選出最適合者： (A)①②正確；③⑤錯誤 (B)③④正確；①⑤錯誤 (C)①③錯誤 (D)②④正確

8 雙向鏈結串列（linked list）中每一節點有 data、prev、next 三個欄位。data 儲存資料而 prev 和 next 兩個指標分別指到前一個和後一個節點。則以下 C++程式指令執行結果為何？(A) 10 (B) 30 (C) 20 (D)無法執行

9 下列那一種資料結構（data structure），最適合以深度優先搜尋（depth first search）走訪一個圖形 （graph）時所採用？ (A)集合（set） (B)串列（list） (C)堆疊（stack） (D)佇列（queue）

10 下列為有關使用 Dijkstra 演算法於圖形（Graph）結構 G 中尋找最短路徑（Shortest path）之敘述： ①Dijkstra 演算法僅適用於對邊線（Edge）具權值（Weight）之有向連接圖形（Directed connected graph） 結構 G 尋找最短路徑 ② 使用 Dijkstra 演算法可尋找 G 中自任一頂點（Vertex）至所有其他頂 點（Vertex）之最短路徑（Shortest path） ③使用 Dijkstra 演算法可尋找 G 中除了頂點（Vertex）vA 以外之所有頂點（Vertex）至 vA 之最短路徑（Shortest path） ④使用 Dijkstra 演算法對圖形（Graph） 結構 G 尋找最短路徑時，必須使用接鄰串列（Adjacency list）儲存 G ⑤使用 Dijkstra 演算法對圖形 （Graph）結構 G 找出之最短路徑中，若存在環路（Cycle），則組成該環路之所有邊線中，至少有 一邊線其權值（Weight）為負值。請選出最適合之選項： (A)②正確；④⑤錯誤 (B)①正確；③④錯誤 (C)④正確；②⑤錯誤 (D)⑤正確；①④錯誤

【已刪除】11 假設系統中只有三個程序 P1、P2 與 P3，其進入 ready queue 的時間（arrival time）、需要花費的 CPU 時間（CPU time）與各程序的優先權（priority）如下表所示。假設 priority 數值越小，優先權越高，且 程序的執行為非搶先（non-preemptive）的，這三個程序的平均等待時間為：  (A) 4.33（ms） (B) 5.67（ms） (C) 5.33（ms） (D) 6（ms）(E)一律給分