阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 105年 - 105年關務特考三等資料結構#51526
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 分)