105年 - 105年關務特考三等資料結構#51526

科目：公職◆資料結構 | 年份：105年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

【已刪除】

⑴請以任何具遞迴呼叫語法之程式語言寫出臭皮匠排序之函式。（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 分）

⑴X 為深度為 D 之偏斜（skewed）二元樹之葉節點（leaf node）。

⑵X 為深度為 D 之完美（perfect）二元樹之最右邊之葉節點。

⑶X 為深度為 D 之完美 k 元（k-ary）樹之最左邊之葉節點。

⑴請分別說明如何使用陣列（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 分）