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

高考三級資料結構：90

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

國家安全情報人員三等資料結構：90

中央暨地方機關公務人員升官等薦任資料結構：90

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

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

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

2001 年高上高普考！

資訊

《資料結構》

一、請回答下列問題：

(一)何謂二元搜尋樹 (Binary Search Tree)？（5分）

(二)用二元搜尋樹去表示 n個元素時，最小高度及最大高度的二元搜尋樹(height of binary search tree) 其值分別為何？（5分）

(三)設計一個演算法 (algorithm)，當輸入n個元素時，能建立一最小高度的二元搜尋樹。（10分）

答：

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

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

二、請回答下列問題：

(一)寫出下列數 5、28、19、15、20、33、12、17、10 所對應的雜湊表 (hash table)，該雜湊表HT[0：8] 其長度為9，用串列 (linked list) 來表示碰撞 (collision) 情形，且其雜湊函數 (hash function) h(k)＝k mod 9（10分）

(二)雜湊函數 h(k) = k mod m，說明當 m = 2^P 時有何缺點？並建議 m值應為何？（10分）

答：

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

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

三、請回答下列問題：

(一)用一維陣列 (one-dimensional array) A[1：10]來表示下圖的兩棵樹。（10分）

(二)利用 (一) 之資料結構，設計一演算法，該演算法將合併 (union) 兩棵樹成為一棵樹。（10分）

答：

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

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

四、請回答下列五個問題：（每小題8分，共40分）請先回答各小題的敘述是否正確（占2分），如果正確則證明之，否則請舉例說明敘述錯誤之處（占6分）。

(一)假設無方向圖形 (undirected graph) G 上沒有迴圈 (cycle) 存在，則 G 必定是一棵樹。

(二)有一非空的二元樹 (non-empty binary tree)，其葉節點 (leaf node) 的個數為n₀，分支度 (degree) 為2的節點其個數為 n₂，則 n₀ = n₂ + 1。

(三)一完整的二元樹其深度為 k (full binary tree of depth k)，此二元樹有 2^k-1個節點。

(四)假如無方向圖形 (undirected graph) G上有 n個節點 (node)，n-1 個邊(edge)，則 G 必定是一棵樹。

(五)利用快速排序 (Quick sort) 將任何 n個數排成由小到大的次序，均可在O(n log n) 時間完成。

答：

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

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

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

公務人員特種考試司法人員

九十年                        考試試題           三：06-7       全一頁

特  種  考  試  軍 法 官

等    別：三等考試

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

科    目：資料結構

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

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

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

一、執行下列程式片段：

A:=10; B:=15; C:=30; D:=12;

Insert(A); Insert(B); Insert(C); Insert(D);

Delete(E); Delete(F);

Insert(X) 是將一 X 值的節點 (node) 插入一個 linked list 的適當位置，Delete (X) 是刪除此 linked list 中適當位置的節點，並將該節點之值儲存在X。

(一)假設 linked list 實現的資料結構為一 stack，則 F 值為何？（5分）

(二)假設 linked list 實現的資料結構為一 queue，則 F 值為何？（5分）

答：

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

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

二、有一串列 (bat, fat, sat, vat)，儲存在一個 linked list，如圖所示：

指到第一個節點 (node) 的指針 (pointer) P 代表此串列 (list)。

(一)請用圖說明如何在 bat 和 fat 這二個節點中間，插入節點 cat？（10分）

(二)請用圖說明如何刪除 sat 這個節點？（10分）

答：

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

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

三、假設一個二元樹 (binary tree) 含有9個節點 (node)：

(一)此樹最小的 level 是多少？（5分）

(二)此樹最大的 level 是多少？（5分）

答：

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

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

四、請扼要說明下列排序法 (sorting)，應用這些排序法將一排數字 (390, 205, 182, 45, 235) 按照由小而大的順序排列，並逐步列出排列情形：（每小題5分，15分）

(一) selection sort

(二) exchange sort

(三) insertion sort

答：

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

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

五、已知一個二元樹：（每小題5分，共15分）

(一)列出 preorder traversal 時，visit 各節點的順序。

(二)列出 inorder traversal 時，visit 各節點的順序。

(三)列出 postorder traversal 時，visit 各節點的順序。

答：

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

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

六、使用資料結構 hash table 儲存一組數字 (4, 9, 10, 12, 16, 20)。假設 hash table 有6個 bucket，hash function 使用 mod 5。

(一)此 hash table 採用 static hashing，而每一個 bucket 有兩個 slot，請說明此組數字儲存在 hash table 的情形。（10分）

(二)假如每一個 bucket 只有一個 slot，請說明在 collision 或 overflow 發生時的處理方式。（10分）

答：

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

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

七、(一)如何界定一個 B tree？（5分）

(二)在什麼狀況之下，使用一般的 B tree 做 tree 的搜尋和增刪，要比 AVL tree 的性能佳？（5分）

答：

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

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

[九十年國家安全情報人員三等資料結構]

                      國家安全局國家安全情報人員

九十年公務人員特種考試                    考試試題  三：04-3   全一張

法務部調查局調查人員

等    別：三等考試

類 科 組：國家安全情報人員資訊組

科    目：資料結構

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

※注意：(一)本試題得使用電子計算器。

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

一、若 A[1][0] 在主記憶體位置8，A[3][3] 在主記憶體位置144，A[4][1] 在主記憶體位置184，試求 A[5][5] 在主記憶體位置。（20分）

答：

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

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

二、請採用 left child-right sibling 表示法將下列的樹化為二元樹 (binary tree)，再將其製成一引線二元樹 (threaded binary tree)。（20分）

(x(a, b (c (d)), e (f (g, h)), i (j, k)))

答：

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

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

三、(一)將下列中序算術式 (infix expression) 轉換為後序算術式 (postfix expression)。（10分）

A*(B+C*D-E)+F*G-H

(二)若 A = 3, B = 5, C = 12, D = 15, E = 2, F = 5, X = 100, Y = 2, Z = 8，試求下列後序算術式的值。（10分）

A B C * D / E F X * + - Y + Z / -

答：

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

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

四、一個陣列裡面包含下列整數。試求出對應的二元樹，再將其轉變為一堆積(heap)。（20分）

45, 84, 7, 12, 62, 90, 77, 44, 29, 14

答：

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

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

五、下列 C 語言程式裡用到堆疊 (Stack) 和佇列 (Queue)。請寫出此程式執行後的列印結果。（20分）

#include <stdlib.h>

#define max   6

typedef struct Item *Element;

struct Item{ int f1; float f2;};

struct Item stack[max];

struct Item queue[max];

Element item;

int top;

int N = max + 1, head;

int tail;

void STACKpush(Element s)

{stack[top].f1 = s->f1; stack[top++].f2 = s->f2;}

Element STACKpop()

{return &stack[--top];}

void QUEUEput(Element q)

{queue[tail].f1 = q->f1; queue[tail++].f2 = q->f2; tail = tail % N;}

Element QUEUEget()

{head = head % N; return &queue[head++];}

main()

{   int i, j, k;

float z;

top = 0;

head = N; tail = 0;

i = 0; j = 1; k = i+j; z = k*2.0;

item = malloc(sizeof *item);

while (z < 60.0)

{   item->f1 = k;

item->f2 = z;

if (k%3 == 0) QUEUEput(item);

else STACKpush(item);

if (k%4 == 0 && head % N == tail)

{   item = QUEUEget();

printf(" DQ %d %d %f\n", head, item->f1,item->f2);

}

if (k%5 == 0 && top != 0)

{   item = STACKpop();

printf(" DS %d %d %f\n",top,item->f1,item->f2);

}

i = j; j = k; k = i + j; z = k*2.0;

}

printf("Stack contains \n");

while (top >= 1) {item = STACKpop();

printf(" %d %d %f\n",top, item->f1,item->f2);

}

printf("Queue contains \n");

while (head % N != tail) {item = QUEUEget();

printf(" %d %d %f\n", head, item->f1, item->f2);

}

}

答：

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

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

[九十年中央暨地方機關公務人員升官等薦任資料結構]

281

九十年中央暨地方機關公務人員升官等考試試題     薦任：    -5    全一頁

283

等    別：薦任升官等考試

科    別：資訊工程、資訊處理

科    目：資料結構

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

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

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

一、A_m×n×p 為一個三維陣列 (array)，其元素(element)以 a_ijk 表示之，其中 1≦i≦m，1≦j≦n，1≦k≦p。若此陣列儲存在記憶體 (memory) 的方式為以列為主 (row major)，且 a₁₁₁ 在記憶體中的位址為 α，請寫出 a_ijk 在記憶體中的位址公式。（20分）

答：

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

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

二、雙鏈串列(doubly linked list)之節點各欄位名稱如下圖所示：

其中 llink 為左鏈結 (left link)，rlink 為右鏈結 (right link)。試寫出雙鏈串列之插入 (insert) 及刪除 (delete) 運算 (operation)，設插入的節點在節點 P 之後，而刪除的節點為 Q。（20分）

答：

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

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

三、令 n₀ 為二元樹 (binary tree) 之葉節點 (leaf node) 個數，n₁ 為只有一個孩子 (child) 的節點個數，n₂ 為有兩個孩子的節點個數。試證對至少有一個節點的二元樹，n₀ = n₂ + 1。（20分）

答：

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

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

四、試敘述合併排序法 (merge sort) 並分析其時間複雜度 (time-complexity)。（20 分）

答：

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

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

五、以 A、B、C、D 四個英文字母可以造出幾棵不同的二元搜尋樹 (binary search tree)？注意：四個英文字母要同時出現在同一棵樹中。（20分）

答：

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

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

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

建築師、技師

九十年專門職業及技術人員高等考試             考試試題  高：14-1 全一頁

不動產估價師

類    科：資訊技師

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

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

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

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

一、假設我們有一組的訊息 M₁, M₂, M₃, M₄, M₅, M₆ 分別有不同的發生頻率如下：

(一)產生一個二元樹 (binary tree)，並最小化其 root 到各 leaves 節點的加權路徑 (weighted external path)。（10分）

(二)解釋如何由此一二元樹產生每一個訊息的 Huffman code 並說明Huffman code 的性質和用途。（10分）

答：

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

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

二、排序 (sorting) 的 lower bound 為 O(n log n)

(一)請簡單的證明為何 lower bound 為 O(n log n)？（10分）

(二)請說明這樣的討論是基於何種計算的模型，為何 Radix Sort 的計算時間低於 O(n log n)？（10分）

答：

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

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

三、定義 2-3trees 並說明 2-3trees 和 AVL tree 在處理 deletion 上的不同之處。

（10分）

答：

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

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

四、在利用 k-way merging 來排序 n 個元素，假設第一次 internal sort 完成後共有 m 個 runs。

(一)在 merge 的過程中，每次都重新比較所有 k 個 runs 的下一個元素（最小值），得到k 個值中的最小值，而後輸出之，則總共需要的比較(comparison) 的次數為何？（10分）

(二)說明如何使用所謂的winner tree，以減少比較次數。總共需要的比較(comparison) 的次數為何？（10分）

答：

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

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

五、請說明 SQL 的組成部分和 relation algebra 之間的關係。

(一) Select Clause（3分）

(二) From Clause（3分）

(三) Where Clause（4分）

答：

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

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

六、請說明 SQL 所支援的3個集合運算以及其使用的語法。（10分）

答：

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

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

七、請說明 Merge-Join 的做法下，如何處理兩個 relations 間的natural join。（10 分）

答：

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

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

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

九十年特種考試台灣省及福建省基層公務人員考試試題    三：22-1    全一頁

等    別：三等考試

科    別：資訊

科    目：資料結構

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

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

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

一、解釋下列名詞：（每小題5分，共20分）

(一)串列走訪 (List traversal)

(二)鄰接矩陣 (Adjacency matrix)

(三)切割征服法 (Divide and conquer approach)

(四)二元樹 (Binary tree)

答：

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

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

二、有一應用需處理零至幾百位數之正整數，並需作加、減、乘、除及比較兩數大小之運算。

(一)請問應採用何種資料結構表示此類正整數較合適？請說明原因。（12分）

(二)試以圖表示下列數字之資料結構。(8分)

答：

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

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

三、請回答下列問題：

(一)試寫出一個遞迴式 (Recursive) 之副程式以計算 n 之階乘 (Factorial)。(n為一自然數)。（12分）

(二)試利用一堆疊 (Stack)，逐步列出在使用上述副程式計算 5! 時，堆疊內所儲存之運算資料的變化過程 (即忽略堆疊中所儲存之返回位址 (Return address) 等與流程控制相關之控制資料)。（8分）

答：

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

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

四、英文字“Reviver”從前面或從後面讀過去，其順序均相同，此種字稱為迴文 (Palindrome)，請利用 Stack 寫一演算法來判斷一英文字是否為迴文。（20分）

答：

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

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

五、請回答下列問題：（每小題5分，共20分）

(一)何謂有序樹 (Ordered tree)？

(二)何謂延伸二元樹 (Extended binary tree)？

(三)請以下圖的二元樹說明，如何以一連續性的記憶體儲存該樹。

(四)如何計算第 (三) 題中任一節點的左子節點及右子節點位址。

答：

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

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