資訊處理 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 分）

給定一個可儲存7 筆資料的雜湊表（hash table）及下列雜湊函式（hash functions） Hash(key)的定義。 First(key) = key 的第一個字母在英文26 個字母的順序，即：'a' = 0, 'b' = 1, 'c' = 2, 'd' = 3。 Length(key) = key 的長度，例如Length('apple') = 5, Length('cat') = 3 等。 Hash(key) = First(key) + i * Length(key), i 的起始值為0，遇有碰撞時i = i + 1 後再重新計算Hash(key) 請將apricot, cat, angel, bath, boy, dog, cub, done 依序儲存進該雜湊表。（15 分） 請說明apricot, cat, angel, bath, boy, dog, cub, done 依序儲存進該雜湊表過程中 Hash(key)被計算的總次數。（5 分）

假設一個無向圖（undirected graph）的邊（edges）如下： S, T S, Z T, Y T, Z V, Y V, Z Y, Z 使用堆疊（stack），從S 開始，進行深度優先走訪（depth-first traversal），請寫出 走訪結果。（10 分） 使用佇列（queue），從S 開始，進行廣度優先走訪（breadth-first traversal），請寫 出走訪結果。（10 分）

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

給定如下含有9 個頂點（vertex）及19 個邊（edge）的圖，每個邊的權重（weight） 都不同。（每小題5 分，共15 分） 若以Kruskal’s 演算法產生最小生成樹（minimum spanning tree），請列出產生該生 成樹的過程中各個邊加入的順序（請以邊的權重列舉）。 若以Prim’s 演算法產生最小生成樹（minimum spanning tree），請列出產生該生成 樹的過程中各個邊加入的順序（請以邊的權重列舉）。 請畫出不同於Kruskal 或Prim 演算法所能產生的任一生成樹（spanning tree）。 （請接第二頁） 105年公務人員特種考試警察人員、一般警察人員 考試及105年特種考試交通事業鐵路人員考試試題 全三頁 第二頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 資訊處理 科 目： 資料結構

請將下列值2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫 出結果。作答時，請標示節點如下：例如節點2B 表示其值為2 的黑（Black）節 點，又如節點5R 表示其值為5 的紅（Red）節點。（10 分） 請畫出與上面小題相對應的2-3-4 樹（2-3-4 tree）。（10 分）

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

兩單位間有大量的訊息互傳需求，為了使訊息傳遞能更有效率，兩單位把可能傳遞訊 息所用到的重要字詞進行頻率分析，並據以建立了如下的霍夫曼碼樹。假設A, B, C, D, E 分別代表不同的字詞，請說明下列各小題敘述的正確性。 （每小題5 分，共25 分） 請說明在所有訊息中A 出現的頻率是否一定低於B 出現的頻率。 請說明在所有訊息中C 出現的頻率是否一定大於或等於A 出現的頻率。 請說明在所有訊息中D 出現的頻率是否一定大於A 出現的頻率。 請說明在所有訊息中D 出現的頻率是否一定大於或等於A, B, C 出現頻率的總和。 請說明在所有訊息中E 出現的頻率是否一定低於A, B, C 出現頻率的總和。

請對下面的樹，分別做前序（preOrder）、中序（inOrder）、後序（postOrder）及廣度 優先（breadth-first）四種走訪（traversals），請分別寫出結果。（20 分）

現有一網路公司想要分析某一網站使用者之使用行為，故想設計一資料結構以記錄 使用者存取網頁之順序，即，如使用者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 分）

給定下列依字母先後順序為依據的最大堆積樹（max heap）。（每小題5 分，共15 分） 請畫出將T 加入該最大堆積樹後的結果。 請畫出從所給定最大堆積樹捨去最大數（W）後的結果。 請列出以後序走訪（post-order traversal）方式走訪所給定最大堆積樹的順序。 （請接第三頁） 105年公務人員特種考試警察人員、一般警察人員 考試及105年特種考試交通事業鐵路人員考試試題 全三頁 第三頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 資訊處理 科 目： 資料結構 （請接背面）

依序插入2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分） 從上面小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並 請寫出此堆（min heap）的陣列內容。（10 分）

二項式係數（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 分）

下表第一行給定16 個需要被排序的英文字，第七行是將第一行16 個英文字被正確 排序後的順序。請分析第二行至第六行的排序順序是採用快速排序法（quick sort），希爾排序法（13-4-1 Shell sort），堆積排序法（heap sort），選擇排序法 （selection sort），或插入排序法（insertion sort），所排序第一行16 個英文字過程 的暫時結果。（每小題5 分，共25 分） 第一行 第二行第三行第四行第五行 第六行 第七行 that bye bye fruit fruit zoo bye work that fruit heaven good work fruit heaven good good manner heaven wish good thought heaven heaven that that thought heaven that fruit manner that bye think manner wish that that that that winner that wish manner that think manner wish that zoo that that thought that that that fruit that that wish zoo fruit that think think think wish think that think manner wish thought work wish manner thought that thought winner zoo wish that winner winner winner wish winner winner heaven wish bye wish zoo bye that bye wish that work work that thought that work good zoo wish good work good zoo 請說明第二行是採取那一種排序法之排序過程的暫時結果？ 請說明第三行是採取那一種排序法之排序過程的暫時結果？ 請說明第四行是採取那一種排序法之排序過程的暫時結果？ 請說明第五行是採取那一種排序法之排序過程的暫時結果？ 請說明第六行是採取那一種排序法之排序過程的暫時結果？

對下列程式片段，請用Big-O 符號（Big-O notation），分別估計最長執行時間（worst time）。注意：S 中沒有與 n 相關的迴圈（n-dependent loops）。（每小題5 分，共20 分） for (int i = 0; i * i < n; i++) S for (int i = 1; i < n+1; i*=2) S for (int i = 1; i < n+1; i*=2) for (int j = 0; j < n; j++) S k=1; for (int i=0; i<n; i++) {k*=3; for (int j=0; j<k; j++) S} ＋ － Ｙ Ｘ ／ ＊ Ｂ Ａ Ｚ