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

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

費氏數值的定義為：00 =f,11 =f，且當1>i時，21−−+=iiifff。 分別編寫遞式函數（recursive function）（10 分）路式函數（iterative function）（10 分）來計算if 。

提出一個程序（procedure）對任意n 個數a1,a2,…, an 執行quicksort，並評估此程序分 別在最佳情況（best case）與最壞情況（worst case）之時間複雜度（time complexity）。 （25 分）

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

說明))(()(ngOnf=，))(()(ngnfΩ=和))(()(ngnfΘ=的意義。若4)(1+= nnf，22)(nnf=‚在什麼條件下)(2 nf會比較大？（10 分）依據二、題的定義，下列敘述何者為真？何者為偽？（10 分）)(23nnΘ=+)( 241022 nnnΘ=++)1(23Θ≠+n)( 2622 nnnΘ=+×)( 24102 nnnΘ=++三、何謂堆疊（stack）？何謂儲列（queue）？計算機中為何需要這兩種資料結構？試著從指令集和程式設計觀點來討論它。（10 分）從實際生活中‚列舉和堆疊與儲列有關的事務（至少五種以上）。（10 分） 四、利用左子-右弟（left-child right sibling）表示法將圖一轉化為二元樹（binary tree）。（10 分）依中序法（inorder），後序法（postorder）和先序法（preorder）分別來尋訪圖一的樹和利用左子-右弟（left-child right sibling）表示法轉化後的相對二元樹，並輸出其尋訪次序。（10 分） 五、假設有n 筆紀錄，設計一累堆排序法（heap sort）將其鍵值由小排到大並依圖二說明其執行結果。（10 分）分析累堆排序法的複雜度。（10 分）ABCDEFGIHJLMK圖一 526271 6111 圖二圖一圖二

提出一個程序將二個長度分別為n 與m 的有序序列（ordered list），A＝（a1,a2,…, an） 與B＝（b1, b2,…, bm），合併（merge）成一個長度為n＋m 的有序序列C＝（c1, c2,…, cn+m）。（25 分）

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

提出一個程序決定是否一個給定的單向連結序列（singly linked list）L 包含一個數x。 若否，請將x 加到L 的尾端。（25 分）

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

提出一個遞迴程序（recursive procedure）依照 inorder 的順序搜尋（traverse）一個二 元樹（binary tree）T。（25 分）

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