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

關務三等資料結構：111

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

鐵路特考高員三級資料結構：無

高考三級資料結構：111

專利商標審查人員三等資料結構：無

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

資訊技師高等資料結構與資料庫及資料探勘：111

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

[一一一年關務三等資料結構]

代號：10560

頁次：1-1

111年公務人員特種考試關務人員、身心障礙人員考試及

111年國軍上校以上軍官轉任公務人員考試試題

考試別：關務人員考試

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、請分別以 big Onotation 表示下列各個小題的時間複雜度 (time complexity)：（每小題10分，共30分）

(一) 2022 n ln n+111 n^1.001

(二) 2022 n³2ⁿ+111 n²3ⁿ

(三) 2022 n!+2ⁿ

答：

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

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

二、遞迴函數 (recursive function) 起始數值與遞迴關係定義為：

P(0) = P(1) = P(2) = 1, P(n) = P(n-1)-2P(n-2)+P(n-3),

n >= 3

(一)請問 P(n) 的前5個值依序為：1, 1, 1，及那兩個數字？（10分）

(二)請問 P(6)+P(8) 的值為何？（10分）

答：

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

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

三、7個工作的利潤及處理的最後期限如下表所示，並假設每個工作的處理時間均為一個時間單位，請求出最適排程及最大利潤 (maximal profit) 為何？（20 分）

答：

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

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

四、以文本 (text) X = “AGTCATTCGATTC”，樣式 (pattern) Y = “ATTC” 兩字串為例，請問使用暴力比較/窮舉法 (exhaustive search) 中的樣式前向法(forward) 及後向法 (backward) 各需比較幾次？（10分）

答：

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

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

五、m, nN，已知三維陣列 (three-dimensional array) A[1:8, 1:9, 1:4] 每一個元素占用2個儲存單元，並且 A[1, 2, 1] 的儲存地址為234，A[2, 3, 1] 的儲存地址是 m，A[2, 3, 4] 的儲存地址為 n。

(一)採用列序為主序 (row major) 方式儲存，則 m、n 分別為何？（10分）

(二)採用行序為主序 (column major) 方式儲存，則 m、n 分別為何？（10分）

答：

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

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

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

代號：30860

頁次：2-1

111年公務人員特種考試關務人員、身心障礙人員考試及

111年國軍上校以上軍官轉任公務人員考試試題

考試別：身心障礙人員考試

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、請回答下列 Big O 的相關問題：

(一) Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在數量上的漸進趨勢。某個問題可採用5個演算法 A~E 求解，各演算法執行時間的 BigO 分別如下：A 為 O(N²)，B 為 O(Nlog(logN))，C為 O(N^1.5)，D 為 O(N²log(N))，E 為 O(SQRT(N))。當 N 很大時，請根據演算法的執行時間，由慢至快排序這5個演算法。（10分）

(二)給定100萬個介於0到100 (含0及100) 的整數，請利用任一種高階程式語言寫出一個 O(N) 的由大至小的排序演算法，並說明此演算法為何是 O(N) 的方法。（15分）

答：

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

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

二、以下7個數字 [21, 1, 16, 11, 25, 9, 35]，要儲存到 Hash Table 中，Hash Table的儲存空間是一個索引從0開始的一維陣列 (Array)。假設 Hash 函數為 H(Key) = (Key*3) mod 7，裝填因子 (Load Factor) 為0.7。

(一)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的線性探測法 (Linear Probing)：增量函數 F(i) = i (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分）

(二)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的平方探測法 (Quadratic Probing)：增量函數 F(i) = i² (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分）

答：

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

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

三、請寫出對以下8個數字 [44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹(Min Heap Tree) 的過程。為方便最小堆積樹的建構，我們通常會使用一個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆積樹的建構。最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小到大的排序過程。請說明此種排序法的計算複雜度 Big O 為何？（25分）

答：

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

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

四、下圖中有4個城市8條公路，公路上的數字表示這條公路的長短。請注意這些公路是單向的。若使用 Floyd Warshall 的動態規劃法求解從任意兩個城市之間的最短路徑，請回答下列問題：

(一)首先將圖的信息建成一個 N*N 的初始距離矩陣，其中 N 是節點的個數，矩陣的各列 (Rows) 代表 From Nodes，矩陣的各行 (Columns) 代表 To Nodes，矩陣中的值則分別代表上圖中從 From Node 到 To Node的距離。（5分）

(二)其次列舉從 D 到 C 的最短路徑求解過程 (需輸出最短路徑的值及路徑)，並說明此方法的計算複雜度 Big O 為何。（15分）

答：

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

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

[一一一年高考三級資料結構]

代號：37250

頁次：3-1

111年公務人員高等考試三級考試試題

類科：資訊處理

科目：資料結構

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

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

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

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、以下是一中序運算式 (Infix expression) 轉換 (Convert) 成後序運算式 (Postfix expression) 的演算法

operstk = the empty stack;

while(not end of input) {

symb = next input character;

if(symb is an operand)

add symb to the postfix string;

else {

while(!empty(operstk) && precedence(stacktop(operstk), symb)) {

topsymb = pop(operstk);

add topsymb to the postfix string;

} /* end while */

if(empty(operstk) || symb != ‘)’)

push(operstk, symb);

else

topsymb = pop(operstk);

} /* end else */

} /* end while */

while(!empty(operstk)) {

topsymb = pop(operstk);

add topsymb to the postfix string;

} /* end while */

其中資料結構：

“operstk”：用來儲存運算子的堆疊 (Stack)；

“stacktop(operstk)”：表示 top 指標所指堆疊 operstk 的運算子；

程序 (Procedures) 或函數 (Functions)：

“empty(operstk)”：檢查堆疊 operstk 是否為空的布林函數；

“pop(operstk)”：從堆疊 operstk 中取出一運算子；

“push(operstk, symb)”：將運算子 symb 存入堆疊 operstk；

“precedence(op₁, op₂)”：布林函數，定義在一沒有左右括弧的中序運算式中，op₁ 運算子出現在 op₂ 運算子的左邊時，當 op₁ 運算子優先順序不低於 op₂ 運算子，則設定成 TRUE，否則為 FALSE。例如，我們給定 precedence(‘*’, ‘+’) = TRUE，precedence(‘+’, ‘+’ )= TRUE，precedence(‘+’, ‘*’) = FALSE，為了處理運算式左右括弧，設定下列的 precedence：

precedence(‘(’, op) = FALSE /* op 為任一運算子 */

precedence(op, ‘(’) = FALSE /* op 為除 ’)’ 外的任一運算子 */

precedence(op, ‘)’) = TRUE /* op 為除 ’(’ 外的任一運算子 */

precedence(‘)’, op) = undefined /* op 為任一運算子 */

以中序運算式 (2+3)*4 為例，執行上述演算法，依處理每一個運算子或運算元時，輸出 postfix string 及 operstk 內容為何 (“eos” 表示end of string)？

（25分）

答：

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

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

二、利用鏈結串列 (Linked list) 實做佇列 (Queues)，給予如下鏈結串列節點及佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x) 程序，將整數值 x 加入 (Insert) 到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode( ) 配置 (Allocate) 一新節點。（25分）

struct node {

int info;

struct node *next;

};

typedef struct node *NODEPTR;

struct queue {

NODEPTR front, rear;

};

struct queue q;

NODEPTR getnode( )

{

NODEPTR p;

p = (NODEPTR)malloc(sizeof(struct node));

return(p);

}

insert(pq, x)

struct queue *pq;

int x;

{

NODEPTR p;

}

答：

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

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

三、一個二元搜尋樹 (Binary search tree) 的前序追蹤 (Preorder traversal) 結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20

請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree (NODEPTR tree)，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25分）

struct node {

int info;

struct node *left;

struct node *right;

} typedef struct node *NODEPTR;

void sortTree(NODEPTR tree) {

}

答：

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

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

四、用 G = (V, E) 表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點(Vertices) 形成邊及對應權重 (Weights) 所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣 (Adjacency matrix) 表示中的值

#define MAX_EDGES 100

typedef struct {

int col;

int row;

int weight;

} edge;

edge a[MAX_EDGES];

已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點0開始依加入其它節點的順序，畫出此圖之最小擴張樹 (Minimum spanning tree)，並計算其最低權重或成本值。（25分）

答：

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

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

[一一一年資訊技師高等資料結構與資料庫及資料探勘]

代號：01310

頁次：2-1

111年專門職業及技術人員高等考試建築師、31類科技師（含第二次食品技師）、大地工程技師考試分階段考試（第二階段考試）暨普通考試不動產經紀人、記帳士考試試題

等別：高等考試

類科：資訊技師

科目：資料結構與資料庫及資料探勘

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

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

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

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

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

(一) Balanced Tree

(二) Record (in database)

(三) Perfect hashing

(四) Entity-Relationship model

答：

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

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

二、什麼是 Open Data？什麼是 Public Data？請說明此兩名詞的不同之處。（16分）

答：

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

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

三、請詳述 (舉例說明) 什麼叫做 Bubble Sort (請以虛擬碼 pseudo-code 表示)，並對您的描述 (pseudo-code) 做效能分析 (說明 big-O 的分析過程)。（20分）

答：

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

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

四、某工廠有以下的兩個表 (Table)：（每小題5分，共20分）

某工廠員工寫了兩個 SQL 語法，如下：

(一)請問 SQL 語法一進行何種的操作 (operations)？

(二)請問 SQL 語法二進行何種的操作 (operations)？

(三)假使我們採用 Table 1 當作語法一的輸入資料，請問會輸出什麼？

(四)假使我們採用 Table1 和 Table2 當作語法一的輸入資料，請問會輸出什麼？

答：

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

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

五、假設某一家店中有以下的六次交易 (transactions)：（每小題8分，共24分）

A：{bread, milk, diapers, juice}

B：{bread, milk, diapers, eggs}

C：{milk, diapers, beer, eggs}

D：{bread, beer}

E：{milk, diapers, eggs, juice}

F：{milk, diapers, beer}

(一)請問產品 diapers 的 support 值為多少？

(二)假設我們設定 support threshold 為0.6，請找出所有的 frequent itemsets。也就是說，U = {bread, milk, diapers, juice, eggs, beer} 這六樣產品的集合，有那些子集合在 A-F 的六個交易中，被採購的機率超過0.6。

(三)假設我們有一個關聯規則 (association rule)：{beer}->{diapers}，請求出 support 值和 confidence 值。

答：

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

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

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

代號：34880

頁次：2-1

111 年特種考試地方政府公務人員考試試題

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、請用 Big-O 符號來表示下列函式的成長速率，並說明之：

(一)T(n) = 3n³+7n³+n³logn（5分）

(二)T(n) = 2T(n/2)+n²（10分）

答：

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

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

二、常用的算術運算式 (Arithmetic Expression) 有：中序運算式 (Infix Expression)、前序運算式 (Prefix Expression)、後序運算式 (Postfix Expression) 三種表示法，考慮下面的算術運算式 (Arithmetic Expression) 並回答下列問題：