高考三級資料結構：92
身心障礙人員三等資料結構：92
檢察事務官三等資料結構：92
交通事業公路人員升資員級晉高員級資料結構：92
港務人員升資員級晉高員級資料結構：92
公務人員升官等薦任資料結構：92
台灣地區省(市)營事業機構人員升等第八職等資料結構：92
資訊技師高等資料結構(去除資料庫)：92
專門職業及技術人員檢覈資料結構：92
地方特考三等資料結構：92
2003年高上高普特考！
資訊
《資料結構》
一、數學上求兩數的最大公因數 (Greatest Common Divisor，簡稱GCD) 可使用歐幾里德 (Euclid) 的輾轉相除法來完成。規則是”兩數 m 與 n 的最大公因數等於這兩數的差和較小數的最大公因數”，由此可看出遞迴規則。請寫一個遞迴程式或演算法來計算 m 與 n 兩數 (m > n) 的最大公因數。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、試說明將1，2，3，4四個數字依此一次序分別經由堆疊 (stack)、佇列 (queue)、與雙向佇列 (deque) 做排列，問各有多少種不同的排列方法？請也分別寫出這些排列的結果。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、(一)一棵 degree 為 k 的二項式樹 (binomial tree) 有多少個節點 (nodes)？（5分）
(二)一棵 order 為 m 的 B-樹 (b-tree)，失敗節點 (failure nodes) 落在第 n 層 (level)，則這棵 B-樹最少可存放多少個鏈 (keys)？（5分）
(三)一棵 degree 為 m，高度為 h 的查詢樹 (search tree) 最多有多少個節點？（5分）
(四)一棵深度 (depth) 為 h 的完整二元樹 (complete binary tree) 最少有多少個節點？（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、找出在下述追蹤 (traversal) 皆具相同順序值之所有二元樹：
(一) preorder 及 inorder。（7分）
(二) preorder 及 postorder。（7分）
(三) inorder 及 postorder。（6分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、(一)請詳細說明「二元堆積」(binary heap) 此種資料型態支援那幾種運算？若以「陣列」(array)來「製作」(implement) 二元堆積，這些運算在時間上的複雜度各為何？
(二)二元堆積裡所存放的元素裡，其最小元素只會出現在該二元堆積的那些地方？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
九十二年公務人員特種考試身心障礙人員考試試題 代號：31610 全一張
等 別：三等考試
科 別：資訊
科 目：資料結構
考試時間：二小時 座號：________________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)本試題禁止使用電子計算器。
一、(一)何為「二元堆積」(binary heap)？假設陣列 A 恰存有整數值 [16, 14, 10, 8, 7, 9, 3, 2,4, 1]，請說明為何 A 的結構為二元堆積。
(二)現在把數字11 加入 A 中，放置的初始位置為數字1之後。請逐步圖說如何由下向上調整 A，使 A 恢復二元堆積的性質。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、二元樹的資料結構如下：（20分）
typedef struct node *node_ptr;
typedef struct node{
int data;
node_ptr left_child, right_child;
};
給定兩顆樹
node_ptr treel, tree2;
試寫一程式比較此二樹是否除了樹葉 (leaf) 外，內部點 (internal node) 的結構與資料均相等。假設一個空的二元樹或指標以 NULL 表示。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、給予如下的迷宮，起點在 A 的位置，終點在 O 的位置。
(一)試提出一資料結構將這個迷宮呈現出來。（10分）
(二)請寫出一個深度優先追蹤 (depth-first traversal) 的演算法可以用來找出出迷宮的路徑。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、請寫一小段程式，以一個大小為 n 之「陣列」(array) 製作一個最大容量為n 之「佇列」(queue)。請特別留當佇列所存放之元素個數等於0或 n 時，你的程式應判斷是否終止執行。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、(一)什麼是尾部遞迴 (Tail recursion)？（5分）
(二)尾部遞迴的演算法很容易移去遞迴呼叫，改成疊代 (Iteration) 的方式。請先判斷下列的演算法有無尾部遞迴，若有則改寫為疊代演算法。若沒有，則說明原因不用修改。（15分）
Procedure traverse (T)
if T ≠ 0 then { print DATA(T)
call traverse (LLINK(T))
call traverse (RLINK(T))}
end
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
九十二年公務人員特種考試司法人員考試試題 代號：30730 全一頁
等 別：三等考試
類 科：檢察事務官電子資訊組
科 目：資料結構
考試時間：二小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、設計一種資料結構可以用來儲存任意大小的非負整數 (包含零及正整數)，並請寫一段程式在這資料結構上做兩非負整數的加法運算。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、假設一組數為：A = 8, B = 17, C = 15, D = 10, E = 12, F = 19, G = 6, H = 30, I = 5, J = 14考慮以下序列運算：Insert(A), Insert(B), Insert(C), Insert(D), Insert(E), Insert(F),Insert(G), Insert(H), Insert(I), Insert(J), Delete(A)。（20分）
(一)請描述 binary search tree 的特性，並請畫出經過以上序列運算所建構的binary search tree。
(二)請寫出所建構之binary search tree 的preorder, inorder, postorder, breadth-first order。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、一個 n 乘 n 的方陣 A = [ai,j]，1≤ i≤ n, 1≤ j≤ n，若存在一數 k, k≤ n，使得當i–j ≥ k 與 i–j < 0 時ai,j = 0；則此方陣稱為下三角斜條方陣 (lower triangular banded matrix)。若 0 ≤ i–j < k 則稱元素 ai,j，在斜條 (band) 上。
請設計一方法將斜條上的元素儲存至一維陣列 D。（20分）
(一)問 D 總共有多少元素。
(二)假設 0 ≤ i–j < k，請寫出 ai,j 儲存於陣列 D 的指標位置。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、假設有一組整數，每個數都介於0與31之間。請寫一個程式將這組數依小到大排序。若這組整數的個數為 N，這程式所需要的計算次數最多為 O(N)。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、寫一程式將一個 linked list 的所有元素 (entries) 的次序完全倒過來 (如下圖所示)。（10分）
原來的linked list:
次序完全倒過來的linked list:
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、令長度為 n 的序列集合
An = {x1,x2,…,xn| xi= 0, 1或2，對 1≤i≤n-1, xi, xi+1≠1,1 且 xi, xi+1≠2,2}（即序列中沒有連續兩個1 或是連續兩個2）。
設 f(n) 為 An 的個數，f0(n), f1(n), f2(n) 分別為 An 中 x1 = 0, 1, 2 的序列的個數。請導出 f(n) 的遞迴公式 (recursive formula)，並請寫一非遞迴函式計算 f(n)。（15分）
[九二年交通事業公路人員升資員級晉高員級資料結構]
10480
九十二年交通事業公路人員升資考試試題 代號：11780 全一頁
41780
級 別：員級晉高員級
類 科：資訊管理、資訊處理
科 目：資料結構
考試時間：二小時 座號：________________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、現有兩「串列」(linked list)，串列內之元素皆已由大到小依序接續排列。（20 分）
(一)請寫出一簡短程序，將這兩個串列「合併」(merge) 為一個單一的串列，串列內之元素也是由大到小依序接續排列。
(二)你所寫的程序的時間複雜度為何？（以 O (…) 表示）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、對於具「線性序列」(linear order) 關係的關鍵值集合，「優先佇列」(priority queue) 此抽象資料型態可用以保存一組關鍵值，並只支援以下四項運算：
(一) create()：建立一個空的優先佇列。
(二) insert(x, Q)：將關鍵值 x 加入優先佇列 Q。
(三) maximum(Q)：傳回優先佇列 Q 中的最大值。
(四) extract-maximum(Q)：傳回並除去優先佇列 Q 中的最大值。
如何以「二元堆積」(binary heap)的方式，在一個「陣列」(array) 裡存放該優先佇列 S 的元素，並支援到四項運算？並請說明所製成的優先佇列在處理以上四項運算時，並列出其時間複雜度。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、下圖中的邊都附有權值 (weight)。圖中路徑 (path) 的長度為其中所有邊權值的總和。列出下圖所有從 s 點出發，到 t 點的最長路徑。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、(一)說明紅黑樹 (red-black tree) 與一般的二元找尋樹有什麼關係？（5分）
(一)一般的樹都可轉換成紅黑樹嗎？請說明理由。（5分）
(二)請以下兩圖為例說明紅黑樹的轉換原則，請以虛線代表紅色指標，實線代表黑色指標。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、如果「可能出現的關鍵值集合」(universe of keys) U 是一個存在有「線性序列」(linear order)關係的集合，那麼「雜湊表格」(hash table) 與「二元搜尋樹」(binary search tree) 都可以用來「製作」(implement) 以關鍵值為查詢方式的「字典」(dictionary)。請就「雜湊表格」與「二元搜尋樹」兩者在「建立初始字典」(creation)，「查詢單一關鍵值」(search)，「消除單一關鍵值」(delete)，「合併字典」(merge) 四項運算方面，比較兩者在運算時間上的複雜度。我們可假設「二元搜尋樹」中的「葉節點」(leaf nodes) 在樹中的深度差別最多唯一，且假設關鍵值隨機出現在雜湊表格中得任何一個儲存格，且無「碰撞」(collision)情形發生。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
[九二年港務人員升資員級晉高員級資料結構]
12840
九十二年交通事業港務人員升資考試試題 代號：14240 全一頁
級 別：員級晉高員級
類 科：資訊處理
科 目：資料結構
考試時間：二小時 座號：_______________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、如果一棵最小累堆所對應的陣列內容如下：
a[0] = 3, a[1] = 5, a[2] = 11, a[3] = 15, a[4] = 19,
a[5] = 77, a[6] = 59, a[7] = 26, a[8] = 48, a[9] = 61
(一)依序加入4, 80, 55, 8, 7, 1，請列出陣列最新的內容。（12分）
(二)由原先給定的10個元素的最小累堆 (min-heap) 中，依序除去4筆較小的資料，請列出陣列最新的內容。（8分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、(一)什麼是外張樹 (Splay tree)？（6分）
(二)於外張樹中一個外張運算 (Splay operations) 是由某一“起始節點”(start node) 展開一連串的旋轉動作。請分別說明如何於加入、刪除、與找尋等動作時決定那一個節點是“起始節點”。（7分）
(三)典型的外張運算可分成 RR, LL, RL, LR 四種類型。
請以右邊圖形說明 RR 外張運算的做法。
假設 q 是起始節點。（7分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、給予如下的圖：
(一)試提出一種圖形表示法，表示這個圖形。（6分）
(二)以頂點1為起點，繪出深度優先展開樹 (depth-first spanning tree)。（7分）
(三)以頂點6為起點，繪出廣度優先展開樹 (breadth-first spanning tree)。（7分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、(一)何謂動態變數？（10分）
(二)於下列程式的片段中，請指出何者是動態變數？為什麼？（10分）
typedef struct node {
int data;
struct node *link;
} NODE;
NODE *list = null;
list = (NODE *) malloc (sizeof(NODE));
list->data = 35;
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、某程式共有 n! 種不同輸入，每種輸入的發生機率都是一樣。已知該程式的平均執行時間為 T，試證明至少存在有n!/2種輸入其每個的執行時間都不超過 2T。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
38250
九十二年公務人員升官等考試試題 代號：38450 全四頁
等 別：薦任升官等考試
科 別：資訊工程、資訊處理
科 目：資料結構
考試時間：二小時 座號：_________________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、所謂三主對角線矩陣 (tridiagonal matrix)，定義為在這種稀疏矩陣中，除了主對角線和其上下的元素非0外 (就是其中間的三條斜線非0)，其它皆為0，如圖一。假如矩陣A，以列主序 (row major order) 的方式存到陣列 B 中，若 A[0][0] 存到 B[0] 處，則 A[i][j]，0 ≤ i, j < n，存至 B 中的那一個位置？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、有一個年輕小伙子，不到二十歲就拿到了電腦博士學位，教了幾年書又覺得學生的素質和他的認知有一段距離，一氣之下，決定入山出家當和尚去了。經過面談後，住持方丈覺得他的心意已決，了無牽掛，乃為其剃度，同時覺得他的學識能力甚佳，於是乎就指定他去管理後山的藏經閣。到了藏經閣，這位年輕的和尚嚇了一跳，整棟屋子擺滿了各式各樣的經書，寺裡的和尚借書，並無任何法則，想讀就拿，讀累了，就隨便放回去! 他心想為了保存這些彌足珍貴的經書，該是為這些經書電腦化的時候了。他希望他的經書管理系統，具有登入借閱者的基本資料以外，同時希望具有查詢、新增、刪減經書的能力。這個和尚花了整整一年的時間，將這些經書分門別類擺在架子上，同時他發現了一些現象如下：每一本經書皆為單一個作者編著，且同一作者不會在不同年編著同一名稱的經書；同一名稱的經書，有不同的和尚在同一年或不同年為其編著；一個和尚在同一年或不同年會編著不同名稱的經書；編著者的出生年月日皆不可考。經過思考後，他馬上進行程式寫作，只花了半小時系統就完成了。假如你是他的話，你將採取何種資料結構來製作此經書管理系統，詳述其優缺點。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、假設有 n 筆資料，利用快速排序法依其鍵值 (key) 排成由小到大，試證明：
(一)快速排序法的最佳計算時間為 O(nlog2 n)。（5分）
(二)快速排序法的最差計算時間為 O(n2)。（5分）
(三)快速排序法的平均計算時間為 O(nlog2 n)。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、我們可以利用堆疊資料結構來把中置式 (infix expression) 轉成後置式 (postfix expression)。其轉換的方法如演算法一，而其用到的 ISP 和 ICP 表為圖二。其中運算子 " + - " 為二元運算子 (binary operator)。
procedure POSTFIX(E)
// convert the infix expression E to postfix. Assume the last character of E is a "∞" ,which will also be the last character of the postfix. Procedure NEXT-TOKEN returns either the next operator, operand or delimiter – whichever comes next. STACK(1:n) is used as a stack and the character "-∞" with ISP( "-∞" ) = -1 is used at the bottom of the stack. ISP and ICP are functions. //
STACK(1) ← "-∞" ; top ← 1 // initialize stack, top is the pointer of the stack //
loop
x ← NEXT-TOKEN(E)
case
:x = "∞" while top >1 do // empty the stack //
print(STACK(top)); top ← top - 1
end
print ("∞")
return
:x is an operand: print(x)
:x = ") " :while STACK(top) " (" do //unstack until ") " //
print (STACK(top)); top ← top - 1
end
top ← top – 1 //delete " (" //
:else: while ISP(STACK(top)) ICP(x) do
print (STACK(top)); top ← top - 1
end
call ADD(x, STACK, n, top) // insert x in STACK //
end
forever
end POSTFIX
圖二.(a)為一般型態的運算子狀況，其優先權順序為 " ( ) " > "**" >" * /" >" + - "；在運算子的結合性中 " **" 運算子為右結合，" * /" 運算子為左結合，" + -" 運算子為左結合。
(一)若把運算子 " * / + -" 的結合性改為右結合 (但其他性質不變)，則應該用圖二中的那一個 ISP 和 ICP 的運算子表？（5分）
(二)若把運算子 " **" 的結合性改為左結合 (但其他性質不變)，則應該用圖二中的那一個 ISP 和 ICP 的運算子表？（5分）
(三)若把運算子 " */" 的結合性改為右結合 (但其他性質不變)，則應該用圖二中的那一個 ISP 和 ICP 的運算子表？（5分）
(四)若把運算子 " */" 的優先權改為比運算子 "+ -" 的優先權還低 (但其他性質不變)，則應該用圖二中的那一個 ISP 和 ICP 的運算子表？（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、在一個二元搜尋樹中有 a1, a2 , ..., an，n 個識別字，其中 a1 < a2 < ... < an。假設搜尋 ai 的機率為 pi 則搜尋成功的成本為 。但因搜尋有可能不成功，我們可以把不在二元搜尋樹中的識別字分成 n+1個類別Ei，0 ≤ i ≤ n，E0包含所有識別字 X，X<a1，Ei 包含所有識別字 X，ai<X<ai+1，1 ≤ i ≤ n，En 包含所有識別字 X，X>an。假設搜尋失敗的機率為 qi 則搜尋失敗的成本為
ic11
。因此一個二元搜尋樹的總成本為
。
其中
。令 Tij 為一個最佳搜尋二元樹，具有 ai+1, ..., aj個識別字，i<j。Tii 為空樹，0 ≤ i ≤ n。Tij 無定義，i>j。令 cij 為尋找 Tij 的成本，cii = 0。rij 為 Tij 的根，
為 Tij 的重量。
令 n = 4且 (a1, a2, a3, a4) = (do, if, read, while)。
假設 (p1, p2, p3, p4) = (3, 3, 1, 1) 和 (q0, q1, q2, q3, q4) = (2, 3, 1, 1, 1)。為了方便計算，所有的機率值已經預先放大16倍，依搜尋總成本找出其最佳搜尋樹。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
[九二年台灣地區省(市)營事業機構人員升等第八職等資料結構]
九十二年台灣地區省（市）營事業機構人員升等考試試題 代號：32120 全一頁
等 別：第八職等
類 科：資訊處理
科 目：資料結構
考試時間：二小時 座號：_____________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、請說明在設計“大富翁”遊戲中你會使用那一種資料結構？如何使用？（20 分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、Queue 適合用在那一類的應用？請說明其理由。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、解釋名詞：（20分）
(一) Abstract Data Types
(二) Class
(三) Object
(四) Tree
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、請說明在設計“電子地圖”中你會使用那一種資料結構？如何使用？（20 分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、Stack 適合用在那一類的應用？請說明其理由。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
[九二年資訊技師高等資料結構(去除資料庫)]
高等考試建築師、技師、不動產估價師
九十二年專門職業及技術人員 考試試題 代號：01410 全一張
暨普通考試不動產經紀人、地政士
等 別：高等考試
類 科：資訊技師
科 目：資料結構（包括資料庫）
考試時間：二小時 座號：______________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、當圖形 G 是聯通時，以任何一個頂點所作的深度優先搜尋或闊度搜尋都會走過 G 中的所有頂點。任何一個只由 G 的邊所構成，且包含 G 中所有頂點的樹稱為一個展開樹。圖一為一個完整圖形，請畫出其至少三個展開樹﹔圖二中邊上的數代表成本，請用最小成本展開樹的方法由頂點1 開始將展開過程寫出，並繪出最小成本展開樹。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、試以英文十二個月之字母建立一高度平衡的二元樹。假設各識別字插入之順序為 MARCH，MAY，NOVEMBER，AUGUST，APRIL，JANUARY，DECEMBER，JULY，FEBRUARY，JUNE，OCTOBER 與 SEPTEMBER 請繪出高度平衡二元樹增長過程與最終結果，同時亦顯示為保持高度平衡所需的重建步驟。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、假設有一多項式 A(X) = amXem + …… + a1Xe1，其中 aj 為非零的係數，其冪次為 ej。請定義一串列來表示此一多項式，並舉例說明之。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、查位法 (hashing) 為關聯式檔案的位址換算技巧之一，其常用的查位函數有除餘法、平方中值法與摺疊法。請舉例解釋相關位址為n 個數字的平方中值法之技術。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、下列為兩個尚未完成的緩衝器管理常式且假設每區段含有 n 個紀錄：
通道程式 應用程式
Loop: If flag = 0 go to Loop. Wait: If flag = (2) Go to wait.
Empty the buffer. Counter := Counter + 1
Counter := 0 Move record work area into
flag := (1) record [counter]
Go to Loop. If Counter :> (3)
then flag := (4)
Go to Wait.
請將以上兩個常式中的空白填入適當的資料，並說明使用了多少個緩衝器暨解釋旗標 (flag) 所有可能的意義。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、假設以鄰近區域性矩陣表示序數為 N 的有方向性的圖形，若 graph (i，j) = 1則有一邊界連接節點 i 和 j，否則其值為0即表示 i、j 不連接，則節點的內分支度 (in-degree)、節點的外分支度 (out-degree) 應如何表示。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
律師、會計師、建築師、技師
九十二年專門職業及技術人員 檢覈筆試試題 代號：31610 全一頁
社會工作師、土地登記專業代理人
類 科：資訊技師
科 目：系統分析
考試時間：二小時 座號：____________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、 迷宮問題 (Maze problem) 是使用資料結構與技巧來撰寫程式模擬老鼠走迷宮。假設老鼠是聰明的， 它使用嘗試錯誤法 (try-end-error method) 及回溯法 (backtracking) 技巧，使得錯誤的路徑不會重複走第二次，且可回到前面的路徑繼續嘗試其他可行的路徑，最後能夠找到正確路徑，走到終點。主要的資料結構是：(1)迷宮：MAZE (1:m, 1:n)，(2)記號：MARK (1:m, 1:n) 記錄有無走過。演算法大致如下：（20分）
set list to the maze entrance coordinates and direction north;
while list is not empty do
(i, j, move)←coordinates and direction from front of list
while there are more moves do
(g, h)←coordinates of next move
if (g, h) = (m, n) then success
if MAZE (g, h) = 0 and MARK (g, h) = 0 then
[MARK (g, h)←1
add (i, j, move) to front of list
(i, j, move)←(g, h, null)]
end
end
print “no path has been found”
問題：(一)從演算法中如何可以說明老鼠是聰明的？
(二)演算法中的 list 有什麼作用？
(三)為了讓老鼠能使用嘗試錯誤及回溯法技巧，list 應該如何製作？
(四)迷宮 MAZE (1:m, 1:n) 一共有個 m×n 位置，規定 MAZE (i, j) = 0代表可通行，MAZE (i, j) = 1 代表無法通行。若 z 代表正確路徑中老鼠可走的最多位置的數目，問 z 應該是多少？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、(一)佇列 (queue) 可使用陣列 (array) 或是鏈結串列 (linked list) 來實作之。請比較兩者的優缺點。（10分）
(二)當分別使用單一鏈結串列 (singly linked list) 與環狀鏈結串列 (circular linked list) 來實作佇列時，你覺得那一個較好，請說明你的理由。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、給定以下八個資料
39, 27, 12, 45, 61, 1, 23, 15
要加入 (insert) 一個目前沒有任何資料的二元搜索樹 (binary search tree) 中。試問何種輸入順序使得最後產生的二元搜索樹的高度 (height) 最高且為傾斜 (skewed)。若答案不只一種，必須列出所有答案。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、令 e 為一個無向圖的一個邊 (edge)，令 G 為把e自 G 刪去後所得到的圖。若在 G 中存在兩個連通 (connected) 的點 u 和 v，但是 u 和 v 在 G卻是不連通，則稱 e 是 G 中的一個橋 (bridge)。
一個連通的圖若是不含任何橋則稱之為橋連通 (bridge connected) 圖。一個圖的最大橋連通子圖 (subgraph) 也稱之為橋連通元件 (bridge connected component)。
(一)試列出下圖中含節點數最多的橋連通元件。（10分）
(二)試列出下圖中含邊數最多的橋連通元件。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、(一) 2-3樹與 AVL 樹都是找尋樹，請簡扼比較兩者的主要差異。（5分）
(二)於下列2-3樹中依序加入70, 30, 60，請畫出最後的結果。（7分）
(三)將(二)加入後的最後結果刪除40，再畫出刪除後的結果。（8分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
九十二年特種考試地方政府公務人員考試試題 代號：32710 全一頁
等 別：三等考試
類 科：資訊
科 目：資料結構
考試時間：二小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、(一)設計一個問題的演算法有遞迴 (Recursive) 與疊代 (Iteration) 等方式，問在什麼情況下，適合將遞迴演算法改為疊代演算法？（6分）
(二)試比較遞迴演算法與疊代演算法的優缺點。（7分）
(三)數學上有一種費氏級數 (Fibonacci numbers)，其定義如下：
請說明產生 n = 100 的費氏級數適合使用遞迴演算法或疊代演算法？寫出你的答案與理由。（7分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、請回答下列問題：（每小題5分，共20分）
(一)說明什麼是雙向佇列 (deque)？
(二)將1, 2, 3 三個數字依此一次序經由 deque 做排列，問有多少種不同的排列方法？
(三)將1, 2, 3, 4, 5 五個數字依此一次序經由 deque 做排列，問能否得到 5, 1, 3, 4, 2 的排列結果？說明你的做法或理由。
(四)下列那一種資料結構最適合於用來製作 deque？說明你的理由。
陣列 (Array), 單鍵鏈結串列 (Singly linked list), 雙鍵鏈結串列 (Doubly linked list), 二元樹 (Binary tree)
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、試列出下圖的所有二連通元件 (biconnected component)。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、(一)說明什麼是外張樹 (Splay tree)？
(二)於下列的二元找尋樹中，若由節點1開始做外張運算，請依序畫出運算動作的過程以及最後的結果。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、將下列資料依序輸入，以所指定的資料結構呈現結果：
Dec, Jan, Apr, Mar, Jul, Aug, Oct, Feb, Sep, Nov, May, Jun
其中字串大小依英文字母順序決定，亦即 A< B <…< Z，a < b <…< z。
(一)二元查詢樹 (binary search tree)。（10分）
(二)最大累堆 (max-heap)。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
留言列表
國考資訊處理解答 (7)
