資訊處理 93 年資料結構考古題

試說明要列印二分樹時應用何種追索程序？並請將其程序之演算法寫出。（15 分）

假設元素n 之個數分別為10、20、100、200、1000 與1000000 時，請比較順序搜尋與 二分搜尋的效率，請繪圖並以計量算式說明之。（20 分）

雜碰函數（Hash Function）基本技術之一的乘法雜碰函數為：若已知一個實數θ，則能 建立一個如下的乘法雜碰函數h（z）。先求算（z θ mod 1），亦即z θ的小數點部分， 再乘以表格大小之整數m，並取積數的最小整數值，即：h（z）=［m（z θ mod 1）］ ，使之滿足0≦h（z）＜m。試說明乘法雜碰函數應避免之病態為何？請舉例說明之。 （25 分）

如下圖之樹，將依虛線順序搜尋，搜尋時向上（D）、向下（U）次序依序記下，且於 序列結束時增加一額外的U，並將該序列視為一個二分樹之節點的先序串列。請重建 一個以D 與U 為節點的二分樹。（20 分）

請寫一程式將一串列之指標（Pointer）鏈結反轉。（20 分） 亦即例如將 A B C NIL A NIL B C 變為