100年 - 100 鐵路特種考試_員級_電子工程、資訊處理：計算機概要#45972

1 若 C 程式語言之程式中宣告一整數陣列（Array）M[15][12]，且 M[5][5]儲存於記憶體中之位址（Address）為 13244868。假設記憶體中儲存一整數（Integer）資料必須使用 4 個位元組（Byte），且陣列 M 之組成元素使用行為主順序（Column major order）之方式儲存，則下列各選項何者正確？ (A) M[6][6]儲存於記憶體中之位址（Address）為 13244928 (B)與 M[14][10]接鄰儲存之組成元素為 M[13][10]與 M[15][10] (C) M 之組成元素 M[4][8]儲存於記憶體中之位址（Address）介於 M[9][3]之位址（Address） M[5][9] 與之位址（Address）之間 (D)儲存 M 所使用之記憶體是位址（Address）自 13244548 至 13245268 之連續記憶體儲存空間

2 下列何者不是堆疊（stack）的應用？ (A)將資料反向排列 (B)程式中副函式的呼叫與返回 (C)在運算式中作括號的配對 (D)尋找一群數值資料中的最大值

3 樹狀（Tree）結構由儲存資料之節點（Node）與連接節點之邊（Edge）組成。下列為有關二元樹（Binary tree）之敘述： ①二元樹（Binary tree）結構中所有節點之分支度（Degree）皆為 2。 ②二元樹（Binary tree）結構中外部節點（External node）之數量是內部節點（Internal node）之數量的 2 倍。 ③二元樹（Binary tree）結構中，除了樹根（Root）節點之外，所有節點皆最多可有兩個父母節點（Parent node）。 ④二元樹（Binary tree）結構中，除了樹根（Root）節點之外，所有節點皆最多可有兩個兄弟節點（Siblings）。 ⑤二元樹（Binary tree）結構中，所有內部節點皆有非空（Non-empty）之左子樹（Subtree）與非空（Non-empty）之右子樹。請選出最適合之選項： (A)①②正確；③⑤錯誤 (B)②④正確；①⑤錯誤 (C)①④錯誤 (D)②⑤正確

4 以下那個序列是右圖的 Breadth-first search 順序？ 0 (A) 0、1、3、2、4、5 (B) 0、1、3、5、4、2 1 2 (C) 0、1、2、4、5、3 (D) 0、1、2、3、4、5

5 一圖形（graph）有 n 個端點（vertices）以及 e 個邊（edges）。若用相鄰矩陣（adjacency matrix）來表示該圖形，則決定該圖形是否為相連圖形（connected graph）所需之時間複雜度（time complexity）為何？ (A)O(n) (B)O(n+e) (C)O(n²) (D)O(n log n)

6 將整數陣列依下列步驟排序的演算法為何？

(A)快速排序法（quick sort） (B)選擇排序法（selection sort） (C)氣泡排序法（bubble sort） (D)合併排序法（merge sort）

7 使用雜湊（Hashing）法時，以 ht 表示雜湊表（Hash table），且 ht 分為 ht[0]、ht[1]、…、ht[b-1]等共計 b 組桶（Bucket），每一桶（Bucket）可存入 s 筆資料；以 f 表示雜湊函式（Hash function）。若 n 為實際存入 ht 之資料筆數，且發生碰撞（Collision）之情形。下列為有關發生碰撞（Collision）可能原因之敘述： ①發生碰撞（Collision）之原因是因為n > b。 ②發生碰撞（Collision）之原因是因為n = b。 ③發生碰撞（Collision）之原因是因為n < b。 ④發生碰撞（Collision）之原因是因為s = 1。 ⑤發生碰撞（Collision）之可能原因是因為資料之鍵（Key）值分布不平均。 ⑥發生碰撞（Collision）之可能原因是因為雜湊函式（Hash function）f 設計不良。 發生碰撞（Collision）之可能原因與 s 之值有關但與 n 之值無關。 發生碰撞（Collision）之可能原因與雜湊函式（Hash function）f 無關但與 n 之值有關。請由下列選項中選出最適合者： (A)⑤⑥正確 (B)②④錯誤 (C)①④⑤正確 (D)③④⑥錯誤

8 下列中序（Infix）運算式之後序（Postfix）運算式表示方式為何？ (A+B)×(A-C)+(A+B)×(B+C)×(C+A) (A) AB+AC-×AB+BC+CA+××+ (B) AB+AC-AB+BC+CA+×××+ (C) AB+AC-×AB+BC+×CA+×+ (D) AB+AC-AB×+BC+×CA+×+

9 將 7 個數值以下列四種順序插入二元搜尋樹（binary search tree），請問何者所產生的二元搜尋樹有最短的平均搜尋時間？ (A)1234567 (B)4261753 (C)6742513 (D)與插入順序無關

11 下列何者不是虛擬記憶體（virtual memory）的優點？ (A)加快記憶體存取的速度 (B)使程式設計者可以設計較大型程式 (C)增加多程式化程度（degree of multiprogramming） (D)加速程式啟動時間

12 一電路由 3 個暫存器（R0, R1, R2）與 1 個 2 對 1 多工器（2×1 MUX）與 2 輸入端或閘（OR）所組成如下圖所示；其中多工器當 S=0 時，選擇標示為 0 的輸入當輸出，當 S=1 時，選擇標示為 1 的輸入當輸出。當 Load=1 時，R0 進行資料載入動作，而當 Load=0 時，R0 的資料維持不變。試問該電路實現下列何種微指令運算？（註：Ri←Rj 表示暫存器 Rj 的資料內容轉移至暫存器 Ri。）

(A) if (K1=1) then (R0←R1) else if (K2=1) then (R0←R2) (B) if (K2=1) then (R0←R1) else if (K1=1) then (R0←R2) (C) if (K1=1) then (R0←R2) else if (K2=1) then (R0←R1) (D) if (K2=1) then (R0←R2) else if (K1=1) then (R0←R1)

13 處理機對兩個有正負號整數（signed integer）運算元 A 和 B 執行加減法運算，可根據 A, B 的正負號位元（sign bit）與運算結果的正負號位元判斷是否有滿溢（overflow）情況發生。以下判斷方式何者錯誤？ (A)執行 A+B 且 A>=0, B>=0，若結果<0：有滿溢 (B)執行 A+B 且 A<0, B<0，若結果>=0：有滿溢 (C)執行 A-B 且 A>=0, B<0，若結果>0：有滿溢 (D)執行 A-B 且 A<0, B>=0，若結果>=0：有滿溢

14 在使用循序派發管線（in-order issue pipeline）的處理器中，假設管線由前而後依序為：指令取得（instruction fetch）、指令解碼及派發（instruction decode and issue）、指令執行（execution）、資料記憶體存取（data memory access）、資料寫回（write back），則下列三個指令要以何種順序重新排程（schedule），才會最快且仍有正確的結果？ ① lw $t0, 20 ($s2) #load a word from address ($s2+20) to register $t0 ② addu $t1, $t0, $t2 #$t1 = $t0 + $t2 ③ sub $s4, $s4, $t3 #s4 = $s4 - $s3 (A)①→②→③ (B)②→③→① (C)③→②→① (D)①→③→②

15 下列關於號誌（semaphore）的敘述何者有誤？ (A)使用號誌可以完全的避免死結（deadlock） (B)使用號誌可能會導致優先權顛倒（priority inversion） (C)使用計數號誌（counting semaphore）時，該計數號誌內部的記數值的初始值不一定要為 0 (D)可以使用計數號誌實現出二元號誌（binary semaphore）

16 Modulo-N計數器如下圖所示，其中(D3D2D1D0)2 表示資料輸入位元，(Q3Q2Q1Q0)2 表示資料輸出位元，其餘控制位元具有下表之操作特性，試問該計數器為何種計數器？

(A) Modulo-9 計數器 (B) Modulo-10 計數器 (C) Modulo-15 計數器 (D) Modulo-16 計數器

17 下列那一項布林函式等於

+x？ (A) x+y’ (B) x+y (C) x’+y (D) x’+y’

18 給定 16 位元運算元A如下：(1000 1110 1010 0101)2，今欲使用運算子與運算元B以將位於運算元A所有偶數位置之位元值設定為 0，試問使用的運算子與運算元B應為何者？（設A中位元位置的編號為最右方者稱為 0，次右方者稱為 1，餘類推。） (A)XOR, (1010 1010 1010 1010)2 (B)XOR, (0101 0101 0101 0101)2 (C)AND, (1010 1010 1010 1010)2 (D)AND, (0101 0101 0101 0101)2

19 在一個多處理機系統中，有多個獨立的工作（tasks）在執行。若是增加該系統中處理器的個數，是否有助改善該系統整體的生產率（throughput，單位時間內完成工作的數目）或者是回應時間（response time，平均每個工作完成所需時間）？（假設目前系統正在處理的工作不具有任何平行性，且其個數大於處理機的個數。） (A)僅改善生產率 (B)僅改善回應時間 (C)改善回應時間及生產率 (D)不會有任何改善

20 在計算機組織中，資料儲存（data storage）的特性對於系統效能相當重要。以下對於儲存裝置之速度和容量比較之敘述何者正確？ (A)快閃記憶體（flash memory）的存取速度較硬碟（hard disk）快 (B) CPU 暫存器（register）的容量較 CPU 快取（cache）大 (C)主記憶體（DRAM）的存取速度較 CPU 快取（cache）快 (D)主記憶體（DRAM）的容量較快閃記憶體（flash memory）大

21 在一般電腦系統中，下列那一個單元或元件負責程式執行時將虛擬記憶體位址（virtual address）轉換為實體記憶體位址（physical address）？ (A) Virtual machine (B) Memory-management unit (C) Register file (D) Memory-address register

22 右圖的功能應如何描述？(A) 1-to-2 Decoder (B) 2-to-4 Decoder (C) 2-to-1 MUX (D) 4-to-1 MUX

23 試問下列何種電子元件，在外部電源關閉後，無法保存資料？ (A)硬碟（hard disk） (B)快閃記憶體（flash memory） (C)快取記憶體（cache memory） (D)唯讀記憶體（read only memory）

24 下列關於程式計數器（Program Counter，簡稱 PC）的敘述，何者錯誤？ (A)在中央處理機內部 (B)用來記錄下一個要執行的指令位址 (C)是暫存器的一種 (D)用來解碼指令

25 下列程式語言，何者屬於物件導向（object-oriented）程式語言？ (A) Java (B) BASIC (C)C (D)組合語言

26 執行下列 C 語言程式後，產生的輸出為何？ #include main() { int S = 0, i; for( i = 1;i < 10; i++) S +=i; printf(“%d ”, S); } (A) 55 (B) 45 (C) 36 (D)變數 d 未宣告，編譯程式會產生錯誤，無法執行

27 下面為一個 C++程式語言撰寫之程式，請選出正確的敘述： class T1 { public: T1() {} //① void foo() { val_= 10;} //② private: int val_; //③ }; int main() { T1 t; //④ return 0; } (A)①行中，因為類別名稱已經取名為 T1，因此不可再有名稱為 T1 的成員函式 (B)②行中，foo 為 T1 的成員函式，在 foo 中可以存取 T1 的私有成員 val_ (C)③行中，val_ 為 T1 的成員，所有 T1 類別的物件共享一份 val_ (D)④行中，我們稱 t 繼承自 T1

28 下列有關副程式（subprogram）的敘述，何者錯誤？ (A)會使程式結構複雜，較不容易閱讀 (B)可節省重複撰寫程式的時間 (C)可節省記憶體空間 (D)可以在主程式中需要的地方加以叫用

29 有關下列兩個 C 語言程式片段的敘述，何者正確？(A)兩個程式片段的執行結果完全相同，且兩個程式片段的控制流程完全相同 (B)兩個程式片段的執行結果不同，但兩個程式片段的控制流程完全相同 (C)兩個程式片段的控制流程不同，但兩個程式片段的執行結果完全相同 (D)兩個程式片段的控制流程不同，且兩個程式片段的執行結果也不相同