關務三等資料結構：110

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

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

高考三級資料結構：110

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

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

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

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

 

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

代號：10560

頁次：1-1

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

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

考 試 別：關務人員考試

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

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

 

一、大學生只剩5天準備4科 X1, X2, X3, X4，估計的成績點數如下表所示，每1科準備至少1天，使用窮舉法 (exhaustive search) 有幾種可能？如何最適化？最適成績 s =？（20分）

    pic01.png

答：

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

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

 

二、(一)求下列遞迴函數值 f(3) =？（10分）

        int f(int n) { if(n == 0) return 0；else return f(n-1)+n*n; }

    (二)求遞迴函數 f(n) =？,∀n ∈ N（10分）

答：

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

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

 

三、∀k ∈ N-{1}，若有一棵 k 元樹 (k_ary tree) 其中分支度 (degree) 為 i 的節點數為 i 個，i = 1, 2, ..., k，請問該 k 元樹其葉節點數 L(k) 為何？（15分）

答：

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

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

 

四、密文 (Cipher text or Cypher text)：明請到家玩天你我來，應用環狀串列 (circular linked list)，請問明文 (Plain text or Clear text) 為何？（15分）

答：

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

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

 

五、(一)如下圖設背包限重100，有 A、B、C、D、E 共五個不可分割物件，請 問依貪婪策略 (Greedy Algorithm)，0_1 整數背包問題 (knapsack problem) / 貨物裝載問題 (cargo loading problem) 其最大利益為何？其對應的0_1整數規劃為何？（20分）

    (二)有 A、B、C、D、E 共五個可分割物件，請問依貪婪策略，0_1 分數背包其最大利益為何？（10分）

        pic02.png

答：

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

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

 

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

代號：30760

頁次：2-1

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

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

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

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

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

 

一、在大數據分析的應用中，許多資料集是以稀疏矩陣 (Sparse matrix) 的方式呈現，如：客戶的購物行為等。這些資料集共同的特性是資料維度大，但其中的資料量相對稀少，若直接以傳統陣列結構來儲存資料，將會造成大量的空間浪費。請以 C 語言完成下列問題要求：

    (一)設計一有效的二維稀疏矩陣資料結構，避免儲存不存在 (或其值為0) 的資料，有效利用空間。（5分）

    (二)使用所設計的資料結構，完成矩陣的轉置 (Transpose) 運算函式。（10分）

    (三)使用所設計的資料結構，完成維度分別為 m×n 的 A 矩陣與 n×l 的 B 矩陣之矩陣相乘 (Multiply) 運算函式。（10分）

答：

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

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

 

二、一有向圖形 (directed graph) G = (V, E) 如下：

        pic03.png

    (一)請以相鄰矩陣 (adjacency matrix) 表達有向圖形 G。（5分）

    (二)設計一演算法找尋圖形中所有端點 (node) 對端點的最短路徑 (all-pairs shortest path)，並以有向圖形 G 的相鄰矩陣為例說明所使用演算法的計算過程。（15分）

    (三)請說明在上述(二)中所使用演算法的時間複雜度 (time complexity) 為  何？（5分）

答：

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

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

 

三、對資料庫系統的檔案儲存結構而言，必須能夠隨著檔案資料的增多，動態的新增儲存區塊 (block)，例如：B-tree 樹狀檔案資料結構，即可隨著資料量變大而增加葉節點區塊 (leaf node block) 或增加樹的高度來因應。下列為 m = 5 (5way) B-tree 的現況，目前已存有13筆資料：

    (一)請問具有 K 層以上 m = 5 結構的 B-tree 至少可以存放多少筆資料？（5分）

    (二)請畫出完成運算 insert(7) 與 insert(28) 後的 B-tree 結構。（10分）

    (三)完成上述(二)之後接續畫出先後完成運算 insert(15) 與 insert(6) 的 B-tree 結構。（10分）

        pic04.png

答：

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

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

 

四、霍夫曼碼 (Huffman code) 是具有最佳編碼的資料壓縮方法之一，今有下列 的訊息欲以霍夫曼碼編碼傳遞以節省訊息量

                “PAPAYA_AND_BANANA_ARE_YUMMY”

    其中空格 ‘_’ 亦需計算在訊息量內。

    (一)請以該訊息詳述構建霍夫曼碼演算法的過程與結果。（20分）

    (二)依步驟說明所使用演算法的時間複雜度 (time complexity)。（5分）

答：

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

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

 

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

代號：37950

頁次：2-1

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

類    科：資訊處理

科    目：資料結構

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

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

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

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

 

一、A 為 (8×4) 矩陣、B 為 (4×10) 矩陣、C 為 (10×3) 矩陣、D 為 (3×20) 矩陣、E 為 (20×4) 矩陣，(一)請列出此5個矩陣相乘 A×B×C×D×E 所有可能的乘法順序 (請用括號表示乘法順序)。（5分）(二)請使用 Dynamic Programming (動態規劃) 的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序 (請用括號表示乘法順序)，使得五個矩陣相乘所需要花費的乘法數量最少。（15分）(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）

答：

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

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

 

二、假設收銀機內銅板的集合 S = {$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額 W = $75。(一)請設計一個 Greedy (貪婪) 的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W = $75 的過程。（15分）(二)此 Greedy 演算法適合使用何種資料結構來完成。（5分）(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分）

答：

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

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

 

三、二元搜尋法 (binary search) 使用 divide-and-conquer (分而治之) 演算法技巧，對一個已排序的 (sorted) 且長度為 n 的陣列 A[0:n-1]，以二元化方式進行資料值 x 的搜尋，其最差時間複雜度 (worst case time complexity) 可降到θ(log n)。(一)請使用 C++ 或 Python 語言，修改此二元搜尋法，使其能對未排序的 (unsorted) 且長度為 n 的陣列 A[0:n-1]，進行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜尋，如果找到則回傳1，如果找不到則回傳0。（17分）（注意：請寫一個 searching 類別，內含一個 search 功能）(二)請分析修改後的三元化搜尋法其最差時間複雜度 (worst case time complexity) 以 order 的方式表示。（8分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）

答：

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

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

 

四、(一)請使用 C 語言寫一副程式 void FindMeanAverage(int A [ ], int n, int * mean, int * average)，對一個未排序的 (unsorted) 且長度為 n 的陣列 A[0:n-1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average 運算複雜度。（17分）(二)請舉例說明此副程式最差情況 (worst case) 所花費的運算複雜度。（8分）（注意：請加註解說明程式碼作法。）

答：

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

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

 

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

代號：18160

頁次：2-1

110年公務、關務人員升官等考試、110年交通事業公路、港務人員升資考試試題

等    級：薦任

類 科（別）：資訊處理

科    目：資料結構

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

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

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

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

 

一、請試述下列名詞之意涵：（每小題5分，共20分）

    (一) B+ 樹 (B+ Tree)

    (二)完美雜湊函數 (Perfect Hash Function)

    (三)霍夫曼編碼 (Huffman Coding)

    (四)拓撲排序 (Topology Sort)

答：

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

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

 

二、給定一個環狀鏈結串列，節點資料結構宣告如下：

    struct node {

        char info;

        struct node *next;

    };

    typedef struct node NODE;

    請用 C 語言或類似虛擬語言 (pseudo code) 寫出 void swapnodes(NODE *p)函式將兩個指定節點位置交換，過程中不能更動節點內info 內容，僅能修改節點內 next 指標，且兩個節點交換後仍保持環狀鏈結串列。

    (一)將指標 p 之後面連續兩個節點位置交換，如下圖所示。（15分）

         pic05.png

    (二)將指標 p 之前後節點位置交換，如下圖所示。（15分）

         pic06.png

答：

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

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

 

三、二維平面空間內包含資料節點，編號為1到11。依編號由小到大加入此二維平面空間。節點1加入時，將空間分割為左右兩個二維空間。之後每加入一資料節點時，若包覆此節點二維空間為前次分割為上下空間，則此次分割為左右空間；反之，則此次分割為上下空間。左圖顯示加入6個資料節點後之空間分割結果，右圖顯示對應的二元樹。若繼續加入節點7到11。（每小題10分，共20分）

    (一)此二維空間平面分割結果將為何？

    (二)對應的二元樹將為何？

                pic07.png

答：

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

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

 

四、給予如下之加權雙向圖，邊上的加權值表示此邊的成本。

                pic08.png

    (一)使用 Kruskal’s algorithm 找最小成本擴張樹 (Minimal Cost Spanning Tree, MST)。執行過程中，將邊 (edge) 逐步加入此 MST 之順序為何？請以邊所對應的兩端節點表示此邊。（5分）

    (二)使用 Prim’s algorithm 找出最小成本擴張樹 (MST)，從節點 a 出發。執行過程中，將邊 (edge) 逐步加入此 MST 之順序為何？請以邊所對應的兩端節點表示此邊。（5分）

    (三)使用 Dijkstra’s algorithm 找出從節點 a (來源節點) 到其五個節點 (目的節點) 之最短路徑 (shortest path)。執行過程中，逐步找出最短路徑的目的節點順序為何？從節點 a 到目的節點之最短路徑被找出表示演算法不再檢視此目的節點之其它可能最短路徑。（10分）

    (四)來源節點 a 出發到其他五個目的節點之最短路徑走法與成本分別為何？（10分）

答：

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

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

 

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

代號：01310

頁次：2-1

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

等    別：高等考試

類    科：資訊技師

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

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

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

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

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

 

一、請試述下列名詞之意涵：（30分）

    (一) Apriori-property

    (二) Bucket-Sort

    (三) False-negative (type-2 error)

    (四)叢集索引

    (五) Database normalization

    (六) Suffix Tree

答：

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

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

 

二、在一個空堆疊 (Heap) 中插入一串數字5, 8, 2, 3, 9, 4, 7, 10, 1, 6。如果此堆疊是最大堆積 (max-heap)，(一)請根據插入數字順序描述堆疊成長過程。(二)並根據此堆疊呈現堆積排序法 (Heap-Sort) 在輸出前兩大數字時的過程。（20分）

答：

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

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

 

三、一個動物分類資料庫如下表。“Name” 為動物名稱，“Give Birth”，“Can Fly”，“Live inWater”，“Have Legs” 是四個屬性，最後一欄為類別 (Class)。(一)請使用 naïve Bayes 方法來計算與預測一筆測試資料其屬性為 “Give Birth” = Yes，“Can Fly” = no，“Live in Water” = Yes，and “Have Legs” = no 的類別。(二)此方法在分類上容易因資料不足造成何種問題？（20分）

            pic09.png

答：

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

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

 

四、根據以下模擬1922實名制簡訊關聯資料表架構，寫出不同查詢的 SQL 表示。

    Location (LID, LPID, Lname) // 位置編號，位置上層編號，位置名稱

    Message (MID, phoneNum, LID, Date) // 1922簡訊

    其中 LPID 為 LID 的更上層區域編號，若 LPID 為0 則無上層區域，如：某甲單位上層區域為臺北市，系統會有兩筆 Location 資料 (10, 1, 甲)，(1, 0, 臺北市)。

    (一)查詢所有在2021/5/10當天出現在 LID = 10 位置超過兩次以上的電話號碼。（5分）

    (二)查詢LID = 10 位置在2021/5/10至2021/5/17間與電話號碼09XX555666到訪日期均相同的所有電話號碼。（5分）

    (三)查詢電話號碼09XX555666 在2021/5/10至2021/5/17有出現過的所有上層區域。（5分）

    (四)查詢與電話號碼09XX555666在2021/5/10共同出現在同樣上層區域的所有電話號碼。（5分）

    (五)請論述在真實實名制資料庫設計中，有可能遇到的查詢效能問題為何？並描述可能解決方法。（10分）

答：

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

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

 

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

代號：34280

頁次：3-1

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

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

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

 

一、(一)請分別寫出下圖二元樹的前序走訪法 (preorder traversal)、中序走訪法(inorder traversal)、後序走訪法 (postorder traversal) 的結果（6分）

    (二)請在無法預知二元樹的節點數條件下，設計在程式中表示二元樹的資料結構。再假設二元樹已依前述結構儲存在程式，設計一副程式 (或函式)的演算法，在提供樹根給此副程式 (或函式) 後，其執行二元樹中序走訪法的程序並輸出走訪結果。此副程式 (或函式) 不可使用遞迴呼叫技術但可添加其他資料結構，演算法的時間複雜度和空間複雜度須均為O(n)，n 為二元樹的節點個數。演算法可以虛擬碼 (pseudocode) 或以高階語言如 C 呈現。需分析說明副程式 (或函式) 演算法的時間複雜度和空間複雜度均為 O(n)。（提醒：若用遞迴呼叫技術設計，演算法部分不給分）（13分）

    (三)請分別說明在程式執行過程，以第(二)子題非遞迴呼叫技術設計相較於以遞迴呼叫技術設計在時間與空間的效能優勢各為何？（6分）

                        pic10.png

答：

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

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

 

二、二維方陣 A 大小為 n×n，方陣中的元素除了主對角線之元素以及緊鄰它的上下兩條對角線之元素的值可能不為零外，方陣 A 其他元素之值一定為零，以5×5方陣為例如下圖。請以一維陣列 B 設計儲存此方陣 A 之結構，陣列 B 之索引值自0開始，且陣列 B 的元素數量須小於或等於3×n-2。設計的結構須包含如何有效率地決定儲存方陣 A 之元素 aij 以及如何自陣列 B 中取得或決定方陣中元素 aij 值，其中0 ≤ i, j ≤ n-1 而 i 與 j 分別為元素在方陣 A 中之列號與行號。（20分）

    pic11.png

答：

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

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

 

三、(一)請畫出下圖以鏈結串列 (link list) 為基礎的相鄰串列 (adjacency list) 結構表示之結果。（5分）

    (二)請運用一維陣列設計一資料結構採循序串列 (sequential list) 架構，其仍舊以類似子題(一)相鄰串列策略表示無向圖 (undirected graph) 節點與邊的關係，但僅以一維陣列呈現第(一)子題之相鄰串列概念。圖之節點與邊的關係僅以此一維陣列元素記錄並呈現，不可使用其他資料結構，另外，陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個數；除了說明資料結構外，也請寫出下圖以此資料結構表示之一維陣列結果。（8分）

    (三)請列出兩項在程式中以第(一)子題之以鏈結串列 (link list) 表示圖比以第(二)子題一維陣列表示圖適合的應用情境或效能優勢。另外，也請列出兩項在程式中以第(二)子題一維陣列表示圖比以第(一)子題鏈結串列(link list) 表示圖適合的應用情境或效能優勢。（12分）

                        pic12.png

答：

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

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

 

四、區間堆積 (interval heap) 是一種優先佇列 (priority queue)，請回答下列相關的問題。

    (一)從一個沒有元素的區間堆積開始，依序插入40, 30, 60, 15, 14, 19, 80, 12, 90等元素。請畫出最後區間堆積的樹狀結構圖。（9分）

    (二)請自第(一)子題建構的區間堆積中刪除元素12，並畫出刪除該元素後區  間堆積的樹狀結構圖。（3分）

    (三)請以一維陣列設計資料結構儲存區間堆積，該資料結構可以透過節點對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子節點 left、右子節點 right 與兄弟節點brother 等在陣列中的索引值。假設此一維陣列之起始索引值為0，請列出由 index 構成的計算 parent、left、right、brother 的數學式。並請畫出以此一維陣列儲存第(一)子題建構完成的區間堆積的結果。（12分）

    (四)舉例並說明一既需要提供最高優先元素，也需要提供最低優先元素的優先佇列的應用實例或系統。（6分）

答：

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

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

 

 

arrow
arrow
    文章標籤
    資料結構
    全站熱搜
    創作者介紹
    創作者 jacksaleok 的頭像
    jacksaleok

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

    jacksaleok 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄