109 年 國立中央警察大學資訊管理研究所《計算機概論》

本題主要考查物聯網 (Internet of Things, IoT) 的基本概念、架構與安全威脅。

核心觀念：物聯網是透過網路將各種實體物件連接起來，使其能夠收集、交換數據並進行互動的技術。其架構通常分為感知層、網路層和應用層，而安全是 IoT 發展的重要考量。

(一) 物聯網的五種應用舉例：
物聯網的應用非常廣泛，以下列舉五種常見的應用：

1. 智慧家居 (Smart Home)：透過連接家中的家電（如智慧燈泡、智慧門鎖、智慧音箱、恆溫器等），使用者可以遠端控制或自動化家居設備，提升生活便利性與舒適度。例如，設定離家模式後，所有燈光自動關閉，門鎖自動上鎖。
2. 智慧醫療 (Smart Healthcare)：可穿戴式裝置（如智慧手環、心率監測器）可以持續收集使用者的生理數據（如心率、睡眠品質、運動量），並將數據傳輸至醫療平台，供醫生遠端監測或進行初步診斷，實現預防性醫療與遠距照護。
3. 智慧交通 (Smart Transportation)：例如，透過安裝在道路或車輛上的感測器，收集交通流量、車輛位置等資訊，實現交通號誌的智慧調控，減少塞車；或提供即時停車位資訊、導航系統最佳路線規劃等。
4. 工業物聯網 (Industrial Internet of Things, IIoT)：在製造業中，感測器被用於監控生產線上的設備狀態、溫度、壓力等參數，以預測設備故障、優化生產流程、提高生產效率與產品質量。例如，預測性維護，在設備損壞前進行維修。
5. 智慧農業 (Smart Agriculture)：利用感測器監測土壤濕度、溫度、光照強度、養分含量等環境數據，並結合氣象預報，自動化控制灌溉系統、施肥系統，精準管理作物生長，提高產量並節省資源。
   【答案】(以上五種應用任選其四，並加以說明即可)

(二) 物聯網的架構三層說明：
物聯網的架構通常被劃分為三個主要層級，分別是感知層、網路層和應用層。

1. 感知層 (Perception Layer / Sensing Layer)：
   • 功能：這是物聯網最底層的架構，負責感知、識別和收集現實世界中的各種資訊。它包含各式各樣的感測器（Sensors）、致動器（Actuators）、條碼/QR Code 掃描器、RFID 標籤及讀取器等硬體設備。
   • 作用：感測器負責偵測環境中的物理參數（如溫度、濕度、光線、壓力、運動等）或識別物體（如條碼、RFID），並將這些類比訊號轉換為數位訊號。致動器則負責根據接收到的指令，對物理世界進行操作（如開關燈、調節溫度、移動機械臂）。
2. 網路層 (Network Layer / Transport Layer)：
   • 功能：這一層負責將感知層收集到的數據傳輸到應用層，並將應用層的指令傳遞到感知層。

本題主要考查圖論中的兩種基本搜尋演算法：廣度優先搜尋 (BFS) 和深度優先搜尋 (DFS)，以及它們在特定圖結構上的應用。

核心觀念：BFS 和 DFS 是用於遍歷或搜尋圖 (或樹) 中節點的兩種重要演算法。BFS 依層級由近至遠搜尋，DFS 則沿著一條路徑盡可能深入搜尋。

(一) BFS 與 DFS 演算法：

1. 廣度優先搜尋法 (Breadth First Search, BFS)

• 核心思想：BFS 從起始節點開始，先訪問所有與起始節點直接相鄰的節點（即同一層級的節點），然後再逐層向外擴展，依次訪問下一層級的所有節點。它利用一個佇列 (Queue) 來管理待訪問的節點。

• 演算法步驟：

  1. 初始化一個空的佇列 Q。
  2. 將起始節點 start_node 加入佇列 Q。
  3. 標記 start_node 為已訪問。
  4. 當佇列 Q 不為空時，執行以下步驟：
     a. 從佇列 Q 的前端取出一個節點 u (dequeue)。
     b. 處理節點 u（例如，將其加入 BFS 遍歷序列，或用於建立擴展樹）。
     c. 對於節點 u 的每一個未訪問過的鄰居節點 v：
     i. 標記 v 為已訪問。
     ii. 將 v 加入佇列 Q (enqueue)。
     iii.（若要建立 BFS 擴展樹，記錄 u 是 v 的父節點）。

• 時間複雜度：$O(V+E)$，其中 $V$ 是圖的節點數，$E$ 是圖的邊數。每個節點和每條邊都會被訪問常數次。

• 空間複雜度：$O(V)$，用於儲存佇列和標記已訪問的節點。

2. 深度優先搜尋法 (Depth First Search, DFS)

• 核心思想：DFS 從起始節點開始，沿著一條路徑盡可能深入地訪問節點，直到無法繼續深入為止，然後回溯到上一個節點，尋找另一條未訪問的路徑繼續深入。它通常利用遞迴 (Recursion) 或一個堆疊 (Stack) 來實現。

• 演算法步驟 (遞迴實現)：

  1. 定義一個遞迴函數 DFS(node, visited)：
     a. 標記 node 為已訪問。
     b. 處理節點 node（例如，將其加入 DFS 遍歷序列，或用於建立擴展樹）。
     c. 對於節點 node 的每一個未訪問過的鄰居節點 v：
     i. （若要建立 DFS 擴展樹，記錄 node 是 v 的父節點）。
     ii. 遞迴呼叫 DFS(v, visited)。

  2. 初始化一個標記所有節點為未訪問的陣列 visited。

  3. 對起始節點 start_node 呼叫 DFS(start_node, visited)。

• 演算法步驟 (迭代實現，使用堆疊)：

  1. 初始化一個空的堆疊 S。
  2. 將起始節點 start_node 推入堆疊 S。
  3. 當堆疊 S 不為空時，執行以下步驟：
     a. 從堆疊 S 的頂端彈出一個節點 u (pop)。
     b. 如果 u 尚未被訪問：
     i. 標記 u 為已訪問。
     ii. 處理節點 u。
     iii.（若要建立 DFS 擴展樹，記錄某個節點是 u 的父節點，這在迭代實現中較複雜，通常需要額外結構）。
     iv. 將 u 的每一個未訪問過的鄰居節點 v 推入堆疊 S (push)。注意鄰居的加入順序會影響遍歷結果。

• 時間複雜度：$O(V+E)$，與 BFS 相同。

• 空間複雜度：$O(V)$，用於儲存堆疊（或遞迴呼叫堆疊）和標記已訪問的節點。

【答案】(BFS 及 DFS 的演算法描述，包含核心思想、主要資料結構、步驟，以及時間/空間複雜度)

(二) BFS 與 DFS 擴展樹的產生：

給定的圖節點與連接關係：

• 1: {2, 4, 5}
• 2: {1, 3, 6}
• 3: {2, 7}
• 4: {1, 5, 8}
• 5: {1, 4, 6}
• 6: {2, 5, 7}
• 7: {3, 6, 8}
• 8: {4, 7}

起始節點為 1。

1. BFS 擴展樹 (BFS Spanning Tree)

BFS 演算法從起始節點開始，逐層訪問。我們需要記錄每個節點是從哪個節點訪問而來的，以構成樹。

• 初始化：

  • 佇列 Q = [1]
  • 已訪問 Visited = {1}
  • BFS 擴展樹邊集 Edges = {}

• 步驟：

  1. Dequeue 1。處理 1。
     • 1 的鄰居：2, 4, 5。
     • 將 2, 4, 5 加入佇列。Q = [2, 4, 5]。
     • 標記 2, 4, 5 為已訪問。Visited = {1, 2, 4, 5}。
     • 加入邊 (1, 2), (1, 4), (1, 5) 到 Edges。
  2. Dequeue 2。處理 2。
     • 2 的鄰居：1, 3, 6。1 已訪問。
     • 未訪問鄰居：3, 6。
     • 將 3, 6 加入佇列。Q = [4, 5, 3, 6]。
     • 標記 3, 6 為已訪問。Visited = {1, 2, 4, 5, 3, 6}。
     • 加入邊 (2, 3), (2, 6) 到 Edges。
  3. Dequeue 4。處理 4。
     • 4 的鄰居：1, 5, 8。1, 5 已訪問。
     • 未訪問鄰居：8。
     • 將 8 加入佇列。Q = [5, 3, 6, 8]。
     • 標記 8 為已訪問。Visited = {1, 2, 4, 5, 3, 6, 8}。
     • 加入邊 (4, 8) 到 Edges。
  4. Dequeue 5。處理 5。
     • 5 的鄰居：1, 4, 6。1, 4, 6 已訪問。
     • 無未訪問鄰居。Q = [3, 6, 8]。
  5. Dequeue 3。處理 3。
     • 3 的鄰居：2, 7。2 已訪問。
     • 未訪問鄰居：7。
     • 將 7 加入佇列。Q = [6, 8, 7]。
     • 標記 7 為已訪問。Visited = {1, 2, 4, 5, 3, 6, 8, 7}。
     • 加入邊 (3, 7) 到 Edges。
  6. Dequeue 6。處理 6。
     • 6 的鄰居：2, 5, 7。2, 5, 7 已訪問。
     • 無未訪問鄰居。Q = [8, 7]。
  7. Dequeue 8。處理 8。
     • 8 的鄰居：4, 7。4, 7 已訪問。
     • 無未訪問鄰居。Q = [7]。
  8. Dequeue 7。處理 7。
     • 7 的鄰居：3, 6, 8。3, 6, 8 已訪問。
     • 無未訪問鄰居。Q = []。
  9. 佇列為空，結束。

• BFS 擴展樹的邊：{(1, 2), (1, 4), (1, 5), (2, 3), (2, 6), (4, 8), (3, 7)}。

  • 節點 1 是根。
  • 節點 2 的父節點是 1。
  • 節點 4 的父節點是 1。
  • 節點 5 的父節點是 1。
  • 節點 3 的父節點是 2。
  • 節點 6 的父節點是 2。
  • 節點 8 的父節點是 4。
  • 節點 7 的父節點是 3。

2. DFS 擴展樹 (DFS Spanning Tree)

本題主要考查網路通訊模型 OSI 七層架構、通訊介面與通訊協定的概念，以及網路插槽 (Socket) 的定義與性質。

核心觀念：OSI 模型是網路通訊的理論框架，將複雜的通訊過程分層處理。介面是連接不同實體或層級的點，協定則是定義溝通規則的規範。Socket 是應用層與傳輸層之間溝通的端點。

(一) OSI 7-layer model 的七層架構及其功能：
OSI (Open Systems Interconnection) 模型是一個將網路通訊功能劃分為七個邏輯層次的理論模型，旨在促進不同廠商的系統之間的互連互通。

1. 第七層：應用層 (Application Layer)

   • 功能：提供應用程式與網路之間的介面，處理使用者感知的網路服務。它讓使用者能夠存取網路資源，例如檔案傳輸、電子郵件、網頁瀏覽等。
   • 代表協定：HTTP, FTP, SMTP, DNS, Telnet。

2. 第六層：表現層 (Presentation Layer)

   • 功能：負責數據的格式轉換、加密與解密、壓縮與解壓縮。它確保不同應用層之間能夠理解彼此傳送的數據格式。
   • 代表協定：SSL/TLS (用於加密), JPEG, ASCII。

3. 第五層：會議層 (Session Layer)

   • 功能：負責建立、管理和終止應用程式之間的通訊會話 (Session)。它處理對話的同步、管理傳輸流量，並確保兩端點之間的對話能夠持續進行。
   • 代表協定：NetBIOS, RPC。

4. 第四層：傳輸層 (Transport Layer)

   • 功能：提供端對端 (End-to-End) 的資料傳輸服務，負責將上層的數據分割成數據段 (Segments)，並進行可靠或不可靠的傳輸。它處理流量控制、錯誤控制和流程控制。
   • 代表協定：TCP (Transmission Control Protocol, 可靠傳輸), UDP (User Datagram Protocol, 不可靠但快速傳輸)。

5. 第三層：網路層 (Network Layer)

   • 功能：負責在不同網路之間進行數據的路由 (Routing) 和定址 (Addressing)。它決定數據封包 (Packets) 的最佳路徑，並處理邏輯位址（如 IP 位址）。
   • 代表協定：IP (Internet Protocol), ICMP (Internet Control Message Protocol), OSPF。

6. 第二層：資料鏈結層 (Data Link Layer)

   • 功能：負責在相鄰節點之間（同一網路內）進行可靠的數據傳輸。它處理實體位址（如 MAC 位址），進行錯誤偵測和糾正，並控制數據幀 (Frames) 的傳輸。
   • 代表協定：Ethernet, PPP (Point-to-Point Protocol), Wi-Fi (IEEE 802.11)。

7. 第一層：實體層 (Physical Layer)

   • 功能：定義了傳輸媒介的物理特性，如電壓、線纜標準、連接器類型。負責將數據比特流 (Bits) 轉換為電信號、光信號或無線電波，並在物理媒介上進行傳輸。
   • 代表標準：RS-232, Ethernet (實體部分), USB。

【答案】(七層名稱及其功能說明)

(二) 通訊介面 (Interface) 與通訊協定 (Protocol) 的主要差異：

本題主要考查程式語言的分類，特別是程序性語言與物件導向語言的概念，以及常見程式語言的分類。

核心觀念：程序性語言著重於「如何做」(How to do)，將程式分解為一系列的步驟和函數；物件導向語言著重於「誰來做」(Who does it)，將程式組織成具有狀態 (資料) 和行為 (方法) 的物件。

(一) 程序性語言與物件導向語言在撰寫程式觀念上的差異：