114 國安局特考三等 資訊組(選試英文) 計算機概論 考古題詳解
第 一 題25 分
(一) 下列兩個 IP 位址以無類別域間路由（Classless Inter-Domain Routing）的方式切割子網路遮罩（subnet mask）位數均為 ：
與 是否會是在同一個子網路內？請仔細說明理由。
如果是，則它們所在的子網路 IP 位址範圍是什麼？
如果在不同子網路，則它們各自所在的子網路 IP 位址範圍又各是什麼？（15 分）
(二) 假設有個雜湊函數（hash function），是將一個英文字，轉換成另外一個英文字。其計算過程如下：
先把英文字中的每個字母轉換成數字，把 轉成 、 轉成 ，依此類推， 轉成 。
接下來把所有數字相加，再除以 ，得到的餘數再加 ，之後再乘以 ，得到一個數字。
再將該數字倒過來寫，例如 變成 、 變成 。
然後再把每位數字對應回英文字母， 對應回 、 對應回 ，依此類推。
請問 fido、blank、good，哪幾個字經過上述雜湊函數計算後的字會是 cf？
請將計算過程詳細列出，以說明你的答案。（10 分）
登入後即可作答並保存紀錄。
（一）判斷兩個 IP 位址是否位於同一子網路
核心觀念
CIDR 前綴 /27 表示子網路遮罩前 27 個位元為 1，亦即子網路遮罩為 255.255.255.224。最後一個位元組的子網路區塊大小為 ，所以每個子網路涵蓋 32 個連續位址。
解題方法
前 3 個位元組相同，都是 200.116.162，只需比較最後一個位元組分別落在哪個 32 位址區塊：
82落在64–95區間，因為 。114落在96–127區間，因為 。
兩者的區塊不同，因此不在同一個子網路。
各子網路範圍如下：
200.116.162.82/27所在網段：網路位址200.116.162.64，廣播位址200.116.162.95，完整位址範圍為200.116.162.64–200.116.162.95。可用主機位址為200.116.162.65–200.116.162.94。200.116.162.114/27所在網段：網路位址200.116.162.96，廣播位址200.116.162.127，完整位址範圍為200.116.162.96–200.116.162.127。可用主機位址為200.116.162.97–200.116.162.126。
解題技巧
/27 的區塊大小是 32，可直接列出最後一個位元組的網段起點：0、32、64、96、128、160、192、224。看各位址落在哪個區間，就能迅速判斷是否同網段。
第 二 題25 分
(一) 下列的函式是 C 語言的 function：
請問呼叫 以及呼叫 各會得到多少？（10 分）
(二) 假設已經有一個程式（或演算法），可以從輸入的整數資料陣列（array）中，找出最大數值在這陣列的位置。
請利用這個 ，寫出一個電腦程式（或演算法），可以找出輸入整數資料陣列中的中間數（median）。
假設所輸入的整數資料陣列，沒有重複的整數資料。
中間數的定義如下：
如果全部資料筆數是奇數，則這些資料中比這個中間數小的筆數，跟比這個中間數大的筆數，剛好一樣。
如果全部資料筆數是偶數，則這些資料中比這個中間數小的筆數，是比中間數大的筆數少 。
你的程式或演算法，一定要用到 才行。（15 分）
登入後即可作答並保存紀錄。
(一) 函式 xyz 的回傳值
核心觀念
函式從 開始遞減，遇到第一個同時整除 與 的數，就立即回傳。因此，xyz(x, y) 會回傳 和 的最大公因數。
解題方法
呼叫 xyz(15, 40) 時， 由 遞減。最大的共同因數為 ：
所以 xyz(15, 40) 回傳 。
巢狀呼叫由內而外計算：
因此外層呼叫為：
解題技巧
函式從第一個引數開始往下搜尋，並在找到共同因數時立刻回傳；因此第一個找到的共同因數就是最大公因數。
(二) 使用 Find_Largest 找中間數
核心觀念
資料沒有重複時，將 筆資料由小到大排列，中間數的位置（以 1 為起始）為：
若 為奇數，該位置左右資料筆數相等；若 為偶數，取較小的中間數，其左側資料比右側少 ，符合題目定義。Find_Largest 可反覆從尚未處理的資料中找出最大值，依序移至陣列尾端；完成 次後，位置 的資料即為所求。
第 三 題20 分
(一) 假設有一個二元搜尋樹（binary search tree），已知若用後序走訪（postorder）這個二元搜尋樹，得到的結果是：
請畫出這個二元搜尋樹。（15 分）
(二) 下列式子是用後序（postfix）表示式：
請問若將它轉成前序（prefix）表示式會是如何？（10 分）
登入後即可作答並保存紀錄。
核心觀念
二元搜尋樹（Binary Search Tree, BST）中，每個節點的左子樹鍵值都小於該節點，右子樹鍵值都大於該節點。後序走訪的順序是：
因此，後序序列的最後一個值是整棵樹的根；再依 BST 的大小關係，將根之前的序列分成左子樹與右子樹，並對兩邊遞迴處理。
解題方法
給定後序序列：
最後一個值 是根節點。根左側的值小於 ，構成左子樹後序序列：
大於 的值構成右子樹後序序列：
左子樹： 序列最後一個值 是左子樹的根。小於 的 為其左子樹後序序列；大於 的 為其右子樹後序序列。
右子樹的根為 ；其左子樹序列為 ，右子樹序列為 。因此，左子樹結構如下：
3
/ \
1 7
/ \
4 8
右子樹： 序列最後一個值 是右子樹的根。小於 的 為其左子樹，右子樹為空； 為其右子樹。因此結構如下：
15
/ \
10 16
合併左右子樹並接回根節點 ，得到：
9
/ \
3 15
/ \ / \
1 7 10 16
/ \
4 8
解題技巧
第 四 題25 分
(一) 只能利用基本的三種邏輯閘 AND、OR、NOT，設計出一個 -bit 的二進位減法器電路。這個減法器有兩個 -bit 的輸入 與 ，一個輸出 ，且：
其中，二進位的減法如下：
（10 分）
(二) 假設一個電腦的實體記憶體有 ，每個字（word）為 bytes，且每個分頁（page）大小為 ，總共有 分頁。
那麼此電腦的邏輯位址（logical address）、實體位址（physical address）分別應是幾 bits？請詳細列計算過程。（15 分）
登入後即可作答並保存紀錄。
核心觀念
本題分別考查：
- 組合邏輯電路：依輸入與輸出關係列出真值表，再化簡布林函數，並以 AND、OR、NOT 閘實作。
- 位址位元數：位址所需位元數為可表示的位置總數取以 2 為底的對數。位元組定址時，位址涵蓋的單位是 byte；字（word）大小不會改變位址位元數。
（一）1-bit 二進位減法器
解題方法
依題目列出的四種輸入組合，整理真值表：
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
輸出 在 與 不同時為 1，因此是互斥或（XOR）函數。只用 AND、OR、NOT 閘表示為：
電路可分成兩條 AND 路徑：一條計算 ，另一條計算 ，再將兩者的結果輸入 OR 閘。所需閘包含兩個 NOT、兩個 AND 與一個 OR。
解題技巧
逐列對照真值表即可驗算： 時輸出為 0； 時輸出為 1。這也就是本題四種減法結果所呈現的規律。
（二）邏輯位址與實體位址
核心觀念與解題方法
每個位址可表示一個可定址單位。一般電腦採位元組定址，因此記憶體位址數由 byte 總數決定。