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

臭皮匠排序（Stooge sort）是一種遞迴（recursive）排序法，其演算法如下： 如果當前集合（current set）最後一個元素值小於第一個元素值，則交換這兩個元 素值。 如果當前集合（current set）元素數量大於等於3 時： ⑴使用臭皮匠排序前2/3 的元素。 ⑵使用臭皮匠排序後2/3 的元素。 ⑶再次使用臭皮匠排序前2/3 的元素。 否則結束程序，返回呼叫程序。 ㈠請以任何具遞迴呼叫語法之程式語言寫出臭皮匠排序之函式。（10 分） ㈡請根據上述演算法將下列資料進行排序：6 8 7 1 2 4 3 9 5。請寫出前五次函式呼叫 後之結果。（10 分） ㈢若以陣列表達欲排序之元素集合，請比較臭皮匠排序、插入排序（insertion sort）、 以及堆積排序（heap sort）之最差狀況（worse case）時間複雜度。（5 分）

㈠請解釋何謂引線二元樹（threaded binary tree）及其優點為何。（10 分） ㈡若要以鏈結串列（linked list）來表達引線二元樹，試設計一適當之節點結構。 （5 分） ㈢請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點（header node）與無 頭端節點之引線二元樹。（10 分） ㈣請寫出在引線二元樹中以線性時間（即時間複雜度為O(n)）進行中序尋訪的演算 法。（10 分） A B C D E F 105年公務人員特種考試關務人員考試、 105年公務人員特種考試身心障礙人員考試及 105年國軍上校以上軍官轉任公務人員考試試題 考試別： 關務人員考試 等 別： 三等考試 類 科： 資料處理 科 目： 資料結構

若欲於下列樹狀結構中，搜尋節點X 之位置，試分析深度優先（depth-first）搜尋與 廣度優先（breadth-first）搜尋之搜尋時間。請由根節點（root node）開始進行節點值 比較之次數來表達。令根節點之深度（depth）為1。（每小題5 分，共15 分） ㈠X 為深度為D 之偏斜（skewed）二元樹之葉節點（leaf node）。 ㈡X 為深度為D 之完美（perfect）二元樹之最右邊之葉節點。 ㈢X 為深度為D 之完美k 元（k-ary）樹之最左邊之葉節點。

現有一網路公司想要分析某一網站使用者之使用行為，故想設計一資料結構以記錄 使用者存取網頁之順序，即，如使用者U 存取A 網頁後，點選其中之連結存取B 網 頁，再點選其中之連結存取C 網頁，則其存取順序為A Æ B Æ C。此資料結構應能 記錄該存取順序與其相關資料，如網址與存取時間等。 ㈠請分別說明如何使用陣列（array）與鏈結串列（linked list）來記錄上述之網頁存 取順序，並分析兩者之優劣。（10 分） ㈡請寫一程式（不限程式語言）來分析使用者存取某一網頁後，接下來最有可能存 取那一個網頁。假設網頁之存取紀錄檔欄位格式如下： Date, Page1, Page2, Page3,... 代表使用者在Date 此日期依序存取了Page1、Page2、Page3 等網頁。範例紀 錄如下： 2016/03/01, a.htm, b.htm, c.htm 2016/03/02, a.htm, c.htm, e.htm, f.htm 2016/03/03, c.htm, a.htm, b.htm, e.htm 此程式必須能讀取紀錄檔並使用鏈結串列來記錄網頁存取順序紀錄。當使用者輸 入某一網頁（例如a.htm）時，此程式應傳回該網頁最有可能之後續網頁。以上 述範例紀錄而言，a.htm 之後續網頁最有可能者應為b.htm，因其在a.htm 後 出現之機率最高。（15 分）

二項式係數（Binomial Coefficient）的計算公式如下： ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − + ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − = − = ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ 1 1 1 )! (! ! m n m n m n m n m n ⎩ ⎨ ⎧ − − + − = = = otherwise ;)1 ,1 ( Bino ) ,1 ( Bino or 0 if ,1 ) , ( Bino m n m n n m m m n ㈠求Bino(5,3)的值？（5 分） ㈡求Bino(5,3)時，共呼叫Bino 此函數多少次？（5 分） ㈢當n, m N ∈ 且n≥m≥0 求Bino(n, m)時，共呼叫Bino 函數T(n, m)次，求T(n, m) =？ （10 分）