111年 - 111 國立嘉義大學_碩士班招生考試試題_資訊管理學系：計算機概論#145432

(1) 依序輸入右邊 7 個值以建立一個 Binary search tree：(C, B, E, F, D, G, A)，請畫出這個 Binary search tree T1。T1 的 Inorder Traversal 的結果有何特性？為什麼會這樣？(5 分)

(2) 有五筆資料(Record)，其排序 Key 值(十進位)分別是 3, 15, 7, 12, 6，我們用 Rk 代表 Key 值為 k 的 Record，所有資料分別是 R3、R15、R7、R12、與 R6。若要以 LSD Radix r Sort 對這些資料進行由小到大排序，可能需要較多的記憶體空間是這個方法的缺點，尤其是排序過程中採用 Array 來實作 Queue 時。請從空間需求的角度來仔細說明，r 值是越大越 好(以 r=10 為例)？還是應該越小越好(以 r=2 為例)？(5 分)

(3) 為了計算出某個 Weighted graph 的 Minimal cost spanning tree，有許多演算法可以採用， 例如 Kruskal’s algorithm、Prim’s algorithm、或是 Sollin’s algorithm 等。這些演算法皆會重 複一樣的動作，因此可以採用 Recursive 或 Iterative 的模式來予以實作。雖然，理論上， 兩種模式的時間複雜度都一樣，但實際執行時，前者會慢於後者，為什麼？(5 分)

(4) 下圖是以 AOE network 畫出來的某專案進度 規 劃圖。如果 a0與 a3一開始就因故各延遲了一天開工，請問這個專案還有辦法在原本的最短完成時 限內做完嗎？請詳細說明你的推論過程。(10 分)

(1) 身為 MIS，請規範五項員工對於自身帳號密碼必須注意的事項。(注意：過於相近的規定 會被視為一項；請依序列出編號，多寫的不予評分。)(5 分)

(2) 身為 MIS，面對網路標準即將從 IPv4 轉換到 IPv6，請列出你的準備工作(5 分)

(3) 採用 NAT 時，內部 IP(Internal IP)可是哪些？(單複選)(5 分)
(A)另一個 NAT 的 External IP (B) Public IP (C)固定 IP (D)浮動 IP (E)Private IP

 i. TCP：少有語音應用程式採用此協定，因為它雖然很可靠，但是它的 ACK 機制卻無用 武之地，請解釋。(5 分)

ii. UDP：多數語音應用程式只能採用本協定，但 UDP 又太不可靠：封包掉了就掉了，哪 個封包不見都沒人知道，例如發話端說「不要」，但分成前後兩個封包發話，結果「不」 的封包遺失了，接收端只聽到「要」，意思大不同。請問這是什麼原因造成？上層(協定) 該提供哪些功能來補救？(5 分)

3. (1)請寫出 ARP 通訊協定的全名及協定的運作方式。(10 分)

(2)一些駭客會使用 ARP 運作的缺點來攻擊網路或是竊取資料，是常見的攻擊手法，請描述 ARP 的攻擊手法。(15 分)

4.(1)IP 子網路切割常會使用到 VLSM 的技術，請寫出 VLSM 的全名，並描述如何使用 VLSM 的技巧來讓切割子網路更有彈性。(10 分)

(2)假設某主機的 IP為172.30.130.84及遮罩255.255.248.0，請計算該主機所在的網路 IP位址、 a5=11 V4 廣播位址及主機的 IP 範圍。(15 分)