112 關務特考三等 電機工程 計算機概論 考古題詳解
第 一 題20 分
假設有兩個整數 與 ，在記憶體各占 8 個位元， 與 。（每小題 10 分，共 20 分）
（一）若 與 都是以「符號及值（sign-and-magnitude）」格式儲存的整數，則 的結果以 8 個位元的「符號及值」格式表示是多少？以十進位表示是多少？請詳細說明計算過程。
（二）若 與 都是以「二補數（2’s complement）」格式儲存的整數，則 的結果以 8 個位元的「二補數」格式表示是多少？以十進位表示是多少？請詳細說明計算過程。
登入後即可作答並保存紀錄。
核心觀念
本題比較 8 位元整數的兩種表示法：
- 符號及值（sign-and-magnitude）：最高位是符號位， 表示正、 表示負；其餘 7 位表示數值大小。
- 二補數（2’s complement）：正數以一般二進位表示；負數可由正數位元逐位反相再加 得到。8 位元二補數的範圍為 至 。
減法可改寫為加法：
（一）符號及值格式
解題方法
先依符號位與數值位解讀 、，再計算十進位的 ，最後轉換成符號及值格式。
的符號位為 ，代表負數；數值位為 ：
的符號位為 ，代表正數；數值位為 ：
因此：
的二進位為 ，補足為 7 位數值欄位：
結果為負數，符號位設為 ，故 8 位元符號及值表示為：
解題技巧
符號及值格式的最高位只負責標示正負，不能把整個 8 位元字串直接當作一般二進位數計算。先拆出符號位與數值位，再進行十進位運算，可避免混淆。
（二）二補數格式
解題方法
先將 、 解讀為二補數，再將 改寫為 。
第 二 題20 分
（一）假設有某一個無階級（classless）IP 位址為 ，則下列 IP 位址何者與前述 IP 位址是在同一個子網域（subnet）？詳細說明理由。（10 分）
（一）子網域判斷
核心觀念
/30 表示子網路遮罩前 30 個位元為 1，後 2 個位元為 0：
每個子網有 個位址，子網網路位址以最後一個八位元組每 4 為一個區段遞增。
解題方法
將 IP 位址最後一個八位元組 除以區段大小 ，取所在區段的起點：
因此， 所屬子網的範圍是 至 ；網路位址為 ，廣播位址為 。可供主機使用的位址是 與 。
選項分析
- (A) ：錯誤。 位於網路位址 至廣播位址 的另一個
/30子網。 - (B) ：正確。 是題目所給 IP 位址所屬子網的網路位址。
- (C) ：錯誤。 所在子網為 至 ，與題目所給位址不同網段。
- (D) ：錯誤。 第三個八位元組已由 變為 ，屬於不同的子網。
解題技巧
/30 的區段大小為 ，所以直接把最後一個八位元組分成 –、–、……的區段，即可快速判斷。選項中的網路位址、主機位址或廣播位址，只要落在同一個四位址區段，都屬於同一子網。
第 三 題20 分
（一）假設有下列三個二元樹走訪的結果：
-
用中序走訪（Inorder traversal）得到的結果是 。
-
用前序走訪（Preorder traversal）得到的結果是 。
-
用後序走訪（Postorder traversal）得到的結果是 。
則上述二元樹中，何者的根（root）一定是相同的節點？說明其理由。（5 分）
（二）又假若上述第 1 項與第 2 項是針對同一個二元樹各別進行中序走訪與前序走訪的結果，請建構出此二元樹。（15 分）
登入後即可作答並保存紀錄。
核心觀念
- 前序走訪（Preorder）：根 左子樹 右子樹。
- 中序走訪（Inorder）：左子樹 根 右子樹。
- 後序走訪（Postorder）：左子樹 右子樹 根。
因此，前序走訪的第一個節點是根；後序走訪的最後一個節點也是根。中序走訪的根則位於左、右子樹走訪序列的分界處。
解題方法
（一）判斷根節點
前序結果為 ，第一個節點是 ，故根為 。
後序結果為 ，最後一個節點也是 ，故根同樣為 。
中序結果為 ，其中 位於左、右子樹序列之間，也與根為 相符。
所以三種走訪結果中的根相同，都是 。
（二）由中序與前序建構二元樹
前序第一個節點是根，因此根為 。在中序序列 中， 左側的 是左子樹，右側的 是右子樹。
第 四 題20 分
（一）假設一個網球單打公開賽採單敗淘汰賽，亦即在每一場比賽中輸的人就出局且無法晉級，贏的人繼續下一場比賽，如此直到最後勝出的一人即是比賽的冠軍者。若此次賽事共有 342 人報名，請問總共要安排幾場賽事，才能決定出最後的冠軍者？請詳細說明理由或計算過程。（10 分）
（二）下列的函式是 C 語言的 function：
int xyz(int x, int y) { if (y == 0) return x; else return (xyz(y, x % y)); }
則呼叫 xyz(60, 45) 會得到什麼結果？詳細列出程式碼的執行過程。（10 分）
登入後即可作答並保存紀錄。
核心觀念
單敗淘汰賽中，每場比賽恰有一人落敗並出局。要從 名參賽者中決出一位冠軍，最後必須淘汰其餘 人。
解題方法
每安排一場比賽，就有一名參賽者出局，因此總場數等於需要淘汰的人數：
無論各輪如何安排對戰，決出冠軍都必須讓其餘每位參賽者各輸一場，故共需 場。
解題技巧
可用「參賽人數減一」快速計算單敗淘汰賽場數。參賽者即使是輪空晉級，也不會增加淘汰人數，因此不影響總場數。
（二）函式 xyz(60, 45) 的結果
核心觀念
函式使用遞迴與取餘數運算，實作的是輾轉相除法，用來求兩個整數的最大公因數。當第二個參數 為 時，回傳第一個參數 ，遞迴即告結束。
解題方法
依照函式呼叫順序逐步計算：
第 五 題20 分
（一）電腦作業系統使用虛擬記憶體的概念。假設每個分頁（page）大小為 4KB，而此電腦的實體記憶體總共有 1024 框（frame），且邏輯位址（logical address）有 24 位元。則該電腦的實體位址（physical address）有多少個位元？且此電腦系統總共有幾個分頁？（10 分）
（二）若對比於常見的資訊安全三原則，下列案例各別是屬於何種攻擊？請說明理由。（10 分）
-
針對使用者的桌機螢幕，偷偷將其螢幕畫面拍下來。
-
到服飾店購買衣服，偷偷將價錢標籤替換成較便宜的標籤去結帳。
登入後即可作答並保存紀錄。
核心觀念
位址由「分頁號」與「頁內位移」組成。頁面大小決定頁內位移的位元數；邏輯位址總位元數扣除頁內位移位元數，即為分頁號位元數。實體位址則由「框號」與「框內位移」組成。
解題方法
每頁大小為 位元組，因此頁內位移需要 位元。
邏輯位址為 位元，故分頁號占：
因此邏輯位址空間共有：
實體記憶體共有 個框，框號需要 位元。每框大小與每頁相同，框內位移需要 位元，所以實體位址長度為：
解題技巧
先由頁面大小換算頁內位移，再分別計算邏輯位址中的分頁號與實體位址中的框號。分頁數由邏輯位址空間決定，框數則用來計算實體位址中的框號位元數，兩者不要混淆。
（二）資訊安全三原則中的攻擊類型
核心觀念