第1題
請以C, C++, C#, Java 或Python 撰寫2 個方法，一個以迴圈方式，一個 以遞迴方式，對存在singular linked list 的資料進行linearly search。假設 Node 的結構如下：（12 分）
民國112年 地方三等 資訊處理 資料結構考古題
民國112年 地方三等 資訊處理 資料結構收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。
官方資料
題目與答案
第2題
請為數列0, 10, 30, 20, 50, 80, 40, 90, 70, 60 建立AVL tree, Min/Max heap, 2−4 tree，並依它們的性質以yes or no 完成下表。註：所建立的tree or heap 請以圖示，如果是Searching Tree，請以左小右大的方式建立。（24 分） Balance Searching Tree AVL tree Min heap Max heap 2−4 tree
第3題
請以如下的Huffman Tree 所做的數字編碼，解讀01010111110100100011 編碼對應的數字。（10 分）
第4題
針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的cost），依 如下BFS（配合queue）與DFS（配合stack）演算法，進行所有節點的 走訪，多個節點可以走訪時，以連線上cost 較低者優先，結果請以迴圈 內部的顯示要求，依下表形式填入（stack 垂直表示，開口在上方，queue 水平表示，出口在左，入口在右）。註：假設節點S 為起始點。（24 分） BFS 演算法Loop1 … DFS 演算法Loop1 … print node print node queue Stack processSet processSet BFS/DFS 演算法（/前為BFS 使用queue, /後為DFS 使用stack） Step1: set queue/stack to empty set processSet to empty Step2: enqueue/push S and add S into processSet Step3: while queue/stack is not empty Step31: dequeue/pop and print it Step32: enqueue/push all one step neighbors which are not in processSet according to the cost of edges and add them into processSet Step33: display content of queue/stack and processSet
第5題
請完成下列表格有關排序演算法的time complexity（假設排序資料有n 個，資料位數有d 個）、是否為In−Space 演算法、是否為Stable 演算法 及範例數列50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分） 排序演算法 Time Complexity In−Space （Yes/No） Stable （Yes/No） 降冪比較次數 Best Worst 50, 46, 37, 28, 19 Bubble Insertion Merge（奇數時， 後半段多1） Quick（第一個當 pivot） Radix（base 10） Selection