鐵路特考高員三級資料結構：97
關務三等資料結構：97
高考三級資料結構：97
身心障礙人員三等資料結構：97
檢察事務官三等資料結構：97
資訊技師高等資料結構(去除資料庫)：97
地方特考三等資料結構：97
97年特種考試交通事業鐵路人員考試及
代號：10940 全一頁
97年特種考試交通事業公路人員考試試題
資 位 別：高員三級
類 科：鐵路－資訊處理
科 目：資料結構
考試時間：2小時 座號：_______________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、假設一個圖 (graph) 的各個邊 (edge) 依下列順序輸入：（20分）
A, B A, D A, E B, C B, D D, C D, F E, F E, G F, G
(一)以 A 為起始點，利用堆疊 (stack) 依字母順序做深度優先搜尋(depth-first search)，請寫出搜尋結果。
(二)以A 為起始點，利用佇列 (queue) 依字母順序做廣度優先搜尋(breadth-first search)，請寫出搜尋結果。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、對下圖的2-3-4 樹 (2-3-4 tree) 刪除60，加入8，再轉為紅黑樹 (red black tree)，請畫出紅黑樹結果〔3-節點 (3-node) 分裂時，以較大鍵值為父節點(parent)〕。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、請畫出如何使用堆疊 (stack)，將下面中序表示法 (infix notation) a + b * c / d - e 轉成後序表示法 (postfix notation)。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、右圖中，邊 (edge) 之數字代表成本 (cost)：（20分）
(一)請用相鄰矩陣 (adjacency matrix) 表示此圖之成本。
(二)請用相鄰串列 (adjacency list) 表示此圖之成本。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、某系課程可視為 N 個資料元素構成的一個集合，裏面每個資料元素即一門課，含(1)課號 (四位數字) (2)名稱 (四個中文字) 等資料欄位，以 “課號” 為鍵，假設依序加入下面四門課：1234資料結構、2345軟體工程、3456網際網路、2333離散結構。分別用下面三種資料結構表示該集合，請分別畫圖表示之：（20分）
(一)陣列 (array)。
(二)雙鏈結環狀串列 (double linked circular list)〔要有頭節點 (head node)〕。
(三)二元搜尋樹 (binary search tree)。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
97年公務人員特種考試警察人員考試及
試題 代號：50470 全一頁
97年公務人員特種考試關務人員考試
等 別：三等考試
類 科：資料處理
科 目：資料結構
考試時間：2小時 座號：_____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、說明演算法 (Algorithm) 的意義及詳述演算法必備的條件有那些？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、假設有20個整數資料已依大小順序排好存放在陣列中，利用二分搜尋法尋找其中的資料，試寫出其演算法。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、動態資料結構與靜態資料結構有何不同？比較其優缺點？（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、試說明鏈結串列 (Link list) 的結構，並以自己熟悉的電腦語言寫一函式來計算鏈結串列的節點數目。（請註明使用的語言）（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、以插入法處理下列10個數字，排出由小到大的順序，寫出其演算法。（15分）
數字為：100，31，60，5，23，89，26，1，50，55
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、試說明遞迴 (recursive) 程式為何？試以任一電腦語言 (或虛擬碼) 以遞迴程式來計算 sin(x) 的值。（15分）
計算 sin(x) 的公式如下：
（考慮求值到小數以下第六位）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
七、例舉說明何謂2元樹、AVL 樹、2-3-4 樹，並說明其異同點。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
97 年公務人員高等考試三級考試試題 代號：35350 全一頁
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：_____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、現有變數宣告如下：（每小題5分，共25分）
int intArray[3][2] = {{10, 20}, {15, 25}, {50, 40}};
int ** intPtr1 = intArray;
int * intPtr2 = &intArray[1][1];
int * intPtr3[2] = &intArray[2];
intArray 的記憶體位址是 0x0008600，int 為 sizeof(int) = 4；
試回答下列問題 (如果是正確的敘述請寫出左邊變數的數值，錯誤請說明原因，但每題題目是有關連性的)：
(一)*intPtr2 = intArray[1][1];
(二)intPtr1 + 1 = intArray[0];
(三)++intPtr = &intArray[1];
(四)*(*intPtr + 1) = intArray[1][0];
(五)*(*intPtr3 + 1) = intArray[2][1];
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、有一個二元搜尋樹 (Binary Search Tree) T 如下：
(一)若欲搜尋的鍵值 (Key) 平均分布在 1 到 100 之間，請算出該值於搜尋樹中平均要比較幾次。（5分）
(二)設鍵值 K = 2 時，其機率為 0.5，K = 5 時其機率為 0.3，K = 9 時其機率為 0.103，其餘 97 個數機率均為 0.001，請算出該值於搜尋樹中要比較幾次。（10分）
(三)設各鍵值的機率如上述第 (二) 小題，是否能將此搜尋樹重新安排以獲得較佳的平均比較次數？請說明原因或理由。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、有關圖形與樹的名詞：（每小題5分，共25分）
(一)請說明何謂擴張樹 (Spanning Tree)。
(二)請說明何謂雙連通圖 (Biconnected Graph)。
(三)請說明何謂二分圖 (Bipartite Graph)。
(四)請說明每個樹是否均屬於二分圖。
(五)請說明每一個高度平衡二元樹 (AVL) 是否均屬於完滿二元樹 (Fully Binary Tree)。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、Ackermann's Function A(m,n)的定義如下：
此函數的成長速度相當快，對於 m 和 n 是很小時亦然
(一)試寫一遞迴演算法 (Recursive Algorithm) 來計算此函數值。（15分）
(二)試求算出 A(2, 2) 的值。（需列出求算過程）（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
97年公務人員特種考試身心障礙人員考試試題 代號：31470 全一張
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：________________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、試執行下面 Bubble Sort 排序程式，請按照 printf 指令印出數字排序的過程。（20分）
void BubbleSort(int *a,int size)
{
int i, j, k, tmp;
for(k=0; k<size; k++){
printf("%d ",a[k]);
}
printf("\n");
for(i=0; i<size; i++){
for(j=size-2;j>=i;j--){
if(a[j]>a[j+1]){
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
printf("a[%d] > a[%d] , swap\n",j,j+1);
printf("\t\t\t");
for(k=0; k<size; k++){
printf("%d ",a[k]);
}
printf("\n");
}else{
printf("a[%d] <= a[%d] , skip\n", j, j+1);
}
}
}
printf("finished\n");
}
void main()
{
int a[] = {23, 41, 33, 96, 5, 3};
BubbleSort(a, 6);
}
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、設有一圖 (graph) G = {V, E}, 點集合是 V = {a, b, c, d, e, f, g, h, i}
邊 (edge) 是以點配對 (node pair) 的方式表示如下：
{(a,b), (a,c), (b,d), (b,e), (b,f), (c,d), (d,g), (d,i), (e,f), (f,h), (f,g), (g,h), (i,g)}
試列出這個圖 d 到 f 的所有最短路徑。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、假設一有根樹 (rooted tree) 以陣列方式表示，陣列索引值 (array index) 為樹的點 (node) 的編號，陣列內容為該點的父節點。那麼考慮下列陣列所代表的樹
tree[1] = undefined
tree[2] = 1
tree[3] = 1
tree[4] = 2
tree[5] = 2
tree[6] = 3
tree[7] = 4
tree[8] = 2
試回答下列問題：（20分）
(一)此樹的高度？
(二)列出所有的葉子點 (leaf node)？
(三)此樹中 degree 最高的節點為那個節點，其 degree 數為何？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、試執行下列程式，
void main(){
int n;
scanf("%d",&n);
printf("%d\n",f(n));
}
int f(int n)
{
if(n==0 || n==1){
return 1;
}else{
return f(n-1)+f(n-2);
}
}
請回答下列問題：（25分）
(一)當輸入值 n = 5，程式輸出為多少？
(二)當輸入值 n = 10，程式執行過程中，f 遞迴深度最高為多少？
（遞迴深度為 function f 在作業系統堆疊區 (stack) 中儲存 return address 最大的個數）
(三)當輸入值 n = 6，f 總共被呼叫幾次？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、在電腦中若要「完全不失真的」儲存「大數整數」該如何儲存？如何作其加、減、乘、除四則計算？（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
97年公務人員特種考試第二次司法人員考試試題 代號：30960 全一張
等 別：三等考試
類 科：檢察事務官電子資訊組
科 目：資料結構
考試時間：2小時 座號：______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、下列兩節點序列分別為某二元樹之中序追蹤節點序列 (in-order) 與前序追蹤節點序列 (pre-order)。
中序追蹤節點序列：C, B, F, E, G, D, H, A, J, I, L, K, N, M
前序追蹤節點序列：A, B, C, D, E, F, G, H, I, J, K, L, M, N
依此兩節點序列可以重建此二元樹。
(一)請逐步演算此重建過程並說明理由。（15分）
(二)請列出此二元樹的後序追蹤節點序列 (post-order)。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、下圖為一迷宮。將有標記的位置視為一個節點 (node)，兩節點在迷宮中可以不經由其他節點走到即構成一邊 (edge)。
(一)請畫出此圖形 (graph)。（2分）
(二)有一個人在位置 S 上要走出迷宮到達位置T。此人以先向下、再向左、再向上、再向右的優先順序搜尋節點做深度優先搜尋 (depth-first-search)來尋找走出迷宮的路徑。請依時間先後列出其經過的節點。（9分）
(三)請列出以 S 為出發點以先向下、再向左、再向上、再向右的優先順序搜尋節點的廣度優先搜尋樹 (breadth-first-search tree)。（9分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、將下列十二個鍵值：22, 9, 4, 7, 25, 15, 24, 12, 3, 21, 27, 13
依序插入一空的二元搜尋樹 (binary search tree) 中。
(一)請列出中間各個步驟的二元搜尋樹。（10分）
(二)在已插入十二鍵值的二元搜尋樹中，刪去鍵值9。請列出刪除鍵值9的步驟。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、解釋下列名詞，並舉例說明。
(一)最小生成樹 (minimum spanning tree)（5分）
(二) 2-3-tree（5分）
(三) Heap sort（5分）
(四) AVL tree（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、以下有兩種資料結構來表示一棵有根樹 (rooted tree)：
(a) 每一個節點 (node) 有一個指標 par[ ] 指向此節點的父節點 (parent node)。
(b) 每一個節點有兩個指標 first-child[ ] 與 sibling[ ]，指標 sibling[ ] 指向此節點的一個兄弟節點 (sibling node) 使得此節點的所有兄弟節點構成一個串列 (linked list)，而 first-child[ ] 指向此節點的所有子節點 (child node) 由 sibling[ ] 所構成的串列的第一個子節點。
請寫一段程式將以資料結構 (b) 表示的一棵有根樹轉換成以資料結構 (a)表示。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
[九七年資訊技師高等資料結構(去除資料庫)]
|
97年專門職業及技術人員高等考試建築師、技師考試暨普通考試記帳士考試、97年第二次專門職業及技術人員高等暨普通考試消防設備人員考試、普通考試不動產經紀人考試試題 |
代號：01310 全一頁 |
等 別：高等考試
類 科：資訊技師
科 目：資料結構（包括資料庫）
考試時間：2小時 座號：_______________
※注意：(一)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(二)禁止使用電子計算器。
一、定義函數：
F(N) = 1×22 +2×32+3×42 +… …+ N×(N+1) 2 其中 N = 1, 2, 3, ……
試求 F(20) 之值為何？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、有一圖形其相鄰串列表示如圖一所示，試繪出其圖形，並求其相鄰矩陣。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、關於快速排序法 (quick sort)：
(一)平均所花時間的複雜度為何？（3分）
(二)最壞情況所花時間的複雜度為何？（3分）
(三)最壞情況何時發生？（3分）
(四)將資料 (41, 16, 48, 21, 61, 76, 13, 38, 19, 53)，以第一筆資料為 pivot key，依 quick sort 方法，由小而大排列，則第一階段 (pass one) 排序結果為何？（6分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、有一 heap tree 如圖二所示，依序執行：插入20，刪除37，插入34，等三項 heap 作業，試逐步繪出作業完成後之 heap tree。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、解釋 super key、candidate key、primary key 與 foreign key；並繪圖表示四者之間的關係。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、試說明雙向鏈結串列 doubly linked list 之結構，及其優缺點。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
七、關於資料採礦 (data mining)：
(一)資料採礦的目的為何？試說明之。（5分）
(二)資料採礦的步驟為何？試說明之。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
八、試說明 static SQL、dynamic SQL 和 embedded SQL 三者間之差異。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
97年特種考試地方政府公務人員考試試題 代號：33780 全一張
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：________________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、heap sort 是一個有名的排序演算法。請回答下列問題：
(一)下圖是 heap 的一個例子，請你說明何謂 heap？（5分）
(二) heap sort 通常使用 heap 的樹狀示意圖 (如上圖) 來表示其執行的過程。但在實作 heap sort 的程式時，我們通常並不使用二元樹 (binary tree)的資料結構來存放其資料，而改採用另一種資料結構，請問是那一種資料結構？它是如何存資料的？（5分）
(三)和 merge sort 比起來，heap sort 有何優點？（5分）
(四)和 quick sort 比起來，heap sort 有何優點？（5分）
(五) heap sort 在排序 n 個資料時，其時間複雜度 (time complexity) 為何？（5分）
(六)如果輸入之資料中所有 n 個元素的值均相等，那麼請問 heap sort 的執行時間會不會變得比較快 (和亂數輸入的資料比起來)？還是變得比較慢？請說明理由。（5分）
(七) heap sort 算是一個不錯的排序演算法，可惜它不是一個“stable”的 sort 方法。請你用較簡單的方法，將 heap sort 改良一下，將它變成一個“stable”的 sort 方法。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、典型的跳棋棋盤如下圖：
其中每個圓圈上可放上一顆棋子 (紅、黃或綠色) 或者不放棋子。現在我們不管跳棋的規則為何或棋子的擺放是否合理，請你設計一個資料結構來表示任何一種可能的盤面。你必須說明需占用多少空間及如何記錄棋子所在的位置。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、假設有一個二元樹 (binary tree) 的節點結構如下圖所示。
(一)試寫一段遞迴的 (recursive) 副程式，以計算一個二元樹 (binary tree) 的節點總數。（10分）
(二)如果這個二元樹中共有 n 個節點，請問你在(一)所設計的副程式執行的時間複雜度 (time complexity) 為何？（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、佇列 (queue) 在實作時，可用一維陣列 (one-dimensional array) 或用單向鏈結串列 (singly linked list) 來儲存。
(一)請說明此兩種資料結構在處理佇列 (queue) 元素的 insertion 及 deletion 時，有何差異。（5分）
(二)請說明此兩種資料結構各自的優缺點。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、下圖是一個假想的遊戲樹 (game tree)，其中終端節點 (terminal nodes) 的分數表示先下的電腦 (以矩形表示) 的得分，分數為正數表示電腦贏了對手(opponent，以圓形表示)，為負數則表示電腦輸了。
(一)試用 Minimax procedure 求 root 的分數。（5分）
(二)請問電腦一開始應該走那一步才會贏？（5分）
(三)這種遊戲我們通常稱為 zero-sum game，請解釋 zero-sum 的意義。（5分）
(四)如果我們寫一個程式，能很快地將某種遊戲的遊戲樹完全展開，並很快地用 Minimax procedure 求 root 的分數，那麼在這個情形下，是否電腦就能下出最好的走法？請說明之。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
留言列表
國考資訊處理解答 (7)
