高考申論題
112年
[資訊處理] 資料結構
第 三 題
三、在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元），當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查詢複雜度，已成為電腦網路的重要課題。
| IP位元0 | IP位元1 | IP位元2 | IP位元3 | IP位元4 | IP位元5 | IP位元6 | IP位元7 | 裝置 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | A |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | B |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | C |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | D |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | E |
| … | … | … | … | … | … | … | … | … |
試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維持在常數8（也就是IP位址位元數）。（25分）
| IP位元0 | IP位元1 | IP位元2 | IP位元3 | IP位元4 | IP位元5 | IP位元6 | IP位元7 | 裝置 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | A |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | B |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | C |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | D |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | E |
| … | … | … | … | … | … | … | … | … |
試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維持在常數8（也就是IP位址位元數）。（25分）
📝 此題為申論題
思路引導 VIP
本題為獨立題。看到「字串/位元序列查詢」且要求「最壞情況複雜度等於字串長度常數」，應立刻聯想到字典樹 (Trie，或稱 Prefix Tree)。 因為 IP 只有 0 和 1 兩個值，所以具體來說是一個二元字典樹 (Binary Trie)。
🤖
AI 詳解
AI 專屬家教
【考點分析】 本題考查字串/位元序列檢索效率最佳化的資料結構設計，主要測驗對「字典樹 (Trie) / 字首樹 (Prefix Tree)」原理與應用的掌握。 【理論依據】
▼ 還有更多解析內容