(4) 倘台電公司所訂購之機器全毀，非因與B船碰撞所致，而係A船船長未經台電公司之同意，擅自將該機器裝載於甲板上，則台電公司得否向甲公司請求損害賠償?(9分)

一、(10%) Use Huffman's algorithm to construct an optimal binary prefix code for the letters in the following table.Letter : A D I M N Y ZFrequency: 12 7 18 10 9 5 2

二、(15%) Let G=(V,E) be the following graph. Use Floyd-Warshall algorithm to find the 5 × 5 matrix of shortest-path lengths δ(i, j) for all i, j∈V.

三、(15%) You are required to compute the binomial coefficient $$Ck^n = \frac{n!}{k!(n-k)!}$$. When n or k is not small, we cannot compute $$Ck^n$$ directly from the definition because n! or k! is very large. Please design an algorithm to compute $$C_k^n$$ in time O(nk) without computing n! or k! directly.

四、(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}

113年 - 113 國營臺灣鐵路股份有限公司_從業人員甄試_第 9 階-事務員-法務：商事法概要#119033

109年 - 109 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#92892

108年 - 108 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#97332

108年 - 108 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#96824

107年 - 107 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法 #79120

106年 - 106 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#71720

102年 - 102 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#33790

101年 - 101 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#96863

100年 - 100 經濟部所屬事業機構_新進職員甄試_國貿：2.商事法#35258

97年 - 97 經濟部所屬事業機構_新進職員甄試試題_法務：商事法#31013