b. 解決死路

4. (20 分) 使用 linked list 完成以下 stack 程式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));// Your answer starts here// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// Your answer starts here// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}

5. (10 分) Find the Breadth-First-Search tree of the following graph. The starting vertex is a.

6. (15 分) Fibonacci numbers: Their recursive definitions are as follows:Fn=0 if n=0; Fn=1 if n=1; Fn=1 if n=2; Fn=2Fn-1+ Fn-2+ Fn-3 if n≥3.Design an O(lg n)-time algorithm to compute Fn.

7. (15分) Describe an O(nlog n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.8. (10分) Run Insertion Sort on the following array: (7,6,5,4,2,3,1) step by step.

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

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

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

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

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

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

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

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

104年 - [非官方正解]104 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113199