四、(10%) Run Merge sort on the following array: (27,10,12,20,25,13,15,22) step by step.

(A)使用 quick sort 排序數列 60 80 45 2 36 98 11 47 52 89 75 63 7。並且說明每次移動數字時，所使用的條件和基準。

(B)使用 binary search 在排序好的數列尋找數字，比如 36，並說明為何能達到 O(log N)的速度，N 是數列的數字個數。

(A)將此 inorder statement : A(B+C)+EF-H/I 轉為 postorder，並畫出它的二元樹。

(B)設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。

3. (8%)使用 linked list 實作 stack，運用以下 C 語言程式：typedef struct node { int value; node *next;}void push (node **top, int new_value) { // assume top is not nullnode new_node = (node ) malloc (sizeof (node));// (A) 實作以下敘述// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// (B) 實作以下敘述// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}

4. (10%) 使用 queue 實作 level order traversal 轉換，運用以下 C 語言程式：void level_order (tree *root) { //assume root is not nullnode front, rear;//實作以下敘述// visit tree nodes based on level order by using queue// use queue by front, rear, enqueue(&rear, root), root =dequeue(&front)// print the values of tree nodes// describe the ending condition}

5. (16%) 使用 stack 實作 老鼠走過言問題 (Maze path search)，運用 C 語言程式：void path(){ // assume int maze30 and offsets move[8] has been set in main function// typedef struct {int v; int h;} offsets;int i, row, col, nextrow, nextcol, dir, found = 0, top =0, mark30;typedef struct { int row; int col; int dir;} elementelement position, stack[100];mark1 = 1; stack[0].row = 1; stack[0].col = 1; stack[0].dir = 0;//實作以下敘述// Use stack to get current row, col, dir// Use dir to calculate nextrow, nextcol// Use nextrow, nextcol to check this move (1) arrive exit, or// (2) become a legal move; add this move into the stack, or// (3) check other dir}

1.1 假設 AP 的 WAN 孔與 Modem 的 LAN A 孔透過網路線相連，請根據上表繪製出網路拓樣 (Topology)，並在各網路節點上標示出如上表的「代號」。各節點連接至 Modem 與 AP 時，請於節點與線的交會處旁標註使用哪一網孔 (A、B、C、D、WAN、E、F、G、H)，有線網路使用實線連接，無線網路使用虛線連接。(10%)

1.2 承 1.1 所述，假設 NAS 可透過 ONIVIF 以及 RTSP 兩協定與 Camera 進行連接，可將影像直接備份於 NAS 內。現於 NAS 的網頁設定畫面中指定 Camera 的 IPv4 位置為 192.168.1.105，但連接不上；透過 ssh 從 NAS 使用 ping 指令測試 192.168.1.105 會顯示封包 100% 遺失，從 NB 使用 ping 指令測試 192.168.1.105 卻顯示 0% 遺失。請嘗試說明可能的原因以及解法。(原因 5%、解法 5%)

1.3 承 1.1 所述，若想將網路架構改為單一 DHCP 同時派送有線及無線的 IPv4 位置，且所有設備仍需維持上表中的 IPv4 位置並正常連網，請嘗試說明可能的解法與原因。(解法 5%、原因 5%)

115年 - 115 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147260

114年 - 114 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147250

113年 - 113 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147281

112年 - 112 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147280

111年 - 111 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147272

110年 - 110 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147276

110年 - [非官方正解]110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108

110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147273

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850