電力工程 92 年計算機概論考古題

假設一個系統其時間之使用率(utilization)如下： CPU 使用率：10％ DBK 使用率：95％ 則下列那一項工作可有效提升系統效率？並說明原因。(20 分) 更換一條較快之CPU 增加多工(multiprogramming) 減少多工 安裝更大之記憶體 安裝更快之硬碟

解釋名詞：（每小題5 分，共20 分） FAT（File Allocation Table） MODEM（Modulation/Demodulation） SRAM（Static Random Access Memory） Multitasking

考慮下面的虛擬程式（pseudocode）： if (A < B) and (A < 0) then C := 1 else if B > 2 then C := 2 else if A > 3 then C := 3 else C := 4 A 與B 的數值要滿足什麼條件，才會使C 的值為4？請用兩個不同形式（forms） 來表示此條件，第一個用到邏輯的否定“not＂，第二個則不用“not＂。（20 分）

說明在一個現有計算機von Neumann 結構之 machine cycle。(10 分) 何謂 von Neumann 瓶頸。(10 分)

數字之進制轉換，下標字體代表其進制。（每小題5 分，共20 分） 18.7510＝ 2 10248＝ 10 244.AC16＝ 8 100105＝ 10

有人將快閃記憶體（flash memory）做成的儲存裝置稱為隨身碟、大姆哥，請就製 造技術、儲存資料原理等方面比較它與硬碟機不同之處。（20 分）

何為遞迴演算法(recursive algorithm)？試以n!說明之。(10 分) 此類演算法應注意邊界條件(boundary condition)，試說明之。(10 分)

請利用卡諾圖來化簡下列式子。（須將下圖先行繪製於試卷上後作答， 於本試題上作答者，不予計分）（10 分）

在一個完全二元樹（complete binary tree）中，若任一個節點（node）上的值都不比 其父節點（parent node）上的值小，則稱該二元樹為堆積（heap）。你要將數值以 堆積的結構儲存，且每輸入一個新數值後，都要能儘快形成堆積。要循序輸入七個 數值6,8,3,2,9,4,5。請畫出每輸入一個數值後，所形成的堆積。你的答案為七個堆 積。（20 分）

軟體工程(software engineering)之目的為何？(10 分) 試畫出軟體之生命週期(software life cycle)。(10 分)

請繪圖說明三種網路架構拓樸（Topology ）：匯流排網路（Bus network）、環狀網路（Ring network）與星狀網路（Star network）並比較 其優缺點。（15 分） （請接背面） 九十二年公務人員特種考試經濟部專利商標審查人員考試試題 代號： 科 別： 電力工程、電信工程 全一張 （背面） 30650 30850

針對含有n 個元素（elements）且已排序（sorted）的陣列（array），做n 次二元搜 尋（binary search）的時間複雜度是多少？做n 次線性搜尋（linear search）的時間 複雜度是多少？請分別簡略說明搜尋過程及如何得到時間複雜度。在什麼情況，你 會使用上述兩種搜尋方式中時間複雜度較差者而捨棄時間複雜度較佳者？（20 分）

以一if-then-else 指令(不限語言)改寫下列程式片段。(10 分) if X>10 then goto 10 X=X+1 goto 20 10 X=X+2 20 stop 下列之程式片段之時間複雜度為何？（10 分) i = 1； j = 0； for k = 1 to n do {j = i + j , i = j – i}; return j；

何謂階層式記憶體（hierarchical memory），繪圖並說明之？（10 分） 六、底下為一個HTML 文件檔的基本格式，請說明各段的意義。（10 分） ＜HTML＞ ＜HEAD＞ ＜TITLE＞HTML Documents＜/TITLE＞ ＜/HEAD＞ ＜BODY BACKGROUND＝”bg.jpg”TEXT=blue LINK=red＞ HTML 文件檔的基本格式 ＜/BODY＞ ＜/HTML＞ 七、 寫出死結（deadlock）發生的必要條件。（8 分） 舉出一個死結例子。（3 分） 有何方法可以預防死結？（4 分）

有5000 個節點（nodes）的完全二元樹（complete binary tree）用陣列A 的5000 個 元素（elements）A[1], A[2],…, A[5000]來儲存，且以A[1]代表根（root），則 A[3001]之父節點（parent node）為何？A[3001]有無子節點（child node）？若有， 是那一個？（20 分）