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

關務三等資料結構：94

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

高考三級資料結構：94

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

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

交通事業公路人員升資員級晉高員級資料結構：94

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

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

專門職業及技術人員檢覈資料結構：94

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

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

9 4年公務人員特種考試關務人員考試及

9 4年公務人員特種考試稅務人員考試試題代號：12430 全一頁

考試別：關務人員考試

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

一、假設三維陣列Ｘ[3:10, 4:15, 5:20] 的第一個元素在記憶體的位址是200。假設每個元素佔4個位元組 (bytes)，那麼當採用以行為主 (column-major) 時，X[5, 7, 10] 之位址為何？（20 分）

答：

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

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

二、(一)寫出累堆排序法 (Heap Sort) 的演算法。（10分）

(二)針對輸入數列 (53、26、41、18、35、10、55、45、9、21)，寫出排序過程。（10分）

答：

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

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

三、有一遞迴函數如下：

int f(int n)

{

if (n < 3)

return n;

else

return f(n-3) + f(n-2) + f(n-1);

}

(一)以 f(9) 叫用之，將傳回值多少？（5 分）

(二)令函數 g(n) 為計算f(n) 時需呼叫f(0) 的次數，試寫出 g(n) 的遞迴關係 (recurrence relation)。（10分）

(三)函數 g(9) 的值為何？（5分）

答：

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

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

四、假設編碼系統中有A、B、C、D、E、F 等符號，其出現機率依序為

0.43, 0.13, 0.12, 0.18, 0.08, 0.06，

請依據此畫出霍夫曼樹 (Huffman tree) 並設計一套霍夫曼碼 (Huffman code)，並依此所設計的霍夫曼碼將011000001000111010011 進行解碼。（20 分）

答：

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

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

五、如下圖以頂點0為啟始點，找出其深度優先展開樹 (Depth-first Spanning Tree)並計算出其成本 (cost)。（20分）

undefined

答：

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

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

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

38350

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

70550

等別：薦任升官等考試

科別：資訊工程、資訊處理（公務）、資訊處理（關務）

科目：資料結構

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

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

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

一、某函數 F 以遞迴的方式定義如下：

a , b 均為自然數

(1) F(a , b) = 0, 如果a＜ b

(2) F(a , b) = F(a－b , b)＋1, 如果a ≧ b

(一)試求 F(88 , 7) 的函數值？（5分）

(二)試說明 F(a , b) 函數的功能為何？（5分）

答：

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

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

二、已知某二元樹 (binary tree) 之後序 (postorder) 追蹤 (traversal) 為 F H I G D E B C A；中序 (inorder) 追蹤為 F D H G I B E A C；

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

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

答：

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

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

三、有一雜湊函數 (hashing function) H 表示如下：

(1) H(id) = id, 如果 id＜m

(2) H(id) = (id)³ mod m, 如果 id ≧m

其中 id 是紀錄的鍵值， m 是記憶區大小。

現有兩個紀錄，其紀錄的鍵值分別為15及30，又記憶區分為23個區域。

(一)試問上述兩個紀錄在記憶體的第幾個區域？是否有碰撞 (collision) 產生？（10分）

(二)試說明一般解決碰撞的方法為何？（10分）

答：

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

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

四、給予資料序列，依序為 25, 37, 52, 68, 16, 43, 9；

(一)試將上述資料建成二元搜尋樹 (binary searching tree)。（5分）

(二)利用所建二元搜尋樹將資料由大而小排序，請詳明方法。（10分）

(三)試將上述資料建成最大堆積樹 (max heap)。（5分）

(四)請逐步列出堆積排序 (heap sort) 每一次調整後的堆積 (heap)。（10分）

答：

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

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

五、有一加權圖形 (weighted graph) 如圖一所示，

(一)運用 Kruskal 方法，逐步畫出最小成本擴張樹 (minimum cost spanning tree)。（15分）

(二)並計算從 A 頂點到其他各頂點的最低成本。（5分）

undefined

答：

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

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

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

2005年高上高普特考‧高分解答‧正確詳實！

http://www.get.com.tw/goldensun

資訊

《資料結構》

一、依照圖(一)的二元樹 (Binary Tree)（每小題5分，共30分）

(一)寫出其後序追蹤 (Postorder Traversal)。

(二)寫出其中序追蹤 (Inorder Traversal)。

(三)寫出其前序追蹤 (Preorder Traversal)。

(四)請舉一例子說明後序追蹤的應用。

(五)請舉一例子說明中序追蹤的應用。

(六)請舉一例子說明前序追蹤的應用。

undefined

答：

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

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

二、在處理互斥集合的聯集和找尋元素時，我們常用樹狀圖來描述集合，例如 {1, 2, 3, 4, 5}、{6, 7}、{8}，我們將它表示如圖(二)：

(一)請利用 UNION 和 FIND 的技巧，畫出元素3所在的集合和元素6所在的集合聯集後所成的新圖形。（5分）

(二)請舉一例子說明 UNION 和 FIND 的應用。（10分）

undefined

答：

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

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

三、一數列 44, 56, 33, 23, 99, 20, 11, 17, 73, 98。

(一)畫出對應二元樹 (Binary Tree)。（5分）

(二)請將這二元樹轉換成堆集樹 (Heap Tree)。（10分）

(三)在使用堆集排序 (Heap Sort) 的前二個步驟後可輸出 99 和 98 兩數，請畫出在經過二個步驟後的堆集樹。（5分）

答：

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

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

四、如圖(三)：（每小題5分，共20分）

(一)請以 A 為起始點，畫出深度優先搜尋法 (Depth First Search) 的生成樹(Spanning Tree)。

(二)請以 A 為起始點，畫出廣度優先搜尋法 (Breadth First Search) 的生成樹 (Spanning Tree)。

(三)請舉一例子說明深度優先搜尋法的應用。

(四)請舉一例子說明廣度優先搜尋法的應用。

undefined

答：

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

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

五、(一)由圖(四)中的二元搜尋樹 (Binary Search Tree)，寫出我們要找到節點數字 363，所會經過其他節點。（5分）

(二)假如我們在某一個二元搜尋樹內有 1 到 999 的數字，並且要搜尋的數字是 363。下列那一個序列不可能是要檢驗節點的序列？（10分）

1. 2、252、401、398、330、344、397、363

2. 924、220、911、244、898、258、362、363

3. 925、202、911、240、912、245、363

4. 2、399、387、219、266、382、381、278、363

undefined

答：

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

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

[九四年身心障礙人員三等資料結構]

94年公務人員特種考試身心障礙人員考試試題代號：30730 全一張

等別：三等

類科：資訊

科目：資料結構

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

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

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

一、電腦硬體基本元件，例如：邏輯閘 (logic gate)，只能處理0 和1 的訊號；處理器 (processor) 只能處理整數 (integer)，或浮點數 (floating point)，等的運算；然而在現實世界裡，資料處理所面臨的是日期、工時、姓名、住址、電話號碼...等等。闡述資料結構在簡單的訊號和複雜的資料之間所扮演的角色，並說明資料結構和其它的系統軟體，例如：作業系統、程式語言、編譯器...等的關係。（20分）

答：

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

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

二、抽象資料型態 (abstract data type) 常被用來設計程式語言未直接提供的資料型態 (data type)。以堆疊 (stack) 為例，說明設計抽象資料型態的步驟，以及至少兩種實現 (implementation) 的方法。（20分）

答：

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

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

三、假設有n 個整數1, 2, . . . , n。開始時，每個整數自成一個集合，之後將對這些集合做一連串的運算，這些運算包含：

(a) u (x, y),

(b) f (z).

其中 u (x, y) 是指將 x 和 y 這兩個集合做聯集 (union)。每個集合都有一個名稱，開始時每個集合都只包含一個整數，就以這個集合所包含的整數當作這個集合的名稱。做完聯集之後，原來的兩個集合就消失，新的集合可用集合中的任何整數命名，唯命名之後，名稱不得改變。另一個運算 f (z) 是找出包含 z 這個整數的集合。（20分）

(一)令 n = 10，假設新集合的命名是以集合中最小的整數當作集合的名稱。寫出做完下列每個 u (x, y) 運算之後這些集合的內容，以及 f (z) 所得到的結果。將答案依照運算的先後次序列出，每個運算寫在一行。

u (1, 2), u (6, 7), f (2), u (3, 4), f (5), u (1, 6), f (2), u (8, 9), u (8, 1), f (9).

(二)設計適合這些運算的資料結構，使得執行α₁, α₂, . . . , α_m 一連串的運算，可以做到平均每個運算所需時間的上界為 c‧log n，其中 c 為一個常數。

答：

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

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

四、假設有個程式必須儲存前面 n 個質數，2, 3, 5, 7, 11 . . . , 但是 n 的大小無法預先得知，只知它會在程式執行中逐漸增大。為了方便起見，假設每個質數的大小可用一個整數來儲存。為了解決這個問題，程式可先用malloc 這個程序取得開始的記憶空間 (memory space)，當n 的值超過原先取得記憶空間的大小時，程式可再用malloc 取得更大的記憶空間，將原有的資料抄(copy) 到新取得的空間，最後再用free 這個程序來釋放原先的記憶空間。若一次便取得很大的記憶空間，則資料移動的成本會變少，但是可能浪費很多記憶空間。反之，若每次取得很少的記憶空間，則浪費的記憶空間可能減少，但是資料移動的成本就會變大。因此，每次取得記憶空間的大小，變得很重要。假設 n 的最後值可能介於1 和 m 之間的任一值，其中 m 為系統可取得的最大記憶體空間。設計一個好的策略，來決定每次取得記憶空間的大小，使得資料移動的成本與浪費的記憶空間之間取得平衡。以移動一個整數當作一個單位的成本，儲存一個整數所需的空間為一個單位，用n 當作參數，在最差的形況下 (worst case) 估計你的策略所需要的資料移動成本與所浪費的空間。你的策略必須使移動成本和空間的浪費的上界在n 的常數倍之內。（20分）

答：

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

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

五、令 G = (V, E, w) 為一權重圖 (weighted graph)，其中 V 是G 的點集合(vertex set)，E 是 G 的邊集合 (edge set)，w：E |→R⁺ 為邊的權重函數。給定X Í E, E [X] 是指以邊的部分集合 X 所產生的子圖 (induced subgraph)。在 G 中找出最小展延樹 (minimum spanning tree) T = G [E_t] 可用下列的方法：（20分）

(a) 將圖的邊 (edge) 按照其權重排列：e1, e2, . . . , em

(b) 令E_t =φ

(d) 執行下列指令直至 G [Et] 為 G 的展延樹 (spanning tree) 為止：

1.若 G [E_t U {e_i}] 沒有迴圈 (cycle) 則令 E_t = E_t U {e_i}.

2.i = i＋1.

若不用其它的資料結構來協助，不管用任何方法，測試 G [E_t U {e_i}] 是否包含迴圈總要檢驗過 E_t U {e_i} 中所有的邊。設計一個好的資料結構，使得整個演算法的時間複雜度可以降低，並比較用了這些資料結構前後，這個演算法的時間複雜度的變化情形。時間複雜度是以最差的情況下 (worst case) 做分析的基準，並以圖的點數 n 和邊數 m 當參數來表示。

答：

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

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

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

94年公務人員特種考試司法人員考試試題代號：30730 全一張

等別：三等考試

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

科目：資料結構

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

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

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

一、考慮某種資源分享系統，該資源可供使用時間共分成n 個時段，依序編號為 1, 2,…, n。每一個使用者只能使用一個時段，而每一個時段最多只能有一個使用者。使用者要預約一個時段時，需透過指令 reserve(i, j) 來完成，這裡i ≤ j 代表使用者希望使用時段的範圍。若這個範圍的時段都已經被預約了，這指令會回傳0 代表預約失敗，反之若這個範圍有空的時段，這指令會回傳一介於i, j 間的整數 k，代表使用者將可以使用時段 k。

一個簡單的作法為用一個一維陣列 a[1.. n] 來表示預約的狀況，a[i] = 1 代表時段i已經被預約，a[i] = 0 代表時段i 未被預約。實做指令 reserve(i, j)時，只需一一檢查 a[i] 到 a[j] 是否有值為0 即可。因此這個指令的執行時間為 O(j - i)，在最差的狀況下這指令的執行時間可高達 O(n)。事實上有在最差狀況下執行時間為 O(log n) 或更好的作法。

請(一)設計一個能表示整個預約狀況的資料結構，與(二)寫出一實做 reserve(i, j) 的演算法，使得在最差情況下reserve(i, j) 的執行時間為 O(log n) 或更好。（20分）

答：

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

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

二、二元搜尋樹 (binary search tree) 是一種基本的資料結構，在實做上有時需將兩個二元搜尋樹T₁, T₂ 合併成一個新的二元搜尋樹。一個單純的作法是：先建一個新的且為空的二元搜尋樹T，然後將 T₁, T₂ 裡的數字一個一個依任意次序拿出，再插入 (insert) 到T 裡面。這個作法的缺點是，在最差的情況下，運算時間會高達 O(n²)，其中n 為T 的大小。實際上有一個運算時間為 O(n) 的作法：

(一)請描述一個線性時間的作法，可以將一個二元搜尋樹裡的數字依小到大的次序排出來，並放在一個一維陣列上。（5分）

(二)利用(一)的特性，請設計出一個線性時間的演算法將 T₁, T₂ 裡的數字依小到大的次序排出來，並放在一個一維陣列上。（5分）

(三)給n 個已經排好的數，請設計出一個線性時間的演算法建構出以這 n 個數為鍵值 (key) 的二元搜尋樹，同時我們要求這個樹的高度必須為 O(log n)。（10分）

答：

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

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

三、一個監測器 (sensor) 可看成是一台計算機，只是其中央處理器速度比一般計算機慢，且記憶體也較小。有一監測器每隔一段時間需從外界讀入一個監測值，一段時間下來總共讀入 n 個數值，而這監測器的任務為記住這 n 個數裡面最小的 k 個，一般來講 k 遠小於 n。現在監測器的記憶體剛好只能放k 個數值，外加一個暫存器存放剛從外界讀入的監測值。同時由於監測器的處理速度不快，根據估計，若在監測器讀取兩個監測值的間隔時間內，處理器需做 k/2 次以上的比較，那麼監測器可能會錯失一個監測值，長期下來會造成紀錄結果不正確。這裡我們假設 k ≥100。請設計出一個可行的作法，可以讓這個監測器正確的完成其任務。（20分）

答：

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

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

四、假設有一個數學運算式 (expression) 裡面每一個運算元 (operand) 都是一個正整數，而運算子 (operator) 只有加法與乘法兩種。請就以下每一數學運算式的格式限制，寫出一段程式算出這個數學運算式的值。（20分）

(一)數學運算式為前序表示 (prefix expression)

(二)數學運算式為後序表示 (postfix expression)

這裡你可以假設已經有一個前處理程式 get-next-token( ) 可以運用，其規格為：

回傳值為正整數，表示 get-next-token( ) 讀到一個運算元，其大小即為回傳值。

回傳值為0，表示 get-next-token( ) 讀到運算式的結尾。

回傳值為-1，表示 get-next-token( ) 讀到加號。

回傳值為-2，表示 get-next-token( ) 讀到乘號。

答：

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

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

五、一個軟體系統內的程式，常需檢查其輸入資料格式是否正確，以確保後續處理不出問題。現有一組輸入資料放在一個陣列p[1.. n] 上代表一棵有根樹(rooted tree)，其中 n 為節點數，且節點編號為 1, 2, …, n。若 p[i] 存的值為 j，表示節點 i 的父節點為 j。若節點 i 為根節點則 p[i] 存的值為 i。請寫出一個線性時間的演算法檢查這陣列是否表示一棵有根樹。（20分）

答：

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

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

[九四年交通事業公路人員升資員級晉高員級資料結構]

94年交通事業鐵路人員、公路人員升資考試試題代號：40430 全一張

41730

級別：員級晉高員級

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

科目：資料結構

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

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

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

一、用一維陣列 A[1.. k×52] 表示由 k 副相同的撲克牌組成的一疊撲克牌。試寫一段程式將這疊撲克牌排序，其順序為 A <2<3< …< 10 <J <Q <K，當大小相同時則 §<¨<©<ª，並分析其時間複雜度 (time complexity)。（20分）

答：

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

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

二、有三個堆疊 A，B，C，其中堆疊A 已有資料 4,3,2,1 由大到小排列，堆疊B 與 C 是空的(如下圖)。堆疊的運算為：

(一) Push(V, X)：將變數 V 中的資料加入堆疊 X，其中 X 為A，B，C。

(二) Pop(V, X)：取出堆疊 X 中的資料放到變數 V，其中 X 為A，B，C。

1.寫出一序列的堆疊運算將堆疊A 的資料保持原有順序搬移到堆疊B。（5分）

2.設定在資料搬移過程中，堆疊 A，B，C 的資料都保持由大到小排列。寫出一序列的堆疊運算將堆疊A 的資料保持原有順序搬移到堆疊B。（5分）

3.如堆疊 A 中有 n 筆資料 n, n-1, n-2, …, 1 由大到小排列，寫一遞迴程式將堆疊 A 中的資料保持原有順序搬動到堆疊 B，且資料搬移過程中，堆疊 A，B，C 的資料都保持由大到小排列。（10分）

1
2
3
4
A	B	C

答：

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

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

三、可合併堆積 (mergable heap) 是一種抽象的資料結構，支援五個資料結構運算：

(一) Make-Heap：造一個空的可合併堆積。

(二) Insert：插入一新鍵值到可合併堆積。

(三) Minimum：報告可合併堆積中的最小鍵值。

(四) Extract-Min：將可合併堆積中的最小鍵值從堆積中移除。

(五) Union：將兩個可合併堆積合成一個可合併堆積。

試用有序串列 (sorted linked list) 來實作一個可合併堆積。請敘明你所知達成各個運算最有效率的演算法並分析其最差情形的時間複雜度 (worst-case time complexity)。（20分）

答：

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

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

四、有一網路圖如下，邊上的值為邊的長度。

(一)試用 Prim 演算法由端點 a 出發找出其最小生成樹 (minimum spanning tree)。（請寫出演算過程）（10分）

(二)試用 Kruskal 演算法找出其最小生成樹。（請寫出演算過程）（10分）

undefined

答：

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

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

五、將下列十二個鍵值：

15, 3, 5, 17, 10, 8, 6, 2, 14, 16, 18, 9

依序插入一空的 B-tree 中，此 B-tree 中的節點至少含一個鍵值，至多含三個鍵值。（20分）

答：

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

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

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

38350

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

70550

等別：薦任升官等考試

科別：資訊工程、資訊處理（公務）、資訊處理（關務）

科目：資料結構

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

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

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

一、某函數 F 以遞迴的方式定義如下：

a , b 均為自然數

(1) F(a , b) = 0, 如果a＜ b

(2) F(a , b) = F(a－b , b)＋1, 如果a ≧ b

(一)試求 F(88 , 7) 的函數值？（5分）

(二)試說明 F(a , b) 函數的功能為何？（5分）

答：

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

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

二、已知某二元樹 (binary tree) 之後序 (postorder) 追蹤 (traversal) 為 F H I G D E B C A；中序 (inorder) 追蹤為 F D H G I B E A C；

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

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

答：

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

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

三、有一雜湊函數 (hashing function) H 表示如下：

(1) H(id) = id, 如果 id＜m

(2) H(id) = (id)³ mod m, 如果 id ≧m

其中 id 是紀錄的鍵值， m 是記憶區大小。

現有兩個紀錄，其紀錄的鍵值分別為15及30，又記憶區分為23個區域。

(一)試問上述兩個紀錄在記憶體的第幾個區域？是否有碰撞 (collision) 產生？（10分）

(二)試說明一般解決碰撞的方法為何？（10分）

答：

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

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

四、給予資料序列，依序為 25, 37, 52, 68, 16, 43, 9；

(一)試將上述資料建成二元搜尋樹 (binary searching tree)。（5分）

(二)利用所建二元搜尋樹將資料由大而小排序，請詳明方法。（10分）

(三)試將上述資料建成最大堆積樹 (max heap)。（5分）

(四)請逐步列出堆積排序 (heap sort) 每一次調整後的堆積 (heap)。（10分）

答：

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

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

五、有一加權圖形 (weighted graph) 如圖一所示，

(一)運用 Kruskal 方法，逐步畫出最小成本擴張樹 (minimum cost spanning tree)。（15分）

(二)並計算從 A 頂點到其他各頂點的最低成本。（5分）

undefined

答：

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

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

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

高等考試建築師、技師考試暨普通考試

94年專門職業及技術人員考試試題代號：01310 全一張

不動產經紀人、地政士、記帳士

等別：高等考試

類科：資訊技師

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

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

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

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

一、霍夫曼碼 (Huffman code) 是常用的資料壓縮方法，請用以下的訊息：

“ANGELA_AND_AN_ANGEL”描述如何構建出該訊息的霍夫曼碼並說明你所用演算法的時間複雜度 (Time complexity)。（註：空格 ‘_’ 亦需計算在內）（10分）

答：

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

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

二、請以陣列設計一大小 (Size) 為10 的環狀佇列 (Circular queue)，以虛擬碼(Pseudo code) 或任一程式語言說明其佇列填滿 (Full) 與清空 (Empty) 的條件及如何加入 (Add) 與刪除 (Delete) 資料之運算 (Operation)。（10分）

答：

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

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

三、請為以下資料構建一二元搜尋樹 (Binary search tree)。（10分）

資料輸入順序依序為：60, 31, 22, 86, 79, 40, 30, 11, 69, 50

答：

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

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

四、(一)請以相鄰矩陣 (Adjacency matrix) 表示右邊圖形 (Graph)。（4分）

(二)說明以 Dijkstra 演算法求由起點v₀ 到所有其他點的最短路徑 (Shortest path)

undefined

的過程與結果。（6分）

答：

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

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

五、試以下列資料說明疊堆排序法 (Heap sort) 的排序過程。（10分）

未排序前之順序：（6, 4, 3, 9, 2, 1, 8, 7, 5）

答：

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

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

六、資料庫中有三個關連式表格 A, B, C 分別如下：

undefined

(一)寫出以下關連代數 (Relational algebra) 的計算結果。（5分）

πA1,B#,C1(σA3=”gov”(A) C)

（∩: Union, ∪: Intersection, -: Difference, σ: Select, π: Project, ⋈: Join, ×: Cartesian product）

(二)將以上(一)的關聯代數以 SQL 改寫表示。（5分）

(三)寫出以下 SQL 的執行結果。（5分）

SELECT A.A1, A.A3, B.B1, C.C1

FROM A,B,C

WHERE A.A2 > 35 AND A.A# = C.A# AND B.B# =C.B# ;

(四)將以上(三)的 SQL 改寫成關聯代數方式表示。（5分）

答：

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

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

七、一資訊系統分析後的功能相依圖 (Functional dependency graph) 如下所示：

其中 A，C 為鍵值 (Key)。

(一)請建立只符合第二正規化格式 (2NF) 的表格，並標示每一表格的鍵值。（5分）

undefined

(二)請建立符合第三正規化格式 (3NF) 的表格，並標示每一表格的鍵值。（5分）

答：

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

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

八、在時間 t0 時A = 10，B= 5，考慮以下兩筆交易 (Transaction) T1 與 T2 的同作 (Concurrency) 狀況：

時間

read(A)

read (B)

B = A + B

write(B)

read(B)

read (A)

A = B – A

write(A)

請指出以上的排程 (Schedule) 是否滿足循序性 (Serializability)？並說明原因。（10分）

答：

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

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

九、試舉例說明資料倉儲 (Data warehouse) 中多維度資料模型 (Multidimensional data model) 常用的星狀綱要 (Star schema) 與雪花狀綱要 (Snowflake schema)。（10分）

答：

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

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

[九四年專門職業及技術人員檢覈資料結構]

94年第二次專門職業及技術人員檢覈筆試試題代號：31610 全一頁

類科：資訊技師

科目：資料結構

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

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

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

一、有一棵二元樹 (binary tree) 如下：

請畫出每個節點 (node) 之左右兒子 (children) 都對調 (swap) 之二元樹。（20分）

undefined

答：

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

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

二、利用 quick sort 將下列資料由小到大排序。請寫出以最左邊的資料為基準值(pivot) 時，執行 quick sort 第一個 pass 後的資料順序：5, 6, 3, 4, 1, 2, 8, 7。（20分）

答：

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

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

三、考慮某一無向圖 (undirected graph) 如下，邊 (edge) 上的數字代表成本：

請畫出用 Kruskal 方法所產生的最小成本擴張樹 (minimum-cost spanning tree)。（20分）

undefined

答：

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

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

四、用陣列 (array) 來表示有下列資料的最大堆積 (maximum heap)：8, 5, 6, 3, 4, 1, 2（20分）

(一)請畫出此 maximum heap 圖。

(二)請畫出加入 (insert) 資料7後之 maximum heap 圖。

【提示：均為完整二元樹 (complete binary tree)】

答：

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

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

五、假設雜湊表 (hash table) 有7個桶子 (bucket)，每個桶子只能存放一筆資料，雜湊函數 (hash function) h定義為：

h(i) = i mod 7

使用線性探測 (linear probing) 來解決碰撞 (collision) 問題。

假設一開始雜湊表是空的，依序加入 (insert) 下列7筆資料：

32, 2, 56, 7, 19, 25, 26

請畫出雜湊表最後之內容。（20分）

答：

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

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

[九四年之一地方特考三等資料結構]

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

等別：三等考試

科別：資訊

科目：資料結構

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

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

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

一、請解釋下列名詞：（20分）

(一) B-Tree

(二) Circular queue

(三) Infix expression

答：

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

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

二、請簡述 insertion sort，heap sort，merge sort，及 quick sort 的原理，有那些因素可以影響應使用何種 sort 的決定？請比較這幾種 sorting 的效能並舉例說明其運作方式。（20分）

答：

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

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

三、何謂 Huffman codes？如何決定其 expected decoding time？其與 minimum weighted external path length 有何關連？請寫出 Huffman algorithm 以找出具有 minimum weighted external path length 的 binary tree 並決定其computing time。（20分）