公職王歷屆試題 (100 地方政府特考 ) 100 年特種考試地方政府公務人員考試試題等別 : 四等考試類科 : 電子工程 電信工程 資訊處理科目 : 計算機概要 將 127 個相異正整數排序後, 由小到大插入至一個空的二元搜尋樹 (binary search tree), 請問利用此二元搜尋樹尋找

Transcription

1 100 年特種考試地方政府公務人員考試試題等別 : 四等考試類科 : 電子工程 電信工程 資訊處理科目 : 計算機概要 將 127 個相異正整數排序後, 由小到大插入至一個空的二元搜尋樹 (binary search tree), 請問利用此二元搜尋樹尋找 127 個數值中的任一數值, 其最差情況要走訪過幾個節點? 設以 G 表示一非多重圖形 (multigraph) 無自身邊線(self edge) 之有向圖形 (directed graph) 結構, 並以 V 表示 G 之頂點 (vertex) 數, 以 E 表示 G 之邊線 (edge) 數 則下列選項中有關 G 之敘述何者正確? 若 G 中有一頂點 (vertex) 其外向度數 (out-degree) 是 j 且其內向度數 (in-degree) 是 k, 則 G 中有另一頂點 (vertex) 其外向度數 (out-degree) 是 k 且其內向度數 (in-degree) 是 j 若 G 中有環路 (cycle) 存在, 則 G 中至少有一頂點 (vertex) 其外向度數 (out-degree) 與其內向度數 (in-degree) 相等 G 中各頂點 (vertex) 其內向度數 (in-degree) 之總和與各頂點 (vertex) 其外向度數 (outdegree) 之總和相等 V E V ( V -1) Hash table 的溢位處理方法中, 將 hash 到相同位址的鍵值以鏈結串列儲存的策略稱為 : Open addressing Chaining Linear probing MD5 若一整數陣列 (array) 使用 C 程式語言之語法宣告為 K[12] [12] [12], 且 K[7] [7] [7] 儲存於記憶體中之位址 (address) 為 假設記憶體中儲存一個整數(integer) 資料必須使用 4 個位元組 (byte), 且使用列為主順序 (row major order) 之方式儲存陣列之組成元素, 則下列各選項何者正確? K[2] [2] [2] 儲存於記憶體中之位址 (address) 為 K[3] [1] [5] 儲存於記憶體中之位址 (address) 為 K[8] [3] [10] 儲存於記憶體中之位址 (address) 為 K[1] [6] [8] 儲存於記憶體中之位址 (address) 為 在由 n 個節點構成的單向串列 (singly linked list) 中, 若已知某節點 x 前一個節點的位置, 則從串列中刪除節點 x 所花費的時間為 : θ(1) θ(n) θ(n 2 ) θ(log n) 下列那一個運算式的後序表示法 (postfix notation) 為 abc+ d-? (a+b) c-d a (b+c)-d a+b c-d a-(b+c) d 當圖形中出現負數成本的 edge 時, 應採用何種演算法才能正確求出圖形中兩個節點的最短路徑? Dijkstra 演算法 Bellman-ford 演算法 Kruskal 演算法 Prim 演算法 執行快速排序法 (quick sort) 的最差時間複雜度為 : O(log n) O(n) O(n log n) O(n 2 ) 下列何者屬於資料封裝 (data encapsulation) 的機制? 陣列 (arrays) 抽象資料型態 (abstract data types) 迴圈 (loops) 遞迴 (recursion) 假設只有一個節點的 AVL 樹的高度為 0, 請問高度為 4 的 AVL 樹最少有幾個節點? 下列作業系統中, 何者採用了微核心 (micro kernel) 架構? Windows 7 GNU/Linux Microsoft DOS Mach 共 6 頁第 1 頁

2 在電腦系統中, 編寫好的 C 程式會經過數個系統程式轉換為可執行的程式碼 (binary code) 後, 才能被載入到記憶體中準備執行 這些系統程式的執行順序為下列何者? assembler compiler linker loader assembler compiler loader linker compiler assembler linker loader compiler assembler loader linker 在一個分頁系統 (paging system) 中, 假設邏輯位址 (logical address) 為 32 bits, 分頁大小 (page size) 為 4K bytes, 實體記憶體 (physical memory) 為 256M bytes 此系統使用單一層次分頁表 (single-level page table) 且每一分頁表項目 (page table entry) 佔 4 bytes 假設目前有 3 個程序 (processes) 在系統中, 則該系統最多需要用多少實體記憶體來存這些程序的分頁表? 12M bytes 48K bytes 12K bytes 256K bytes 下圖是利用解碼器 (decoder) 實作布林函數 F 的組合電路圖 下列何者是 F 的布林函式? F=x + y + z F=xy + yz + zx F=x y z + x yz + xy z + xyz F=x y z 一個 4 階段管道化精簡指令集計算機 (RISC) 包含指令提取階段 解碼和運算元提取階段 執行階段以及寫回階段 假設在執行之初管道內並無其他指令, 執行時脈為 200 MHz, 且當有資料危障 (data hazard) 的可能時, 只要提供值的指令之寫回階段於前半週期完成, 則若需要該值的指令之解碼和運算元提取階段於同一週期完成, 也就是同一個暫存器的前寫後讀於同一個週期中發生, 即可避免資料錯誤 試問正確地執行下列 6 道指令直至完成最少需要多少時間? ADD R1,R2,R3 SUB R4,R1,R5 AND R2,R4,R7 XOR R10,R2,R11 OR R12,R10,R13 ADD R1,R10,R13 ( 註 : 各指令中第一個暫存器為目的暫存器, 餘為來源暫存器 ) 70 ns 45 ns 65 ns 55 ns 共 6 頁第 2 頁

3 根據以下真值表, 應採用之線路為下列何者? 在邏輯電路中, 令 AND gate 最少可用 x 個 NAND gate 表示,OR gate 最少可用 y 個 NAND gate 表示,NOT gate 最少可用 z 個 NAND gate 表示, 假設上述 AND OR NAND gates 均為具有二個輸入者, 則 x+y+z=? 下列關於 4 位元二進位制的數值表示法, 何者為正確的描述? 2 的補數表示法 (2 s complement) 中, 數值 0 有兩種表示方式 符號與大小表示法 (sign-and-magnitude) 能表示的整數數值範圍為 +7 到 -8 無符號表示法 (unsigned) 能表示的整數數值範圍為 0 到 16 2 的補數表示法 (2 s complement) 能表示的整數數值範圍為 +7 到 -8 以下有關於磁碟陣列 (redundant array of inexpensive disks, RAID) 的敘述, 何者錯誤? RAID 0 主要的目的之一是提高系統對檔案的讀取速度 RAID 0 並沒有冗餘 (redundancy) 功能 RAID 1 提供資料鏡射複製 (mirroring) 功能 RAID 3 以 Hamming Code 進行錯誤更正 在一電腦系統上, 某程式的執行時間中, 處理機有 80% 花在計算, 剩餘的 20% 時間為存取磁碟檔案資料 若將其處理機由單核心升級到四核心, 每一核心的架構與時脈不變, 程式也具有理想的平行度並且予以適當平行化, 則該程式整體效能最高可提升為多少倍? 2 倍 2.5 倍 3 倍 3.5 倍 以下何者為組成一台電腦之基本元件?1 輸入裝置 2 輸出裝置 3 記憶體 4 資料通路 (datapath) 5 控制單元 在分頁 (paging) 機制中, 下列那一項單元或元件可做為分頁表 (page table) 的快取 (caching) 機制? Memory-management unit(mmu) First-level cache Reorder buffer(rob) Translation look-aside buffer(tlb) 試問下列何者為通用閘 (universal gate)? 通用閘的意思是任何布林函數 (boolean function) 均可僅用此種邏輯閘即予實現 : AND 邏輯閘 Inverter 邏輯閘 NOR 邏輯閘 OR 邏輯閘 下列何者不等於十進位數 (36) 10? 十六進位數 (24) 16 八進位數 (44) 8 二進位數 ( ) 2 二進位數 ( ) 2 共 6 頁第 3 頁

4 在開放系統互連 (Open System Interconnection, OSI) 參考模型之網路架構中, 下列何者是網路層 (network layer) 所負責的工作? 控制資料流量 資料的壓縮和解壓縮 偵錯與錯誤處理 路徑選擇 以下有關資訊安全的敘述何者錯誤? 數位信封 (digital envelop) 的觀念就是使用收訊人的公開金鑰 (public key) 對某些機密資料作加密, 收訊人收到後再使用自己的私密金鑰 (private key) 解密而讀取資料 傳訊人使用其私密金鑰 (private key) 將原始訊息進行加密, 即得到此訊息的數位簽章 (digital signature) 數位憑證 (digital certificate) 內含有憑證持有者的公開金鑰 (public key) SSL(Secure Socket Layer) 架構於 TCP 傳輸層 (TCP transport layer) 之上, 應用層 (application layer) 之下 在電腦網路中,SNMP 之用途為 : 電子郵件傳輸協定 儲存網路管理物件的資料庫 網路管理協定 資訊安全協定 下列那一種網路服務協定, 在實際應用上, 通常建構在 UDP(User Datagram Protocol) 網路通信協定之上? HTTPS(Hypertext Transfer Protocol Secure) SMTP(Simple Mail Transfer Protocol) TELNET(Teletype network) VoIP(Voice over Internet Protocol) ISO 組織將網路管理區分為五大項目, 以下何者不在其中? 流程管理 錯誤管理 效能管理 組態管理 在 Internet 架構中, 那一層通訊協定負責提供不同主機上的程序 (processes) 之間的邏輯通道 (logical channels)? 應用層 (application layer) 資料鏈結層 (data link layer) 網路層 (network layer) 傳輸層 (transport layer) 網頁代理伺服器 (Proxy) 之功能為 : 網頁資料搜尋比對 增加網頁互動性 加速網頁下載效能 加速網頁上傳檔案效能 網路中每一台主機均需有 IP 位址, 以下何種協定用來自動設定 IP 位址以方便管理網路 : DNS ARP SNMP DHCP 在 C-like 程式語言中, 陣列 (array) 中最小的索引值 (index) 為何? 0 1 依該陣列宣告而定 隨著程式執行而改變 已知一 C 語言程式中, 宣告陣列 A 為 int A[10][4], 且 A 在記憶體的位址為 0x0080(0x 代表 16 進位表示法 ), 若每個 int 資料使用 4 個位元組 (byte), 請問 A[3][3] 使用的記憶體位址為何? 0x0131 0x0113 0x00B3 0x00BC C 或 C++ 程式語言中, 當 & 運算子(operator) 置於變數 (variable) 前時, 其代表的意義為何? 該變數的值 (value) 該變數的格式 (format) 該變數的位址 (address) 該變數的二進位形式 (binary form) 關於 C++ 或 Java 程式語言中的建構子 (constructor), 下列敘述何者正確? 它無法回傳資料值 (return data value) 它的回傳值型別 (type) 為 void 它的回傳值型別為 int 它的回傳值型別由程式設計者決定 共 6 頁第 4 頁

5 下列以 C 程式語言撰寫之程式執行後產生之輸出為何? 下列以 C 程式語言撰寫之程式執行後, 若使用者輸入的數值為 20, 則畫面上的輸出為何? 下列以 C++ 程式語言撰寫之程式執行後的輸出為何? CD ACBD ACDB CABD 共 6 頁第 5 頁

6 下列以 C++ 程式語言撰寫之程式執行後的輸出為何? 程式無法通過編譯 共 6 頁第 6 頁