[考題] 97年鐵路計概

看板Examination作者 (mingrong)時間11年前 (2013/06/19 18:26), 編輯推噓11(11推 0噓 22→)
留言33則, 7人參與, 最新討論串1/1
[問題一] 將 1234567 七個數目依某順序插入一個空的二元搜尋樹（Binary Search Tree）後， 所得的二元搜尋樹如下圖所示： 4 / \ 2 6 / \ / \ 1 3 5 7 總共有幾種可能的插入順序？ (A)40 種 (B)48 種 (C)80 種 (D) 96 種 答案:(C) 這題請問一下要如何計算?? [問題二] 假設一路由器（router）的路徑表格（routing table）如下圖所示。 路由器可以將收到的封包傳給直接相連的網路或其它路由器。選擇路徑的 原則是最長字首相同（longest prefix match）。如果路由器要將封包傳給位 址 140.252.13.45，該透過那一個介面（interface）？ Destination Gateway Flags Refcnt Use Interface ----------------------------------------------------------- 140.252.13.65 140.252.13.35 UGH 0 171 le0 127.0.0.1 127.0.0.1 UH 1 766 lo0 140.252.1.183 140.252.1.29 UH 0 0 emd0 140.252.13.32 140.252.13.33 U 8 99551 sl0 default 140.252.1.183 UG 1 2955 viv0 (A)le0 (B)lo0 (C)emd0 (D) sl0 答案:(D) 這題想請問一下,封包要傳給的位址140.252.12.45是要 看Destination還是看Gateway??為什麼? 麻煩知道的大大說明一下~感謝><... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.34.31.118
推
06/19 19:31, , 1F
第一題我是用排列組合~第一個一定放4第二個可能2or6
06/19 19:31, 1F
→
06/19 19:32, , 2F
考慮放2or6其中一個就好,另外一邊會一樣,已考慮2舉例
06/19 19:32, 2F
→
06/19 19:35, , 3F
2之後可能放6,1,3然後在繼續考慮放6以及放1和放3的可能
06/19 19:35, 3F
→
06/19 19:38, , 4F
然後記得*2(因為這裡只考慮放2,還要考慮放6)
06/19 19:38, 4F
推
06/19 19:52, , 5F
問題二看destination 換成2進位可以推出mask
06/19 19:52, 5F
推
06/19 19:55, , 6F
順便說問二其實連換成二進位都不需要
06/19 19:55, 6F
推
06/19 19:57, , 7F
根據題目說的，destination 是路由器介面
06/19 19:57, 7F
→
06/19 19:58, , 8F
我們可以假設那些位址都是network ID
06/19 19:58, 8F
→
06/19 19:59, , 9F
然後你要送到140.252.13.45的話 networkid 不可能是
06/19 19:59, 9F
→
06/19 20:00, , 10F
140.252.13.65 這組 因為這組比140.252.13.45 還後面
06/19 20:00, 10F
→
06/19 20:01, , 11F
127.0.0.1也不可能 那是測試用的IP位址
06/19 20:01, 11F
→
06/19 20:03, , 12F
所以只剩下140.252.1.183 140.252.13.32兩組
06/19 20:03, 12F
→
06/19 20:03, , 13F
這兩組用眼睛看都不用算你就會知道誰的prefix bits長
06/19 20:03, 13F
→
06/19 20:03, , 14F
最後驗算一下就可以
06/19 20:03, 14F
→
06/19 20:04, , 15F
另外gateway位址是某台機器的位址
06/19 20:04, 15F
→
06/19 20:05, , 16F
該一邊連接你的網路、一邊連接另外一個網路
06/19 20:05, 16F
→
06/19 20:06, , 17F
總之因為gateway 不是網路ID 位址，所以用他不準
06/19 20:06, 17F
→
06/19 20:07, , 18F
應該是這樣吧～
06/19 20:07, 18F
推
06/19 20:22, , 19F
第一題4不算,剩下的6個數字2一定要在1和3前,6一定要在5和7前
06/19 20:22, 19F
→
06/19 20:23, , 20F
的排列順序數目就是答案了，但我不確定怎麼可以直接算
06/19 20:23, 20F
→
06/19 20:24, , 21F
我是有列舉出來，好像是三種情況，最後乘以2就是答案了
06/19 20:24, 21F
→
06/19 20:27, , 22F
(1) 26____ (2) 2_6___ (3) 2__6__ 會長這三種情況吧
06/19 20:27, 22F
推
06/19 20:27, , 23F
以42開頭為例有 42136XX 4216XXX 42316XX 4236XX 426XXXX
06/19 20:27, 23F
→
06/19 20:28, , 24F
最後再乘以二 也就是46開頭 此題比較耗時間!!
06/19 20:28, 24F
→
06/19 20:29, , 25F
拍謝 4236應該是XXX少打一個
06/19 20:29, 25F
推
06/19 20:35, , 26F
第二題最快的方式就是直接轉換成二進位看哪個符合最長就是了
06/19 20:35, 26F
推
06/19 20:45, , 27F
第一題我在想...不知道這樣對不對...
06/19 20:45, 27F
→
06/19 20:46, , 28F
4C2+4C2+6C3+6C3+7C5-3C1-3C2-3C3=80這樣...？
06/19 20:46, 28F
推
06/19 21:21, , 29F
版上高手雲集~推解答
06/19 21:21, 29F
推
06/19 22:01, , 30F
推薦atoi解法,(1)4x3x2x1=24,(2)2x3x2x1=12,(3)2x1x2x1=4
06/19 22:01, 30F
→
06/19 22:01, , 31F
24+12+4=40, 40x2=80
06/19 22:01, 31F
推
06/19 22:08, , 32F
感謝樓上把我那方法詳解解出來，這題可能是稍微需要列舉一下
06/19 22:08, 32F
→
06/20 00:56, , 33F
感謝各位的詳細說明><.....
06/20 00:56, 33F
‣ 更多 mingrong2 的文章
文章代碼(AID): #1HmOTojX (Examination)