刑事警察人員 97 年計算機概論考古題

㈠將A=-1710，B=-1910 以6-bit 2’s complement 二進位形式表示之。（4 分） ㈡請列出A＋B 的計算過程及結果（計算過程與計算結果均以6-bit 表示之）。（4 分） ㈢請問結果是否有Overflow？（4 分） ㈣請問結果是否有Carry？（4 分） ㈤請問結果是否為Negative？（4 分）

假設今有下圖之程式片段， int unknown( int n) { if ( n==1 ) return 0; else if ( n==2 ) return 1; else return unknown (n-1) + unknown (n-2); } ㈠該程式執行時，請敘述其過程，並說明其結果為何？（假設初始輸入的n 值為5）。 （15 分） ㈡請問該程式屬於recursive、iterative 的那一種？並說明原因。（5 分）

㈠請畫出下列常見的幾種網路拓撲（topology）方法：bus、ring、binary tree、star、 2D mesh、fully connected（請各用6 個節點，並以圓圈代表節點，線條代表連結）。 （10 分） ㈡上述各種拓撲中，假設節點數為N，試分別指出：其節點對外通訊所需之維度 （degree，即節點上需具有之I/O 埠數）各為何？（如拓撲中各節點之維度不同 時，請以最大可能之維度回答。）（10 分） 97 年公務人員特種考試警察人員考試及 97 年公務人員特種考試關務人員考試試題 等 別：二等考試 類 科：刑事警察人員犯罪分析組 科 目：計算機概論（包括計算機結構、資料結構、程式設計） g f c a b d e T1

有一二元樹T1 如下： ㈠請寫出T1 的前序追蹤順序（Prefix order traversal）。（6 分） ㈡請寫出T1 的後序追蹤順序（Postfix order traversal）。（6 分） ㈢今有一二元樹T2 含7 個nodes {a,b,c,d,e,f,g}，其前序追蹤順序為b a c e f g d，中 序追蹤順序為a b f e g c d。請畫出T2。（8 分）

今有一byte addressable 電腦，其address 有A 個bits，cache size 為2S bytes，cache block size 為2B bytes，cache 採2W-way set-associative 設計。請問： ㈠Cache 中有多少sets？（5 分） ㈡Address 中的index 欄位占多少bits？（5 分） ㈢Address 中的tag 欄位占多少bits？（5 分） ㈣實做這樣的cache，tag 及data 總共需要多少bits 的儲存空間（假設不計valid bits、 replacement bits 及dirty bits）？（5 分）