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

關務三等資料結構：96

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

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

公務人員、關務人員升官等薦任資料結構：96

高考三級資料結構：96

退除役軍人轉任公務人員三等資料結構：96

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

公路人員升資員級晉高員級資料結構：96

郵政人員升資員級晉高員級資訊處理資料結構：96

資訊技師高等資料結構(去除資料庫)：96

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

[九六年關務三等資料結構]

96年公務人員特種考試關務人員考試試題代號：50470 全一張

等別：三等考試

科別：資訊處理

科目：資料結構

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

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

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

一、假設我們要對一組訊息 AAAAABBCCCDDDDE 進行二進位數的編碼(Code)

(一)若每個字元編碼為相等長度，則此訊息進行編碼後，最少需多少位元？（10分）

(二)若每個字元編碼為可變長度，則此訊息進行編碼後，最少需多少位元？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、假設一個含有十個不相等鍵值 (Key) 的檔案，每個鍵都有對應使用頻率如下：

鍵 (Key)

使用頻率 (%)

K₁

K₂

K₃

K₄

K₅

K₆

K₇

K₈

K₉

K₁₀

(一)若使用循序搜尋法 (Sequential Search)，試問搜尋一個鍵值 (Key) 的平均比較次數 (Average Number of Comparisons) 為多少？（10分）

(二)若想有效減少平均比較次數，這些鍵值應重新安排 (Arrangement)，經過重新安排之後，試問其平均比較次數為多少？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、以下為前序追蹤 (Preorder Traversal)及後序追蹤 (Postorder Traversal) 的順序

前序追蹤順序：M, N, I, A, H, B, C, J, G, F, K, L, E, D, Y

後序追蹤順序：A, B, C, H, I, G, F, J, N, E, D, L, Y, K, M

(一)請畫出此二元樹。（10分）

(二)請寫出此二元樹的中序追蹤 (Inorder Traversal) 順序。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、費氏級數定義於下：

undefined

(一)試求算 F(5) 的值。（5分）

(二)計算 F(5) 的值需呼叫函數的次數。（5分）

(三)計算 F(5) 的值需加法運算的次數。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、下列為一個環狀串列 (Circular Queue) 中加入與刪除一個元素的演算法：

Procedure ADDQ(item,Q,n,front,rear)

rear←(rear+1) mod n

if front=rear then call QUEUE_FULL

Q(rear)←item

end ADDQ

Procedure DELETEQ(item,Q,n,front,rear)

if front=rear then call QUEUE_EMPTY

front←(front+1) mod n

item←Q(front)

end DELETEQ

(一)在演算法 ADDQ 中當 front = rear 時發生溢位 (Overflow)，實際上還有一個空間，請說明為何不使用呢？（5分）

(二)若欲使用此一空間，則 ADDQ 及 DELETEQ 應如何改寫，試寫出他們修改後的 ADDQ 及 DELETEQ 演算法。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年專利商標審查人員三等資料結構]

96年公務人員特種考試經濟部專利商標審查人員考試試題代號：30830 全一頁

等別：三等考試

類科：資訊工程

科目：資料結構（包括資料庫）

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

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

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

一、如下表所示，資料內容存放在陣列 (Array) Data 中，如果要資料按內容字母次序建立雙鏈串列 (Doubly linked list)，寫出兩標頭 (Header) Head_f, Head_b 與指標 (Pointer) 陣列 Link_f 與 Link_b 之內容。（請將下表繪製於試卷上作答，於本試題作答者，不予計分）（20分）

Index	Data	Link_f	Link_b
1	Eat
2	Date
3	Can
4	Hat
5	Fat
6	Kid
7	Man
8	Bob
9	Gate

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、(一)簡釋何謂二元搜尋樹 (Binary search tree)。

(二)如果依序將52, 20, 60, 30, 16, 55, 72, 36, 39, 66等數字加入成為二元搜尋樹，寫出最後所得的二元搜尋樹。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、以下列技術設計階乘次常式 (Subroutine)，以n 為輸入參數，回傳 n! 之值：（20分）

(一)遞迴 (Recursive) 技術。

(二)反覆 (Iterative) 技術。

備註：n! = n*(n-1)*(n-2)*...*2*1

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、寫出並說明 ANSI/SPARC 對資料庫所建構的三階結構 (Three levels of the architecture)。（20 分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、如果 G 代表一無向圖 (Undirected graph) 的定義：

V(G) = {1,2,3,4,5,6,7,8}

E(G) = {(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,5),(4,6),(5,5),(6,7),(7,8)}

其中 V(G) 為 G 之節點 (Vertices) 集合，E(G) 為邊線 (Edges) 集合。（20 分）

(一)指出該定義有一不合法的邊線並說明原因。

(二)剔除該不合法的邊線後，依節點編號次序編製，寫出該無向圖的鄰接矩陣（Adjacency matrix）。

(三)寫出其中任兩個不同的跨距樹 (Spanning tree)。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年關務人員升官等薦任資料結構]

96年公務人員、關務人員升官等考試試題代號：36160 全一張

70560

等別：薦任

類科：資訊處理（公務）、資訊處理（關務）

科目：資料結構

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

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

(二)本試題可以使用電子計算器。

一、二元搜尋法 (binary search) 是用來從排序好的資料陣列中尋找資料。假設 n 筆資料由小到大按照順序存在一維陣列 A 中，且每一筆資料長度一樣。

(一)請簡要描述二元搜尋法的原理。（5分）

(二)設 f (n) 為二元搜尋法的執行時間，請分析 f (n) 和 n 的關係。提示：設 n = 2^k，且每次搜尋的資料筆數為前次的一半。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、有一個一維陣列 (array) A，內含6個元素，分別為 A[1]、 ...、A[6]。每個元素含有兩個欄位：data 和 next。欄位data 用來存放整數資料，欄位 next 儲存索引 (index) 用來鏈結下筆資料或空位。若 next 的值為 -1 表示鏈結結束。所有存入的資料經由 next 欄位串在一起，所有空位亦經由 next 欄位串在一起。另外，有兩個變數 start 和 avail，分別表示第一筆資料和第一個空位的位置。每次一個整數要儲存時，便從 avail 中取出第一個空位，把整數放入，並且插入到資料串內適當的位置，而 avail 則記錄下一個空位的位置。當一筆資料被刪除時，其元素變成第一個空位，其後接原來的第一個空位，而資料相關位置不變。假設 A 陣列經過多次儲存和刪除後，其狀態如下所示：

undefined

此時，start = 4 表示第一筆資料存在 A[4] 中，下一筆在 A[1] 中，再下一筆在A[6]中。而 avail = 3 表示第一個可用的空位為 A[3]，下一個可用的空位為 A[5]，再下一個可用的空位為 A[2]。

(一)將一筆新的資料40 存入 A 中，其位置介於資料10和50之間。請畫出存入40 後的狀態。（5分）

(二)承上題(一)，將10從 A 中刪除，請畫出刪除後的狀態。（5分）

(三)承上題(二)，將60存入 A 中，使其成為第一筆資料，請畫出存入後的狀態。（5分）

(四)承上題(三)，請畫出將50刪除後的狀態。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、已知有一棵二元搜尋樹 (binary search tree) 如下圖所示：

undefined

(一)現有一數 X，其值大於 B 但小於 H，將 X 加入此樹，請畫出加入後的二元搜尋樹。（5分）

(二)承上題(一)，今欲將 A 刪除，請畫出刪除後的二元搜尋樹。注意：我們規定一個數被刪除後，會被其左子樹 (left subtree) 的最大數取代。（5分）

(三)承上題(二)，請寫出此二元樹的中序追蹤 (inorder traversal) 為何？（5分）

(四)承上題(三)，請寫出此二元樹的後序追蹤 (postorder traversal) 為何？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、一個一維陣列 A 的元素 A[1]、A[2]、 ...、A[n]，可視為一個含有 n 個節點 (node) 的完全二元樹 (complete binary tree)，每個元素為一個節點。根節點 (root) 為 A[1]，且對任何一個節點 A[k]，其子女 (children) 為 A[2k] 和A[2k+1]。

(一)假設有8個整數：95、55、70、90、30、65、80、85，依序存入 A[1]至 A[8] 中。利用父母－子女 (parents-children) 節點交換的方式，將此8 個整數所形成的完全二元樹轉化為一個最小堆積 (min-heap)，並列出A[1] 到 A[8] 的值。（15分）

(二)承上題(一)，將最小整數30 刪除，並將 A[8] 放入 A[1] 中，利用父母－子女節點交換的方式，將 A[1] 至 A[7] 調整成一個最小堆積，並列出A[1] 到 A[7] 的值。（5 分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、有7個數依序為70、250、180、100、20、190、200。

(一)請將上述資料建成一棵3 次的B-樹 (B-tree of order 3)。（15分）

(二)承上題 (一)，將70從此樹刪除，請畫出刪除後的B－樹。假設一個數被刪除後，會被其右子樹 (right subtree) 的最小數取代。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年高考三級資料結構]

96年公務人員高等考試三級考試試題代號：35450 全一張

類科：資訊處理

科目：資料結構

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

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

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

一、圖 (graph) 的表示法 (Graph Representation)

(一)以下面的無向圖 (undirected graph) 為例，說明圖的鄰接串列 (adjacency list) 表示法。（10分）

undefined

(二)以下面的有向圖 (directed graph) 為例，說明圖的鄰接矩陣 (adjacency matrix) 表示法。（5分）

undefined

(三)給一 n 個節點 (vertex) 的有向圖 G 的鄰接矩陣，請問計算圖 G 的一個節點的出分支度 (out degree) 的時間複雜度為何？（5分）

(四)給一 n 個節點 (vertex) 的有向圖 G 的鄰接矩陣，請簡述判斷圖 G 是否連通 (connected) 的演算法。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、霍夫曼碼 (Huffman code) 是一種依照字母出現的頻率決定編碼的不定長二進位編碼法 (variable-length binary code)。

(一)說明霍夫曼碼的編碼與解碼原理。（10分）

(二)假設字母集為 {甲、乙、丙、丁、戊、己}，個別字母出現頻率如下表。請填寫每個字母的霍夫曼碼。（15分）

字母	甲	乙	丙	丁	戊	己
出現頻率	45	13	12	16	9	5
霍夫曼碼

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、遞迴演算法 (recursive algorithm)

(一)令 A 為 N 個數的整數陣列 (Integer array)。請用虛擬碼 (Pseudo Code)描述求陣列 A 中最大值的遞迴演算法。（5分）

(二)令 A 為 N 個數的整數陣列 (Integer array)。假設 A 中的數字已經由小到大排列好。請用儘量接近程式語言的虛擬碼 (Pseudo Code) 描述搜尋整數 X 是否存在陣列 A 中的二元搜尋 (Binary Search) 的遞迴演算法(recursive algorithm)。請說明此一搜尋法的時間複雜度。（10分）

(三)請用儘量接近程式語言的虛擬碼 (pseudo code) 描述計算費氏數列(Fibonacci numbers) 第 N 項的遞迴演算法。請問該遞迴演算法的時間複雜度 (time complexity) 是否為多項式時間 (polynomial time) 複雜度？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、堆積排序 (Heap Sort)

(一)堆積排序將堆積樹 (heap tree) 用一個陣列 (array) A 儲存。陣列的指標(index) 從 1 到 N。請說明堆積樹的根 (root) 在陣列中的位置。請說明陣列 (array) A 第 i 個位置 A[i] 所儲存的堆積樹節點的左子節點 (left child)、右子節點 (right child)、以及父節點 (parent) 各自在陣列 A 中的位置。（5分）

(二)在 Max-堆積樹中，除了根節點 (root) 外，每一個節點所儲存的數小於或等於其父節點所儲存的數。假設陣列 A 儲存一個十個節點的 Max-堆積樹。陣列 A 中的數字從第一個位置到第 10 個位置所存數字依序為 16, 14, 10, 8, 7, 9, 3, 2, 4, 1。請畫出陣列 A 所儲存的堆積樹以及各節點所儲存的數。（5分）

(三)請以儘量接近程式語言虛擬碼描述如何將一個不符合 Max-堆積樹性質的陣列轉換成符合 Max-堆積樹性質的陣列。請分析你的演算法的時間複雜度。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年退除役軍人轉任公務人員三等資料結構]

96年特種考試退除役軍人轉任公務人員考試試題代號：80570 全一頁

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

一、假設我們要對一組訊息 AAAAABBCCCDDDDE 進行二進位數的編碼(Code)

(一)若每個字元編碼為相等長度，則此訊息進行編碼後，最少需多少位元？（10分）

(二)若每個字元編碼為可變長度，則此訊息進行編碼後，最少需多少位元？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、假設一個含有十個不相等鍵值 (Key) 的檔案，每個鍵都有對應使用頻率如下：

鍵 (Key)

使用頻率 (%)

K₁

K₂

K₃

K₄

K₅

K₆

K₇

K₈

K₉

K₁₀

(一)若使用循序搜尋法 (Sequential Search)，試問搜尋一個鍵值 (Key) 的平均比較次數 (Average Number of Comparisons) 為多少？（10分）

(二)若想有效減少平均比較次數，這些鍵值應重新安排 (Arrangement)，經過重新安排之後，試問其平均比較次數為多少？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、以下為前序追蹤 (Preorder Traversal) 及後序追蹤 (Postorder Traversal) 的順序前序追蹤順序：M, N, I, A, H, B, C, J, G, F, K, L, E, D, Y

後序追蹤順序：A, B, C, H, I, G, F, J, N, E, D, L, Y, K, M

(一)請畫出此二元樹。（10分）

(二)請寫出此二元樹的中序追蹤 (Inorder Traversal) 順序。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、費氏級數定義於下：

undefined

(一)試求算 F(5) 的值。（5分）

(二)計算 F(5) 的值需呼叫函數的次數。（5分）

(三)計算 F(5) 的值需加法運算的次數。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、下列為一個環狀串列 (Circular Queue) 中加入與刪除一個元素的演算法：

Procedure ADDQ(item, Q, n, front, rear)

rear←(rear+1) mod n

if front = rear then call QUEUE_FULL

Q(rear)←item

end ADDQ

Procedure DELETEQ(item, Q, n, front, rear)

if front = rear then call QUEUE_EMPTY

front←(front+1) mod n

item←Q(front)

end DELETEQ

(一)在演算法 ADDQ 中當 front = rear 時發生溢位 (Overflow)，實際上還有一個空間，請說明為何不使用呢？（5分）

(二)若欲使用此一空間，則 ADDQ 及 DELETEQ 應如何改寫，試寫出他們修改後的 ADDQ 及 DELETEQ 演算法。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年檢察事務官三等資料結構]

96年公務人員特種考試第二次司法人員考試試題代號：30630 全一張

等別：三等考試

類科：檢察事務官電子資訊組

科目：資料結構

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

※注意：(一)可以使用電子計算器。

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

一、分別用反覆合併排序法 (iterative merge sort) 和遞迴合併排序法 (recursive merge sort) 將下列數字由小至大排序，必須列出整個排序過程。（20分）

26, 5, 77, 1, 61, 11, 59, 15, 48, 19

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、對陣列 A = (5, 3, 17, 10, 84, 19, 6, 22, 9)，

(一)列出堆積化 (heapify) 後的陣列。（10分）

(二)接著列出加入20 後的陣列。（5分）

(三)再接著列出刪除最大值後的陣列。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、(一)依下圖建構以節點 (node) b 為根 (root) 的深度搜尋樹 (depth-first search tree)，掃描邊 (arc) 的順序是根據字母順序。（10分）

(二)根據建構的深度搜尋樹，列出下圖的邊那些是樹邊 (tree arc)、前向(forward arc)、後向邊 (backward arc)、交叉邊 (cross arc)。（10分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、請將下列二元樹 (binary tree) 以左前序 (left preorder)、右前序 (right preorder)、左後序 (left postorder)、右後序 (right postorder) 方式表示。（20分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、在下列之雙向鏈結串列 (doubly linked list) 的插入及刪除副程式中，依序填入空白位置，下圖為串列之示意圖。（20分）

undefined

list-insert(L, x)

{

next[x] ← head[L]

if head[L]≠NIL

then (1) ;

head[L] ← x

(2) ;

}

list-delete(L, x)

{

if prev[x]≠NIL

then (3) ;

else head[L] ← next[x]

if next[x]≠NIL

then (4) ;

}

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年公路人員升資員級晉高員級資料結構]

96年交通事業公路人員升資考試試題代號：10430、11630、41630 全一頁

級別：員級晉高員級

科別：資訊管理、資訊處理

科目：資料結構

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

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

(二)禁止使用電子計算器。

一、抽象資料型態 (Abstract Data Type；簡稱 ADT) 是利用資料結構來設計演算法的重要基礎，請定義下列資料結構的 ADT：（每小題5分，共20分）

(一) Heap（5分）

(二) Binary Tree（5分）

(三) 23 Tree（5分）

(四) Set（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、今有一存有 n 個整數的陣列 (array)，請設計一個遞迴演算法來找出這些整數的最大數和最小數。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、佇列 (Queue) 和堆疊 (Stack) 是重要的資料結構，請利用兩個堆疊來設計一個佇列 (Queue) 的 Enqueue( )和 Dequeue( ) 動作。並請分析你設計的 Enqueue( ) 和 Dequeue( ) 的時間複雜度。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、請設計一個遞迴演算法來計算下列平方和的值：

undefined

注意：你的演算法可用 SQ(n) 函數來做平方的計算。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、假設有一個二元搜尋樹 (Binary Search Tree；簡稱BST)，若 a 和 b 為此BST 所存的兩個節點值，且 a < b。請證明若將此 BST 用中序法 (inorder)印出節點值時，a 一定在 b 之前印出。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年郵政人員升資員級晉高員級資訊處理資料結構]

96年交通事業郵政人員升資考試試題代號：11160 全一頁

等別：員級晉高員級

科別：資訊處理

科目：資料結構

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

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

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

一、(一)試設計一遞迴演算法 (Recursive algorithm)，執行二分搜尋法 (Binary search)。這個程式呼叫方式為 Binary(a, x, left, right)，其中所有的資料均存放在 array a中，x 為被搜尋的資料，left 及 right 為 a 的第一個及最後一個資料所在 array a 的 index。（15分）

(二)分析此程式的執行時間複雜度。請以 Big O 表示。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、(一)將下列之 infix 表示式轉成 postfix 表示式。（10分）

A * B + C - D * E * B + C

(二)利用堆疊 (stack) 計算 (evaluate) 上述之 postfix 表示式。請將每一步驟之堆疊內容列出。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、給定一無向圖 (graph)，我們可以找到這圖的展開樹 (Spanning tree)。

(一)試設計一演算法，建構展開樹。（15分）

(二)試舉出一利用展開樹之實例。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、設計一演算法計算一個二元樹 (Binary tree) 的高度 (Height)。此演算法之複雜度需為 O( | V | )，| V | 為此樹結點 (node) 之個數。（25分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年資訊技師高等資料結構(去除資料庫)]

96年專門職業及技術人員高等考試建築師、技師、法醫師考試暨普通考試記帳士考試、96年第二次專門職業及技術人員高等暨普通考試消防設備人員考試、普通考試不動產經紀人考試試題

代號：01310 全一頁

等別：高等考試

類科：資訊技師

科目：資料結構（包括資料庫）

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

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

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

一、(一)計算 123！(即123×122×…×3×2×1) 數值最後有幾個0？（5分）

(二)執行下列函數 (圖一)，求 F(10) 之值為何？（10分）

Float F(int number)

{

if (number <=2)

return 1;

else

return(3*F(number-2) + 2*F(number-1)); }

圖一

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、某二維陣列 A，A(1, 7) 位址為1242，A(2, 3) 位址為1150，A(4, 1) 位址為1110：

(一) A 陣列係以何種方式存於記憶體內？（2分）

(二) A(5, 5) 位址為何？（2分）

(三) A 陣列中每一元素佔用位址大小為何？（2分）

(四) A 陣列共有幾行 (column)？（2分）

(五) A 陣列共有幾列 (row)？（2分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、某二元樹之後序 (postorder) 追蹤 (traversal) 為 DCFEBIJHGA；中序 (inorder) 追蹤為 CDBFEAIHJG：

(一)試畫出此二元樹。（5分）

(二)此二元樹之前序 (Preorder) 追蹤為何？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、(一)何謂 Hashing？（5分）

(二)使用上有何優點？（5分）

(三) Hashing 運算會遇到什麼問題？如何解決？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、關聯表為何需要正規化？關聯式資料庫第一正規化形式 (1NF)、第二正規化形式 (2NF)、第三正規化形式 (3NF)、第四正規化形式 (4NF) 定義為何？（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

六、(一)使用資料庫管理系統有何優點？（8分）

(二)選擇資料庫管理系統必須考慮那些成本？（7分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

七、(一)資料庫處理中所謂“交易 (transaction)”是何意思？（5分）

(二)如果以未控制的方式執行並行交易，可能發生那些問題？（5分）

(三)交易故障的原因可分為幾類？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[九六年地方特考三等資料結構]

96年特種考試地方政府公務人員考試試題代號：34050 全一張

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

一、(一)試寫出 bucket sort 的演算法，並說明在何種狀況下此排序法的平均時間複雜度 (average time complexity) 為線性時間 (linear time)。（10分）

(二)試寫出 counting sort 的演算法，並說明在何種狀況下此排序法的時間複雜度 (time complexity) 為線性時間。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、令一疊紙牌依序為 a₁, a₂, …, a_n。洗牌動作 shuffle(q), q < n，為將紙牌分成 a₁, a₂, …, a_q與 a_q+1, a_q+2, …, a_n 兩疊，再將兩疊紙牌逐張交錯放置成一疊為 a₁, a_q+1, a₂, a_q+2,…, a_q,a_2q, a_2q+1, a_2q+2, …, a_n 當 q ≤ n/2, a₁, a_q+1, a₂, a_q+2,…, a_n-q, a_n, a_n-q+1, a_n-q+2, …, a_q 當 q > n/2。用單向鏈結串列 (single-linked list) 來模擬此疊紙牌。試寫一段程式模擬洗牌動作 shuffle(q)。（20分）