7. Use Kruskal and Prim algorithms to find the minimum spanning tree step by step of the following graph. (20%)

Please write the recursive formula. (5%)

Given str1 = INTENTION and str2 = EXECUTION, use the above recursive formula to calculation an edit distance. (5%)

9. Step by step to build the Huffman Code tree and list Huffman codes for all characters as the following alphabets and their frequencies: [A:5, B:12, C:33, D:19, E:40, F:41]. (10%)

(a) How many words begin with R and end with T?

(b) How many words begin with A or end with B?

(c) How many words begin with A or R or end with T or B?

2. (20%) Consider the following graph. It has 20 vertices each with degree 3. Answer the questions. Is it a planar graph? Does it have an Euler circuit? Does it have an Euler path? Does it have a Hamilton circuit? Does it have a Hamilton path? Prove all your answers.

3. (15%) Boolean function \( f(x, y, z, w) = -x \vee (x \wedge y \wedge z \wedge w) \vee (x \wedge y \wedge z \wedge -w) \). First, find the truth table of function \( f \). Second, simplify the expression of \( f \) to minimize the number of AND, OR, NOT operations. Third, draw out the combinatorial circuit corresponding to your simplified expression. Finally, transform and redraw your combinatorial circuit to contain NAND gates only.

4. (15%) Let \( \mathbf{R} \) denote the set of real numbers. Show that \( \mathbf{R} \), together with the usual addition and scalar multiplication of real numbers, is a vector space.

(a) Show that the mapping \( L \) is a linear transformation.

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