103年 - 103年高員三級資料結構#43470

科目：公職◆資料結構 | 年份：103年 | 選擇題數：0 | 申論題數：9

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (9)

⑴試以最少的記憶體儲存之，請說明應用何種資料結構？（5 分）

⑵總共用多少記憶體空間？（5 分）

⑶若矩陣第一個元素（0,0）在位址 S，請分別以 Row-Major 及 Column-Major Ordering 寫出矩陣任意元素（i, j）所在位址的表示式。（10 分）

二、請將下列運算式由中序（Infix）改為後序（Postfix）及前序（Prefix）表示法，（A-B）^（X+D）^（Y-4%H）*G-6/（F+2）+C。其中 ^為指數運算符號、%為取餘數運算符號。（10 分）

三、已知有一個二元樹的前序搜尋（Preorder）結果為“ABDGHCE”，且其後序搜尋（Postorder）結果為“GHDBECA”。⑴請問由前述二個結果，是否可以得到唯一的二元樹（4 分）？⑵前小題若為是，請畫出此唯一的二元樹；否者，請畫出二個二元樹，可得出具有前述前序搜尋與後序搜尋之結果（6 分）。

四、有一組原始的整數序列為 56, 18, 79, 7, 42, 96, 35, 66，請分別以 Insertion sort 及 Quick sort 的方法寫出將此一數列由小到大的排序過程。注意：是寫出排序的過程，不只是排序結果。（20 分）

【已刪除】五、請寫出下列圖形結構的相鄰串列（Adjacent List）（串列順序應依節點編號由小至大表示）（6 分）。並請依此相鄰串列畫出以 S5 為起點之 DFS 展開樹（DFS Spanning Tree）及 BFS 展開樹（BFS Spanning Tree）（14 分）。

【已刪除】六、請推算下圖中，由節點 S 到其他各點的最短路徑長度以及路徑所需經過的節點。（10 分）

【已刪除】七、已知使用 Linked List 為 Stack 的類別（Class）宣告如下，請寫出其 Delete（Pop）的函式（Functions）。（10 分）