114年 - 114 國家安全情報特種考試_三等_資訊組（選試英文）、電子組（選試英文）：計算機概論#127710

(一)下列兩個 IP 位址為無類別域間路由（Classless Inter-Domain Routing）
的方式切割子網路遮罩（subnet mask）位數均為 27。
請問 200.116.162.82/27 與 200.116.162.114/27，會是在同一個子網路內嗎？請仔細說明你的理由。如果是，那他們所在的子網路 IP 位址範圍是什麼？如果在不同子網路，那他們各自所在的子網路 IP 位址範圍又各是什麼？（15 分）

(二)假設有個雜湊函數（hash function） ，是將一個英文字，轉換成另外一個英文字。其計算過程如下：先把英文字中的每個字母轉換成數字， 把 a 轉成 1，b 轉成 2，以此類推，z 轉成 26。接下來把所有數字相加， 再除以 7，得到的餘數，再把餘數加 1 之後，再乘以 9，得到的數字， 再將其倒過來寫（譬如 27 變成 72，126 變成 621），然後再把每位數 字對應回去英文字母（1 對應回去 a，2 對應回去 b，以此類推） 。
請問 fido、blank、good，那幾個字經過上面這個雜湊函數計算後的字會是 cf？
請將計算過程詳細列出，以說明你的答案。（10 分）

(一)下列的函式是 C 語言的 function：

請問呼叫 xyz(15, 40)以及呼叫 xyz(xyz(42, 63), xyz(105, 60))各會得到
多少？（10 分）

(二)假設已經有一個程式（或演算法）Find_Largest()，可以從輸入的整數資料陣列（array）中，找出最大數值在這陣列的位置。
那麼，請你利用這個 Find_Largest()，寫出一個電腦程式（或演算法） ， 可以找出輸入整數資料陣列中的中間數(median)。
假設所輸入的整數資料陣列，沒有重複的整數資料。
中間數的定義如下：如果全部資料筆數是奇數，則這些資料中比這中間數小的跟大的的筆數剛好一樣。如果全部資料筆數是偶數，則這些資料中比這中間數小的筆數，是比中間數大的筆數少 1。
你的程式或演算法，一定要用到 Find_Largest()才行。（15 分）

(一)假設有一個二元搜尋樹（binary search tree），已知若用後序走訪（postorder）這個二元搜尋樹，得到的結果是 1, 4, 8, 7, 3, 10, 16, 15, 9。
請畫出這個二元搜尋樹。（15 分）

(二)下列式子是用後序（postfix）表示式：
1 2 3 + * 5 +
請問若將他轉成前序（prefix）表示式會是如何？（10 分）

(一)只能利用基本的三種邏輯閘 AND、OR、NOT，設計出一個 1-bit 的二進位減法器線路。這個減法器有兩個 1-bit 的輸入 a 與 b，一個輸出 c， c = a-b。其中，二進位的減法如下：（10 分）
0–0=0
1–0=1
0–1=1
1–1=0

(二)假設一個電腦的實體記憶體有 512 MB，每個字（word）為 4 bytes，且每個分頁（page）大小為 16 KB，總共有邏輯位址（logical address） 空間共 1024*1024 分頁。那麼此電腦的邏輯位址、實體位址（physical address）分別應是多少 bits？請詳列計算過程。（15 分）