114年 - 114 地方政府公務特種考試_三等_統計：資料處理#134709

一、在資訊安全中，雜湊函數（Hash Function）與數位簽章（Digital Signature） 常被用來確保資料的正確與完整。請敘述兩者的功能，並說明雜湊函數的主要特性及數位簽章的運作過程。 （25 分）

⑴將下列運算式由中序式（Infix）轉換為前序式（Prefix） ：
(A-B)*(C+D)/F

⑵根據下列二元樹，寫出其後序（Postfix）走訪結果：

⑶依序將數字 12, 8, 20, 4, 15, 7, 3, 10 插入一個空的最小堆積樹，畫出最後的堆積樹。

⑷承上題，刪除最小數字 3 後的最小堆積樹，畫出其最後結果。

三、正規化是為資料表的優化，而資料庫正規化有一些規則，每條規則都稱為「正規形式」 （Normal Form） ，請說明各階段正規化的規則（包含第一 正規化、第二正規化、第三正規化和 BCNF 等） 。（25 分）

四、請依照下列程式碼，當執行函數呼叫 Test(3)時，最後輸出結果為何？並請寫出詳細過程。（25 分）
String Test(int n) {
String s = n + Test(n - 1) + n + Test(n - 2);
if (n ＜= 0) return "";
return s;
}