:::
資料處理概要4033-001
一、網路通信中,須採用通信協定(communication protocol)。請說明為什麼要有通信協定及通信協定的定義。

◎【擬答】:

通訊協定(Communications Protocol),是不同電腦上相同階層間的通訊協議,指電腦通訊或網路裝置的共同語言,一般都 指電腦通訊的通訊協定,如:TCP/IP、NetBEUI、DHCP、FTP 等,運用通訊協定以確保傳信雙方能夠溝通無間。

二、欲拜訪一顆樹諸節點,有深度優先(depth-first search)和廣度優先(breadth-first search)二種方式。請說明二 者拜訪順序的差異,並說明實作上最適合這二種拜訪方式的資料結構。

◎【擬答】:

(一)深度優先搜尋演算法(Depth-First-Search, DFS)是一種用於遍歷或搜索樹或圖的演算法。沿著樹的深度遍歷樹的節 點,儘可能深的搜索樹的分支。當節點 v 的所在邊都己被探尋過,搜索將回溯到發現節點 v 的那條邊的起始節點。這一 過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點,則選擇其中一個作為源節點並重複 以上過程,整個進程反覆進行直到所有節點都被訪問為止。在實作上會運用堆疊(Stack)來儲存搜索過的節點。

(二)廣度優先搜尋演算法(Breadth-First-Search, BFS),是一種圖形搜索演算法。簡單的說,BFS 是從根節點開始,沿著 樹的寬度遍歷樹的節點。如果所有節點均被訪問,則演算法中止。在實作上會運用佇列(Queue)來儲存搜索過的節點。