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

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)①②正確；④錯誤

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

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)②④正確

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)一律給分

12 下圖是那一種正反器（flip-flop）？ (A) SR flip-flop (B) Positive-edge-triggered D flip-flop (C) Master-slave D flip-flop (D) T flip-flop

13 一般 CPU 均會包含以下三種基本定址模式：immediate addressing mode、register addressing mode 與 base addressing mode 來存取運算元（operand）。對 CPU 而言，這三種定址模式取得運算元的速度由 快而慢的順序應為何？ (A) base addressing mode、register addressing mode、immediate addressing mode (B) immediate addressing mode、register addressing mode、base addressing mode (C) register addressing mode、immediate addressing mode、base addressing mode (D) immediate addressing mode、base addressing mode、register addressing mode 代號：5405 頁次：6－3

14 下列三個程序 P1、P2、P3 同時進入系統，所需的計算時間如下表所示：作業系統使用依序循環（round robin）排程演算法，且每個時間切割（time quantum）為 4 個時間單 位。這三個程序的平均等待時間為何？（四捨五入到小數點第二位，循序排程時依照程序的名稱依 序執行） (A)7 (B) 5.67 (C) 33.67 (D) 25