資訊處理 93 年資料結構考古題（共 5 題）
資料來源：考選部歷屆試題｜法律人 LawPlayer 整理
https://lawplayer.com/exam/information-processing/93-data-structures

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

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

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

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

第 5 題
請寫一程式將一串列之指標（Pointer）鏈結反轉。（20 分）
亦即例如將

A
B
C
NIL
A    NIL
B
C
變為

題目為考試當年公告版本，實務標準請以現行規範為準。