

100 年公務人員普通考試試題 代號 :5405 頁次 :6-1 類科 : 電子工程 電信工程 資訊處理科目 : 計算機概要考試時間 :1 小時座號 : 注意 : 本試題為單一選擇題, 請選出一個正確或最適當的答案, 複選作答者, 該題不予計分 本科目共 40 題, 每題 2.5 分, 須用 2B 鉛筆在試卡上依題號清楚劃記, 於本試題上作答者, 不予計分 禁止使用電子計算器 1 若要將二元搜尋樹 (binary search tree) 中的元素由小到大依序走訪, 可使用何種走訪法? 前序走訪 (preorder traversal) 中序走訪 (inorder traversal) 後序走訪 (postorder traversal) 合併走訪 (merge traversal) 2 下列有關 Prim 演算法 (Prim s algorithm) 的敘述, 何者正確? Prim 演算法是搜尋二元樹 (binary tree) 的演算法 Prim 演算法是搜尋二元搜尋樹 (binary search tree) 的演算法 Prim 演算法是找出最低成本展開樹 (minimum-cost spanning tree) 的演算法 Prim 演算法是廣度優先搜尋 (breadth-first search) 的演算法 3 資料個數很少時 ( 例如 10 筆以下 ), 以下那一種排序演算法能得到較佳效能? Quick sort Insertion sort Heap sort Merge sort 4 假設記憶體中儲存一整數 (Integer) 資料必須使用 4 位元組 (Byte) 今有一整數矩陣(Matrix)T 宣告為 T[n][n] 若 T 為上三角矩陣 (Upper triangular matrix), 如下所列是有關 T 之敘述 :1T 其位於主對 角線 (Main diagonal) 上之組成元素其值皆為 0, 即 T[k][k] = 0,0 k < n 2T[i][j] = 0,0 i j < n 3 若矩陣 U = T T, 則 U 亦為上三角矩陣 (Upper triangular matrix) 4 為節省記憶體儲存空間, 可宣告一維陣列 (One dimensional array)a[m] 儲存 T 中非 0 之組成元素, 則 m n (n + 1)/2 5 將 T 之組成元素存入一維陣列 (One dimensional array)a 之順序可選擇依 列為主順序 (Row major order)" 或 行為主順序 (Column major order)" 之方式 請選出最適合之選項 : 23 正確 ;4 錯誤 15 正確 ;3 錯誤 35 正確 ;1 錯誤 12 正確 ;4 錯誤 5 對一個堆疊 (stack) 依序作 push(a), push(b), push (C), pop(), pop(), push(d), pop(), pop(), 則上述四次 pop() 的結果依序為何? CBDA ABCD ABDC CBAD 6 下列何者為樹林 (forest) 資料結構的定義? 由零或零個以上互斥節點 (disjoint node) 所組成的集合 由零或零個以上互斥葉節點 (disjoint leaf node) 所組成的集合 由零或零個以上互斥樹 (disjoint tree) 所組成的集合 由零或零個以上互斥路徑 (disjoint path) 所組成的集合 7 下列為使用雜湊 (Hashing) 法有關之敘述 :1 雜湊 (Hashing) 法之主要應用為資料搜尋 (Searching), 故搜尋資料效率優於插入 (Insertion) 與刪除 (Deletion) 資料之效率 2 雜湊 (Hashing) 法之要點 為 : 使用雜湊函式 (Hash function) 將資料鍵 (Key) 值對應至雜湊表 (Hash table) 中之儲存位置 3 使用雜湊 (Hashing) 法搜尋資料, 其最佳情況 (Best case) 與最糟情況 (Worst case) 時間複雜 度 (Time complexity) 皆為 O(1) 4 使用雜湊 (Hashing) 法之優點為 : 不需要比較鍵值 (Key value) 且資料不需要依據鍵值 (Key value) 排序之順序儲存 5 使用雜湊 (Hashing) 法之缺點為 : 雜湊表 (Hash table) 使用大量之記憶體儲存空間且雜湊函式 (Hash function) 計算費時 請由下列選項中 選出最適合者 : 12 正確 ;35 錯誤 34 正確 ;15 錯誤 13 錯誤 24 正確

頁次 :6-2 8 雙向鏈結串列 (linked list) 中每一節點有 data prev next 三個欄位 data 儲存資料而 prev 和 next 兩個指標分別指到前一個和後一個節點 則以下 C ++ 程式指令執行結果為何? cout << p-> next-> next->prev->data; p prev data next prev data next prev data next null 10 30 20 null 10 30 20 無法執行 9 下列那一種資料結構 (data structure), 最適合以深度優先搜尋 (depth first search) 走訪一個圖形 (graph) 時所採用? 集合 (set) 串列 (list) 堆疊 (stack) 佇列 (queue) 10 下列為有關使用 Dijkstra 演算法於圖形 (Graph) 結構 G 中尋找最短路徑 (Shortest path) 之敘述 : 1Dijkstra 演算法僅適用於對邊線 (Edge) 具權值 (Weight) 之有向連接圖形 (Directed connected graph) 結構 G 尋找最短路徑 2 使用 Dijkstra 演算法可尋找 G 中自任一頂點 (Vertex) 至所有其他頂 點 (Vertex) 之最短路徑 (Shortest path) 3 使用 Dijkstra 演算法可尋找 G 中除了頂點 (Vertex)v A 以外之所有頂點 (Vertex) 至 v A 之最短路徑 (Shortest path) 4 使用 Dijkstra 演算法對圖形 (Graph) 結構 G 尋找最短路徑時, 必須使用接鄰串列 (Adjacency list) 儲存 G 5 使用 Dijkstra 演算法對圖形 (Graph) 結構 G 找出之最短路徑中, 若存在環路 (Cycle), 則組成該環路之所有邊線中, 至少有 一邊線其權值 (Weight) 為負值 請選出最適合之選項 : 2 正確 ;45 錯誤 1 正確 ;34 錯誤 4 正確 ;25 錯誤 5 正確 ;14 錯誤 11 假設系統中只有三個程序 P 1 P 2 與 P 3, 其進入 ready queue 的時間 (arrival time) 需要花費的 CPU 時間 (CPU time) 與各程序的優先權 (priority) 如下表所示 假設 priority 數值越小, 優先權越高, 且 程序的執行為非搶先 (non-preemptive) 的, 這三個程序的平均等待時間為 : 程序 Arrival time(ms) CPU time(ms) Priority P 1 0 4 1 P 2 1 8 3 P 3 1 5 2 4.33(ms) 5.67(ms) 5.33(ms) 6(ms) 12 下圖是那一種正反器 (flip-flop)? X D Q Clk Clk Q' SR flip-flop Positive-edge-triggered D flip-flop Master-slave D flip-flop T flip-flop 13 一般 CPU 均會包含以下三種基本定址模式 :immediate addressing mode register addressing mode 與 base addressing mode 來存取運算元 (operand) 對 CPU 而言, 這三種定址模式取得運算元的速度由快而慢的順序應為何? base addressing mode register addressing mode immediate addressing mode immediate addressing mode register addressing mode base addressing mode register addressing mode immediate addressing mode base addressing mode immediate addressing mode base addressing mode register addressing mode

頁次 :6-3 14 下列三個程序 P 1 P 2 P 3 同時進入系統, 所需的計算時間如下表所示 : 程序名稱 所需計算時間 P 1 20 P 2 3 P 3 3 作業系統使用依序循環 (round robin) 排程演算法, 且每個時間切割 (time quantum) 為 4 個時間單位 這三個程序的平均等待時間為何?( 四捨五入到小數點第二位, 循序排程時依照程序的名稱依序執行 ) 7 5.67 33.67 25 15 在 Linux 作業系統核心中, 下列運算何者最少發生? 浮點數運算 整數運算 指標運算 迴圈運算 16 某組合電路 (combinational circuit) 有兩個輸出 F 1 和 F 2, 其布林函數 (Boolean function) 分別為 : F 1 = AB + AC', F 2 = AC' +BC 若以可規劃邏輯陣列 (programmable logic array, PLA) 來實現此電路, 則下列何者之規格 ( 以輸入個數 積項個數 輸出個數表示之 ) 最恰當? 2 4 2 2 3 2 3 4 2 3 3 2 17 使用 2 個 SR 正反器 (flip-flop) 與 3 個邏輯閘組成一時序電路 (sequential circuit) 如下圖所示, 其中 SR 正反器由 NAND 閘所組成,A B 表示狀態位元,X 表示外部輸入位元,Y 表示輸出位元,S A 與 R A 表示第一個 SR 正反器之輸入位元,S B 與 R B 代表第二個 SR 正反器之輸入位元,CLK 表示時脈, 試問該時序電路之輸出方程式為何? S A A S B B C C R A R B B CLK X Y Y = (A X) + B Y = (A X) + B Y = (A + X) B Y = (A + X) B 18 (126.25) 10 轉換至二進制表示法的結果為何? (111100.10) 2 (111110.10) 2 (1111100.01) 2 (1111110.01) 2 19 下列那一項記憶體定址模式最適用於跳躍指令 (branch instruction) 中用來表示目的位址 (Target address) 之用? PC-relative addressing mode Base addressing mode Immediate addressing mode Register addressing mode 20 在 Windows 上執行辦公室文書類的應用程式 ( 如 :word excel) 時, 發現硬碟不停的在動作, 此時 最可能需要升級那一個系統元件? 處理器時脈 記憶體 顯示卡 螢幕解析度 21 下列有關 TLB(translation look-aside buffer) 的敘述, 何者錯誤? 可以加快真實位址轉換成虛擬位址的時間 一般而言, 在環境切換 (context switch) 時要清空 TLB 若 TLB hit, 則本次存取時間會較 TLB miss 者為快 一般來說, 有 TLB 的機器會有較好的效能

頁次 :6-4 22 一反向器 (Inverter) 邏輯閘之輸出入訊號特性如下圖所示, 其中 V IH = 2.5 伏特 V IL = 1.2 伏特 V OH = 4.5 伏特 V OL = 0.4 伏特 則當該等輸出訊號用於該等輸入時, 其高狀態雜訊容忍度 (High-state Noise Margin) 為何? V dd V dd V IH V OH V IL V OL 0 (a) 輸入電壓範圍 0 (b) 輸出電壓範圍 2.0 伏特 1.3 伏特 3.3 伏特 0.8 伏特 23 下列以 C 程式語言撰寫之程式執行後產生之輸出為何? #include <stdio.h> double foo(int v) return v/2; int main() int n = 10; double m; m = foo(n/2.0); printf("%f", m); return 0; 2.000000 2.500000 5.000000 10.000000 24 關於物件 (object) 與類別 (class) 之間的關聯性, 下列敘述何者正確? 類別 (class) 是物件 (object) 的實例 (instance) 物件 (object) 是類別 (class) 的實例 (instance) 物件 (object) 是其子類別 (subclass) 的祖先 (ancestor) 物件 (object) 是其子類別 (subclass) 的後代 (descendant) 25 下列以 C 程式語言撰寫之程式執行後的輸出為何? #include <stdio.h> void set(int arr[], int size) int i; for (i=0; i<size; i+=1) arr[i] =i; int get(int arr[], int i) return arr[i]/2; int main() int arr[10]; set(arr, 10); printf("%d", get(arr, arr[get(arr, 7)]) ); return 0; 1 3 5 7

頁次 :6-5 26 在 C 語言中, 如何將變數 (variable)s 的資料型別 (data type) 由整數 (integer) 轉換成浮點數 (floating-point)? (float)s s(float) float(s) (s)float 27 假設在 C 或 C ++ 語言中宣告以下陣列 :int array[3][2][2] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12; 試問 array[2][1][0] 的值為何? 5 7 9 11 28 下列何者為 2 的補數 (11100100) 2 所表示的十進位數? -28-27 27 28 29 執行下列 C 語言程式後, 產生的輸出為何? #include <stdio.h> main() int S = 0, i; for( i = 1; i < 10; i++) S +=i; i++; printf( %d\n, S); 55 45 25 編譯程式會產生錯誤, 無法執行 30 下列以 C ++ 程式語言撰寫之程式執行後的輸出為何? #include <iostream> using namespace std; class P public: void foo() cout << 'P'; ; class C : public P public: void foo() cout << 'C'; ; int main() P p; C c; P *pc = &c; P &rc = c; p.foo(); c.foo(); pc->foo(); rc.foo(); return 0; PCPP PPPP PCCC CCCC 31 下列以 C 程式語言撰寫之程式執行後產生之輸出為何? int y[4] = 6, 7, 8, 9; int *ptr = y + 2; printf("%d\n", ptr[ 1 ]); 6 7 8 9

頁次 :6-6 32 在資料庫系統中, 為了避免系統發生故障 (failure) 後造成資料錯亂, 通常會備有預防措施的回復機制 試問下列基於交易紀錄做回復處理 (log-based recovery) 的機制可能遇到的情況之敘述, 何者錯誤? 在停電或斷電情況下導致的系統當機, 電腦主記憶體的內容會因斷電而消失, 影響目前正在執行 的交易, 和儲存在工作區和緩衝區的交易資料 在系統故障 (failure) 後的回復時, 如果某個交易的 開始 和 結束 紀錄都出現在紀錄檔 (log) 中, 表示這筆交易已經完成, 但尚未寫入資料庫, 因此必須重新處理 (redo) 這筆交易, 讓這筆交 易進到資料庫中 在系統故障後的回復時, 如果某個交易的 開始 紀錄出現在紀錄檔中, 表示這筆交易已經開始, 因此必須重新處理這筆交易, 讓這筆交易進到資料庫中 系統故障有可能發生在執行系統回復動作的時間點 33 下列何項機制使得記憶體與 I/O 裝置進行資料傳輸時,CPU 必須一直等待 I/O 裝置準備好才能進行 資料傳輸? Programmed I/O Interrupt-driven I/O DMA Isolated I/O 34 以下有關資訊安全的敘述何者錯誤? 雜湊函數 (hash function) 可以用以儲存密碼檔案, 可以避免系統管理人員或其他人員窺視密碼 傳訊人使用其私密金鑰 (private key) 將原始訊息的摘要 (digest) 進行加密, 即得到此訊息的數 位簽章 (digital signature) RSA 公開金鑰加密法是一種絕對安全 (unconditionally secure) 的加密法 數位信封 (digital envelop) 的觀念就是使用收訊人的公開金鑰 (public key) 對某些機密資料作加 密, 收訊人收到後再使用自己的私密金鑰 (private key) 解密而讀取資料 35 以下有關於磁碟陣列 (redundant array of inexpensive disks, RAID) 的敘述, 何者錯誤? RAID 是一種資料即時備援與復原技術 RAID 0 可以在磁碟機損毀時復原資料 RAID 3 利用同位元 (parity) 技術復原資料 RAID 6 可以在兩個磁碟機同時損毀時復原資料 36 以下有關數位憑證 (Digital Certificate) 撤銷 (Revocation) 的描述, 何者錯誤? 用戶的密鑰遺失會造成認證機構 (Certification Authority, CA) 撤銷用戶的憑證 CA 發現簽發的憑證發給錯誤的用戶, 會撤銷該憑證 使用者只需要檢查憑證是否過期, 不須核對憑證是否已被撤銷 CA 會用憑證撤銷串列 (Certificate Revocation List, CRL) 來記錄所有已撤銷而尚未到期的憑證 37 IP 安全通訊協定 (Internet Protocol Security, 簡稱 IPSec) 包含那個運作協定? IKE(Internet Key Exchange) HMAC(Hash Message Authentication Code) PPTP(Point-to-Point Tunneling Protocol) VPN(Virtual Private Network) 38 以下何者不是公開金鑰基礎建設 (Public Key Infrastructure, PKI) 所提供的安全保障? 不可否認性 (non-repudiation) 鑑定性 (authentication) 完整性 (integrity) 透通性 (transparency) 39 在短時間內發動多台主機, 傳送大量封包至特定主機的攻擊方法稱為 : 分散式阻斷服務 (DDoS) 後門程式 開機型病毒 木馬病毒 40 下列關於智慧財產權 (Intellectual Property Right) 的敘述, 何者錯誤? 電腦程式為一種著作物, 受著作權的保護 電腦程式是可專利的法定標的 小圖像 (icon) 與電腦字型的 (type font) 不是可專利的法定標的 文字 圖片 影音 動畫等素材都是著作, 必須要經過權利人的授權才能利用