105年資料結構分年題庫－國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

關務三等資料結構：105

身心障礙人員三等資料結構：無

鐵路特考高員三級資料結構：105

高考三級資料結構：105

檢察事務官三等資料結構：無

專利商標審查人員三等資料結構：無

關務人員升官等薦任資料結構：無

資訊技師高等資料結構與資料庫及資料探勘：105

地方特考三等資料結構：105

[一○五年關務三等資料結構]

105年公務人員特種考試關務人員考試、

105年公務人員特種考試身心障礙人員考試及代號：10560 全一張

105年國軍上校以上軍官轉任公務人員考試試題

考試別：關務人員考試

等別：三等考試

類科：資料處理

科目：資料結構

考試時間：2小時座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、臭皮匠排序 (Stooge sort) 是一種遞迴 (recursive) 排序法，其演算法如下：

1.如果當前集合 (current set) 最後一個元素值小於第一個元素值，則交換這兩個元素值。

2.如果當前集合 (current set) 元素數量大於等於3時：

(1)使用臭皮匠排序前2/3的元素。

(2)使用臭皮匠排序後2/3的元素。

(3)再次使用臭皮匠排序前2/3的元素。

3.否則結束程序，返回呼叫程序。

(一)請以任何具遞迴呼叫語法之程式語言寫出臭皮匠排序之函式。（10分）

(二)請根據上述演算法將下列資料進行排序：6 8 7 1 2 4 3 9 5。請寫出前五次函式呼叫後之結果。（10分）

(三)若以陣列表達欲排序之元素集合，請比較臭皮匠排序、插入排序 (insertion sort)、以及堆積排序 (heap sort) 之最差狀況 (worse case) 時間複雜度。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、(一)請解釋何謂引線二元樹 (threaded binary tree) 及其優點為何。（10分）

(二)若要以鏈結串列 (linked list) 來表達引線二元樹，試設計一適當之節點結構。（5分）

(三)請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點 (header node) 與無頭端節點之引線二元樹。（10分）

undefined

(四)請寫出在引線二元樹中以線性時間（即時間複雜度為O(n)）進行中序尋訪的演算法。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、若欲於下列樹狀結構中，搜尋節點 X 之位置，試分析深度優先 (depth-first)搜尋與廣度優先 (breadth-first) 搜尋之搜尋時間。請由根節點 (root node) 開始進行節點值比較之次數來表達。令根節點之深度 (depth) 為1。（每小題5分，共15分）

(一)X 為深度為 D 之偏斜 (skewed) 二元樹之葉節點 (leaf node)。

(二)X 為深度為 D 之完美 (perfect) 二元樹之最右邊之葉節點。

(三)X 為深度為 D 之完美 k 元 (k-ary) 樹之最左邊之葉節點。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○五年鐵路特考高員三級資料結構]

105年公務人員特種考試警察人員、一般警察人員

考試及105年特種考試交通事業鐵路人員考試試題代號：71070 全三頁

考試別：鐵路人員考試

等別：高員三級考試

類科別：資訊處理

科目：資料結構

考試時間：2小時座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、給定一個可儲存7筆資料的雜湊表 (hash table) 及下列雜湊函式 (hash functions) H_ash(key) 的定義。

First(key) = key 的第一個字母在英文26個字母的順序，即：’a’ = 0, ‘b’ = 1, ‘c’ = 2, ‘d’ = 3。

Length(key) = key 的長度，例如 Length(‘apple’) = 5, Length(‘cat’) = 3 等。

H_ash(key) = First(key) + i*Length(key),

i 的起始值為0，遇有碰撞時 i = i+1 後再重新計算 H_ash(key)

(一)請將 apricot, cat, angel, bath, boy, dog, cub, done 依序儲存進該雜湊表。（15分）

(二)請說明apricot, cat, angel, bath, boy, dog, cub, done 依序儲存進該雜湊表過程中 H_ash(key) 被計算的總次數。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、給定如下含有9個頂點 (vertex) 及19 個邊 (edge) 的圖，每個邊的權重(weight) 都不同。（每小題5分，共15分）

(一)若以 Kruskal’s 演算法產生最小生成樹 (minimum spanning tree)，請列出產生該生成樹的過程中各個邊加入的順序 (請以邊的權重列舉)。

(二)若以 Prim’s 演算法產生最小生成樹 (minimum spanning tree)，請列出產生該生成樹的過程中各個邊加入的順序 (請以邊的權重列舉)。

(三)請畫出不同於 Kruskal 或 Prim 演算法所能產生的任一生成樹(spanning tree)。

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、兩單位間有大量的訊息互傳需求，為了使訊息傳遞能更有效率，兩單位把可能傳遞訊息所用到的重要字詞進行頻率分析，並據以建立了如下的霍夫曼碼樹。假設 A, B, C, D, E 分別代表不同的字詞，請說明下列各小題敘述的正確性。（每小題 5分，共25分）

(一)請說明在所有訊息中 A 出現的頻率是否一定低於 B 出現的頻率。

(二)請說明在所有訊息中 C 出現的頻率是否一定大於或等於A 出現的頻率。

(三)請說明在所有訊息中 D 出現的頻率是否一定大於 A 出現的頻率。

(四)請說明在所有訊息中 D 出現的頻率是否一定大於或等於 A, B, C 出現頻率的總和。

(五)請說明在所有訊息中 E 出現的頻率是否一定低於 A, B, C 出現頻率的總和。

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、給定下列依字母先後順序為依據的最大堆積樹 (max heap)。（每小題5分，共15分）

(一)請畫出將 T 加入該最大堆積樹後的結果。

(二)請畫出從所給定最大堆積樹捨去最大數 (W) 後的結果。

(三)請列出以後序走訪 (post-order traversal) 方式走訪所給定最大堆積樹的順序。

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、下表第一行給定16個需要被排序的英文字，第七行是將第一行16個英文字被正確排序後的順序。請分析第二行至第六行的排序順序是採用1.快速排序法 (quick sort)，2.希爾排序法 (13-4-1 Shell sort)，3.堆積排序法 (heap sort)，4.選擇排序法 (selection sort)，或5.插入排序法 (insertion sort)，所排序第一行16個英文字過程的暫時結果。（每小題5分，共25分）

undefined

(一)請說明第二行是採取那一種排序法之排序過程的暫時結果？

(二)請說明第三行是採取那一種排序法之排序過程的暫時結果？

(三)請說明第四行是採取那一種排序法之排序過程的暫時結果？

(四)請說明第五行是採取那一種排序法之排序過程的暫時結果？

(五)請說明第六行是採取那一種排序法之排序過程的暫時結果？

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○五年高考三級資料結構]

105年公務人員高等考試三級考試試題代號：26650 全一頁

類科：資訊處理

科目：資料結構

考試時間：2小時座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、假設一個無向圖 (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分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、(一)請將下列值 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分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、(一)依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆 (min heap)，請畫圖顯示此堆 (min heap) 的樹狀結構，並請寫出此堆 (min heap) 的陣列內容。（10分）

(二)從上面(一)小題的結果刪除兩個元素，請畫圖顯示此堆 (min heap) 的樹狀結構，並請寫出此堆 (min heap) 的陣列內容。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、對下列程式片段，請用 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}

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○五年資訊技師高等資料結構與資料庫及資料探勘]

105年專門職業及技術人員高等考試建築師、

技師、第二次食品技師考試暨普通代號：01310 全三頁

考試不動產經紀人、記帳士考試試題

等別：高等考試

類科：資訊技師

科目：資料結構與資料庫及資料探勘

考試時間：2小時座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、Fibonacci 數列的遞迴 (recursive) 定義如下：

undefined

(一)請用 C 或 Java 程式語言以1.遞迴 (recursive) 和2.迴圈 (iterative) 方法寫出求 F_n 的函式 (function) Fib(n)。（10分）

(二)請各別分析你所寫出1.遞迴 (recursive) 和2.迴圈 (iterative) 演算法的時間複雜度，並以 Big-O 方式表示。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、圖形 (graph) 的實際表達方法通常可以使用1.相鄰矩陣 (adjacency matrix)、2.相鄰串列 (adjacency list) 等資料結構。以下為一有向圖 (directed graph) G = (V, E)：

undefined

(一)請以 C 或 Java 程式語言寫出1.相鄰矩陣 (adjacency matrix) 和2.相鄰串列 (adjacency list) 的宣告以有效表達有向圖 G 的資料結構；並繪出相對使用以上資料結構表達有向圖 G 的矩陣與串列結果示意圖。（10分）

(二)Floyd-Warshall’s algorithm 是找尋圖形中所有端點 (node) 對端點最短路徑 (all-pairs shortest path) 的方法，請選擇一種資料結構，以有向圖 G 為例，繪圖說明用此一演算法求解過程中每一回合 (run) 的計算結果。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、對資料庫系統的永久儲存結構而言，通常必須能夠隨著檔案紀錄的增多，進而動態的新增儲存區塊 (block)，例如：B-tree 樹狀檔案資料結構，即可隨著資料量變大而增加葉節點區塊 (leaf node block) 或增加樹的高度來因應。傳統的雜湊 (hashing) 方法為靜態雜湊 (static hashing) 結構，雖然有快速搜尋資料的優點，但是無法有效率的擴充儲存區塊；為改善靜態雜湊的缺點，動態雜湊 (dynamic hashing) 結構則能夠同時達成快速搜尋資料和動態擴充儲存區塊的功能。假設每一儲存區塊最多可以儲存3筆紀錄資料，試設計一動態雜湊資料結構與相對應的新增函數（Insert(key)），用以下的鍵值(key) 新增順序為例：

1, 3, 5, 7, 2, 4, 6, 8, 10, 9, 11, 21

說明你所設計的動態雜湊結構方法。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、一個跨國量販公司資料庫系統的部分相關關聯式表格名稱、欄位屬性名稱和資料如下：（每小題5分，共15分）

undefined

(一)請指出每一個表格最合理的主鍵 (primary key) 欄位集合與外鍵 (foreign key)。

(二) YU01 分公司在今天售出產品編號 A13011 的4件貨品，請以 SQL 語法寫出新增此筆售貨紀錄到 SALE 表格中的功能。

(三)以 SQL 語法寫出查詢 (query)：亞洲 ‘Asia’ 商店所賣出產品名稱為 ‘k-phoneS’ 的總數量。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、承續第四題，量販公司的高層決策者希望能夠從系統的每日交易運作資料庫(operational transaction database) 中，建立線上分析處理 (on-line analytical processing, OLAP) 系統。因此，首先必須由 PRODUCT、SALE、COMPANY、STATE 等資料表中轉換構建資料倉儲 (data warehouse)。假設所要分析的主要目標資料項包括：‘售貨的金額’ (NUM*VALUE) 和‘數量’ (NUM)；分析的維度 (dimension) 包括有：‘售出日期’、’地區’和‘產品’等3個維度，並且各個分析維度又可進一步分成以下概念階層 (concept hierarchy) 所組成的分析層次：

售出日期：年 (year) > 季 (quarter) > 月 (month) > 日 (day)

地區：洲別 (area) > 國別 (country) > 城市 (city)

產品：產品類別 (class) > 產品編號 (product)

請應用資料倉儲模型 (data warehouse model) 為此 OLAP 系統設計資料倉儲綱要 (schema)，並回答下列問題：

(一)採用的綱要模型為何？請說明原因。（5分）

(二)請繪出所設計的綱要，包含事實表格 (fact table)、維度表格 (dimension table)，以及相對的參考屬性 (referential attribute)。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

六、某營運單位的資料庫系統經系統分析、進一步設計後，得到實體-關係模型(E-R model) 圖結果如下。其中屬性 (attribute) 名稱下有底線者為各實體(entity) 的主鍵，實體C 中的屬性彼此另有以下的功能相依 (functional dependency) 存在：C3→C4，C3→C2。

undefined

(一)將以上實體-關係模型轉成符合第二正規化格式 (second normal form) 的關聯式表格綱要 (relational schema)。（10分）

(二)將本題(一)中的關聯式表格綱要轉成符合第三正規化格式 (third normal form) 的關聯式表格綱要。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○五年地方特考三等資料結構]

105年特種考試地方政府公務人員考試試題代號：34080 全一頁

等別：三等考試

類科：資訊處理

科目：資料結構

考試時間：2小時座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、請回答下列問題：

(一)畫出 AVL 平衡二元樹，其中序 (inorder) 拜訪為1、2、3、4、5任三種。（24分）

(二)請問共有多少種 AVL 平衡二元樹，其中序拜訪為1、2、3、4、5？（6 分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、分別給定矩陣 A、B、C 與 D 的大小為2×4、4×3、3×5 和5×1：（每小題5分，共15分）

(一)共有幾種加括號的方法？

(二)例如 (AB)(CD)，共需多少次乘法？

(三)求出三者乘積之最有效的方式為何？

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、試針對下列無向網路圖形 (Undirected Network Graph)

N(V,E,C),V={1,2,3,4,5,6},N={(1,2,6),(1,5,19),(1,6,21),(2,3,5),(2,4,16),(2,5,11), (3,4,10),(4,5,8),(4,6,9),(5,6,7)}，成本 C(1,2)=6, C(1,5)=19...等，求最小成本擴張樹 (minimal cost spanning tree) 的最小成本。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、有一浮點數三維陣列 (three dimensional array) float A [6][7][10]；假設sizeof(float) = 4：

(一)請問此陣列共佔多少位元組？（10分）

(二)若A[0][0][0] 在記憶體中的位址為 03C4₁₆，則元素 A[5][2][9] 的位址為何？（15分）