國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

關務三等資料結構：98

高考三級資料結構：98

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

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

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

資訊技師高等資料結構：98

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

 

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

98年公務人員特種考試基層警察人員考試、98年公務人員特種考試稅務人員考試、98年特種考試退除役軍人轉任公務人員考試、98年公務人員特種考試海岸巡防人員考試、98年公務人員特種考試關務人員考試及98年國軍上校以上軍官轉任公務人員考試試題

代號：63370 全一頁

等    別：三等關務人員考試

類(科)別：資訊處理

科    目：資料結構

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

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

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

 

一、有 N 份資料，每份資料皆以兩個大寫英文字母標記 (例如 AK、TA 等等)。請設計一 O(N) 時間的演算法，將此組資料依標記的字典順序排序，並請說明此演算法所需使用的空間。（20分）

答：

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

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

 

二、圖形 (graph) G 有12個節點 (node)，分別用數字 0, 1, 2, 3, 6, 7, 8, 9, 12, 13, 14, 15標記。標記為 a, b 的兩個節點間有邊線 (edge)，若且唯若 a =a₁a₂a₃a₄, b = b₁b₂b₃b₄ 的四位元二進位表示法恰有一個位元不相同。例如1 = 0001, 3 = 0011, 9 = 1001，則標記為3的節點與標記為1的節點間有邊線，與標記為9的節點間沒有邊線。

(一)請分別用鄰接矩陣 (adjacency matrix) 與鄰接串列 (adjacency list) 的方式表示圖形 G。（10分）

(二)請在標記小的節點先搜尋的規則下，產生以節點0為起始節點的廣度優先搜尋擴張樹 (breadth-first search spanning tree) 與深度優先搜尋擴張樹(depth-first search spanning tree)。（10分）

答：

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

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

 

三、令 N 為2的 m 次方，a 為任意正整數。

(一)請寫一使用 O(log N) 次乘法運算的遞迴 (recursive) 程式計算 a 的 N次方。（10分）

(二)請寫一使用 O(log N) 次乘法運算的疊代 (iterative) 程式計算 a 的 N次方。（10分）

答：

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

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

 

四、今有一採用開放位址 (open addressing) 方式儲存鍵值，大小為14的雜湊表(hash table)，其雜湊函數為 H_i(k) = h₁(k) + i h₂(k) (mod 14)，i = 0, 1, …, 13,其中 h_i(k) = k (mod 14)。依序存入下列鍵值 15、18、42、19、10、28、27、38、80、55。

(一)設 h₁(k) ≡ 1，請列出最後雜湊表的結果與使用雜湊函數的次數。（10分）

(二)設 h₂(k) = 1 + k (mod 13)，請列出最後雜湊表的結果與使用雜湊函數的次數。（10分）

答：

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

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

 

五、有一檔案其字母集為 {S, T, U, V, W, X, Y, Z}，字母出現的頻率如下表：

字母	S	T	U	V	W	X	Y	Z
頻率	4	6	10	24	10	2	15	29

(一)若以下列不定長度二進位編碼 (variable-length binary code) 來編碼此檔案，請問每個字母平均用幾個位元表示？（5分）

字母	S	T	U	V	W	X	Y	Z
編碼	00	10	010	011	1100	1101	1110	1111

(二)霍夫曼碼 (Huffman code) 是一種與檔案中字母出現頻率有關的不定長度二進位編碼法，檔案經其編碼後，長度是所有不定長度二進位編碼中最短的。請為此檔案建立其霍夫曼碼，並算出此編碼下每個字母平均用幾個位元表示。（15分）

答：

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

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

 

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

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

類    科：資訊處理

科    目：資料結構

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

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

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

 

一、二元樹 (binary tree)

(一)有一個二元樹 (binary tree) 的中序走訪 (inorder traversal) 順序為ABCDEFGHI，它的後序走訪 (postorder traversal) 順序為BACFEIHGD，其中每個英文字母代表一個節點。請畫出此二元樹。（6分）

(二)上述二元樹的前序走訪 (preorder traversal) 順序為何？（6分）

(三)在二元搜尋樹 (binary search tree) 中，那一個走訪順序 (前序、中序或後序) 正好為排序好的情況？原因何在？（本小題未寫明原因者，不給分）（6分）

(四)如何利用線性掃瞄方式，判斷一個前序運算式 (prefix expression) 是否合法？（7分）

答：

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

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

 

二、解釋下列名詞：（每小題5分共25分）

(一) AVL 樹 (AVL tree)

(二)解釋圖形 (graph) 名詞：漢米爾頓迴路 (Hamiltonian circuit)

(三)解釋圖形 (graph) 名詞：廣度優先搜尋 (breadth first search)。以程式實作此搜尋時，該使用那一種資料結構？

(四) C++ 或 JAVA 語言中，protected 之意義

(五) Hanoi towers problem

答：

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

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

 

三、假設有下列數種排序方法：(A)bubble sort (B)quick sort (C)heap sort (D)merge sort (E)radix sort (F)insertion sort。回答下列問題時，請分別以 ABCDEF 之代號答之。（每小題6分共24分）

(一)一個排序法，在輸入資料中有多筆相同資料時，於排序前與排序後，任兩筆相同的資料前後順序不變者，稱之為「穩定排序法」。請問那些排序法為穩定排序法？

(二)假設輸入資料有n個，在最糟情形下，那些排序法的時間複雜度為O(nlogn)？

(三)排序程式實作時，那些排序法需要額外的陣列或鏈結串列？

(四)在程式實作時，一般使用陣列進行排序。有些時候也需要對鏈結串列進行排序。那些排序法無法對單向鏈結串列 (linearly linked list) 進行排序？

答：

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

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

 

四、假設有一個 C 語言函式如下 (左側數字為列號，非程式之一部分)：

1 int f(int n)

2 {

3 if (n == 0)

4 return(0);

5 if (n == 1)

6 return(1);

7 printf("ADD ");

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

9 }

(一)以 f(4) 呼叫上面函式，會列印出多少個 “ADD”？（6分）

(二)如果以 f(n) 呼叫上面函式，n 為任意正整數，程式執行完畢後，會列印出多少個 “ADD”？請推導其通式 (只要推導出其關係式即可)。（12分）

(三)在忽略第7列的情形下，可將上面函式改寫成更有效率的函式如下。請完成第10~12列的程式內容。（8分）

1 int f(int n)

2 {

3 int i, a, b, c;

4 if (n <= 1)

5     return(n);

6 a=0;

7 b=1;

8 for (i = 2; i <= n; i++)

9 {

10

11

12

13 } // end of for

14 return (c);

15 }

答：

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

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

 

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

98年公務人員特種考試身心障礙人員考試試題         代號：31170   全一頁

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

 

一、假設原有 N 筆資料以排序方式 (ordered) 存放於陣列，試計算插入一筆新資料平均需移動幾筆資料？（10分）

答：

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

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

 

二、請解釋堆疊 (stack) 的資料結構及運作 (operation)，並列舉一些常使用堆疊的應用。（15分）

答：

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

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

 

三、試討論使用陣列 (array) 及鏈結串列 (linked list) 實作佇列 (queue) 之優缺點。（15分）

答：

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

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

 

四、請說明在作資料排序時，選擇一個合適的排序演算法 (sorting algorithm) 必須考慮那些因素？（15分）

答：

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

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

 

五、將二元搜尋樹 (binary search tree) 所有節點資料從小到大按順序列印出來，請說明用下列那種樹尋訪演算法 (tree traversal) 可以達成：中序尋訪法(inorder)，先序尋訪法 (preorder)，後序尋訪法 (postorder)。（15分）

答：

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

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

 

六、請說明使用雜湊表 (Hash Table) 實作一個編譯器中常用關鍵詞表 (symbol table) 之優缺點。（15分）

答：

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

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

 

七、請說明最大堆積 (Max Heap) 的資料結構及運作 (operation)，並討論使用最大堆積來實作優先權佇列 (priority queue) 之優點。（15分）

答：

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

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

 

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

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

等    別：三等考試

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

科    目：資料結構

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

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

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

 

一、圖一為一個二元搜尋樹 (binary search tree)，每個節點含有一個整數。

(一)請將48加入圖一，並將結果的二元搜尋樹畫出。（5分）

(二)請將53從圖一刪除。假設每個數刪除後，皆由小於但最接近的數取代。請將結果的二元搜尋樹畫出。（5分）

(三)請將圖一以前序 (preorder) 方式表示。（5分）

(四)請將圖一以後序 (postorder) 方式表示。（5分）

答：

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

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

 

二、有兩個陣列 A = (40, 32 ,27 ,16 ,29 ,23 ,5 ,14 ,2 ,3 ,15)，

B = (39, 32, 28,16, 15, 2 ,14 ,3 ,5 ,17 ,24)。

(一) A 和 B 那一個是最大堆積 (maxheap)？（10分）

(二)將30加入是最大堆積的那個陣列中，並將結果的最大堆積以陣列的方式列出。（5分）

(三)將最大的數從最大堆積的那個陣列中刪除，並將結果的最大堆積以陣列的方式列出。（5分）

答：

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

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

 

三、假設有一個 C 程式：

int ppp (int d) {

if (d <= 1)

return d ;

return 2*ppp(d-1)+3*ppp(d-2);

}

(一)請問呼叫 ppp(4) 的回傳值為何？（10分）

(二)請問在執行 ppp(4) 的過程中，ppp(0) 被呼叫幾次？ppp(1) 被呼叫幾次？（10分）

答：

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

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

 

四、有一個鄰接矩陣 (adjacency matrix)：

其中 A, B, C, D, E, F代表節點 (node)。

(一)請將對應此矩陣的有向圖型 (directed graph) 畫出。（5分）

(二)請將此圖型的鄰接表單 (adjacency list) 畫出。節點請依字母順序由小到大列出。（5分）

(三)請列出長度為2的所有路徑。（10分）

答：

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

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

 

五、有一個雜湊表 (hash table)，共有11個籃子 (bucket)，且每個籃子中可存一個鍵值 (key)，假設雜湊函數為 h(x) = x %11，亦即除以11的餘數。今有8個鍵值：73, 25, 29, 33 , 51, 41, 20, 43。

(一)請將此8個鍵值依次存入此雜湊表，並將結果的雜湊表畫出。假設利用線性探測法 (linear probing) 來處理碰撞 (collision) 的問題。（10分）

(二)假設現在要找鍵值43，請問需要做幾次鍵值的比較才能找到43？（5分）

(三)假設現在要找鍵值64，請問需要做幾次鍵值的比較才能確定64不在雜湊表裡？（5分）

答：

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

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

 

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

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

等    別：薦任

類    科：資訊處理

科    目：資料結構

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

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

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

 

一、將四個字母 A、B、C、D依序放入 (push) 一個堆疊 (stack) 內。在放入之過程，堆疊內之字母可隨機取出 (pop)。若此四個字母最終皆被取出，則以下何者可為此四個字母被取出的順序 (例如，D、C、B、A 代表 D 首先被取出，其次為 C，再其次為 B，A 最後被取出)？（可複選）（20分)

(1) A、B、C、D

(2) C、B、D、A

(3) B、D、A、C

(4) D、C、A、B

(5) C、B、A、D

答：

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

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

 

二、如何將以下15個英文單字存入陣列 (array) A[1]，A[2]，…，A[15]，使得以後搜尋 (search) 其中任何一個字，至多只需執行三次字比較 (word comparisons)？又搜尋方法為何？請詳述。（20分）

read，educate，place，touch，fill，calculate，save，increase，

gain，print，begin，work，take，derive，operate

答：

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

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

 

三、請設計一個遞迴程式 (recursive procedure)。當輸入 (input) 為一顆有順序性且有固定根的二元樹 (ordered rooted binary tree) T 時，此遞迴程式可依中序追蹤 (inorder traversal) 方式拜訪 T 的每一個節點 (node) 恰好一次。（20分）

答：

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

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

 

四、當輸入 (input) 為 x₁, x₂, …, x_n 時，塞入排序 (insertion sort) 可將此 n 個輸入值從小到大排列。塞入排序的執行 (execution) 可簡略表示如下：

For i = 2, 3, …,n, insert x_i into x₁, x₂, …, x_i-1 such that

these i data items are sorted.

例如，當輸入為 7, 5, 1, 4, 3, 2, 6 時，塞入排序的執行如下：

i = 2:  5, 7

i = 3:  1, 5, 7

i = 4:  1, 4, 5, 7

i = 5:  1, 3, 4, 5, 7

i = 6:  1, 2, 3, 4, 5, 7

i = 7:  1, 2, 3, 4, 5, 6, 7

若 T(n) 表示執行塞入排序所需的時間複雜度 (time complexity)，其中 n 表示輸入值的個數。請用 O(f(n)) 的符號估算 T(n) 在最佳情況 (best case) 與最壞情況 (worst case) 之值，其中 f(n) 表示 n 的一個函數。（20分）

答：

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

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

 

五、假設 L 是一指標 (pointer)，指向一個雙鏈結串列 (doubly linked list)，圖示如下。

請設計一個程式 (procedure)：當輸入 (input) 為 x, y 與 L 時 (x 為存在於L 所指的串列內之資料，y 為不存在於 L 所指的串列內之資料)，此程式可在 L 所指的串列內增加 (insert) y 於 x 之後。增加 y 之後，串列仍必須為雙鏈結結構。（20分)

答：

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

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

 

[九八年資訊技師高等資料結構]

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

防設備師考試、普通考試不動產經紀人、記帳士、第    代號：01310  全一頁

二次消防設備士考試暨特種考試語言治療師考試試題

等    別：高等考試

類    科：資訊技師

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

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

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

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

 

一、假設有 n 筆資料，我們可以利用二分搜尋法 (binary search method) 或在二元搜尋樹 (binary search tree) 上搜尋特定的一筆資料。試分別說明這兩種方法如何安排資料與如何從這 n 筆資料中搜尋特定的一筆資料，並說明這兩種方法最糟情況 (worst case) 的時間複雜度。（20分）

答：

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

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

 

二、以遞迴 (recursive) 的方式寫出二元樹 (binary tree) 的中序追蹤 (inorder traversal) 與後序追蹤 (postorder traversal) 演算法。（20分）

答：

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

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

 

三、將11筆資料 (126，205，319，154，301，61，212，15，248，77，29) 以基數排序法 (radix sort) 由小到大排列，則第一階段 (pass one) 結果為何？（10分）

答：

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

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

 

四、以 6，3，1，5，4，2，7，9，8 的順序將資料插入空的二元搜尋樹 (binary search tree)，試繪出作業完成後之二元搜尋樹。（15分）

答：

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

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

 

五、有一 AOE (Activity On Edge) 網路如下圖所示，其中有向邊 (directed edge)代表工作或活動且邊上的數值代表工作或活動所需時間。試算出每個邊的最早 (earliest) 開始時間、最晚 (latest) 開始時間、與鬆散 (slack) 時間，並寫出其臨界路徑 (critical path)。（20分）

答：

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

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

 

六、試說明資料庫、資料倉儲 (Data Warehouse) 與資料探勘 (Data Mining) 三者間之差異。（15分）

答：

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

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

 

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

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

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

 

一、左下圖為一6×6迷宮，其中灰色區域表示不可通行，其餘可通行區域則有編號，入口與出口分別位於左上角 (編號0) 與右下角 (編號35)。假定每個區域有八個可能的行動方向，找尋出口路徑時，會依序嘗試此八個方向(次序請參考右下圖之箭頭編號)。利用深度優先搜尋 (depth-first search)，在迷宮中探索所有可行路徑 (路徑中不可包含重複的區域)。

(一)利用區域編號，寫出找到的第一條路徑 (編號間用逗號隔開)。（4分）

(二)利用區域編號，寫出找到的倒數第二條路徑 (編號間用逗號隔開)。（4分）

(三)找到第一條路徑前，曾經拜訪過但最後未出現在該路徑上之區域有那些？（利用區域編號作答）（5分）

(四)若迷宮大小改為2×2，且所有區域均可通行，仍以左上角與右下角區域做為入口與出口，則共存在多少種不同路徑？（5分）

答：

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

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

 

二、線性探測 (linear probing)、平方探測 (quadratic probing) 與雙雜湊 (double hashing) 可用來解決雜湊 (hashing) 時發生的碰撞 (collision) 問題，它們使用不同的 g(key, i) 函數來決定發生第i次 (i≥0) 碰撞時，鍵值 key 在雜湊表中的探測位置。

(一)線性探測為何會產生群集 (clustering) 問題？假設雜湊函數與表格容量分別為 h(key) 與 T，先寫出其 g(key, i) 函數後，再說明之。（4分）

(二)問題同(一)，但將線性探測改為平方探測。（4分）

(三)設計雙雜湊函數時，有何基本原則？先寫出其 g(key, i) 函數，再說明之。（4分）

(四)在何種狀況下，使用雙雜湊才能探測到雜湊表中所有可用的位置？（3分）

(五)某空雜湊表共有7個位置，使用線性探測來排解碰撞問題。假設鍵值k1, k2, k3均對應至相同的雜湊值4，先依序將k1, k2與k3加入雜湊表後，再刪除k2。請問此時查詢表中是否含有k3，其結果為成功或失敗？請配合圖形說明之。（5分）

答：

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

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

 

三、二元搜尋樹 (binary search tree)：

(一)二元搜尋樹與堆積 (heap) 有何主要相異點？寫出二項。（6分）

(二)將一含有 n 個節點 (n>1) 之二元搜尋樹以堆積來表示，並以一陣列來儲存此堆積，請問此陣列容量可能之最小值與最大值分別為何？請說明原因。（6分）

(三)已知二元樹節點含有二個指標欄位以指向其左子與右子，請問一棵具有n 個節點 (n>=1) 的二元樹，存在多少個空的指標欄位 (也就是其值為NULL)？請說明原因。（5分）

(四)依序將整數鍵值45, 33, 17, 65, 54, 70, 88, 25加入一棵空的二元搜尋樹，再繪製此二元樹對應之引線樹 (threaded tree)。（8分）

答：

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

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

 

四、排序 (Sorting)：參考下表之程式一與程式二回答問題。

(一)程式一是那一種排序演算法的實作？又其中的s變數有何功用？（6分）

(二)當程式一結束執行後，第9行的 swap() 函數共被呼叫幾次？又此時變數i的值為何？（6分）

(三)程式二是那一種排序演算法的實作？當其中的 while 迴圈第一輪執行完畢後，陣列 a 的內容為何？（6分）

(四)參考程式二，假設陣列 a 的元素個數為 N(N>1)，若要成功完成排序，整數變數 p 的值需有那些限制？請說明原因。（7分）

	程式一	程式二
1 1 3 4 5 6 7 8 9 10 11 12 13	int a[] = {17, 88, 19, 7, 43, 23, 56, 35} ; int n = 8; int i, j, s=0 ; for (i = 0; i<n-1 && s==0; i++){ s = 1 ; for (j=0; j<n-i-1; j++) { if (a[j]>a[j+1]) { /*將a[j]與a[j+1]互換*/ swap(a, j, j+1) ; s=0; } } }	int a[] = {17, 88, 19, 109, 7, 43, 1, 23, 99, 56} ; int n = 10; int i, j, g = n, p=2 ; while ((g=g/p)>0) { for (i = g; i<n; i++) { int temp = a[i] ; for (j = i ; j>=g && a[j-g]>temp ; j-=g) { a[j] = a[j-g] ; } a[j] = temp ; } }

答：

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

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

 

五、參考下右圖形 (graph) 回答問題，頂點 (vertices) 中的數字為頂點編號，邊(edge)上的數值代表成本 (cost)。

(一)分別使用相鄰矩陣 (adjacency matrix) 與相鄰串列 (adjacency list) 來儲存此圖時，何者所需之記憶體空間較小？假設節點編號與邊值均不大於255，且指標欄位需占用4個位元組 (byte)。（5分）

                            

(二)利用 Sollin 演算法 (Sollin’s Algorithm) 找出此圖的最小成本生成樹(minimum cost spanning tree)，須按步驟寫出此樹的成長過程。（7分）

答：

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

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