加載中. ..
PDF
103年公務人員特種考試警察人員考試
103年公務人員特種考試一般警察人員考試
103年特種考試交通事業鐵路人員考試試題 代號：71070
等 別：高員三級鐵路人員考試
類 科：資訊處理
科 目：資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、有一個 N×N的上三角矩陣，每個元素占一個 Byte。
試以最少的記憶體儲存之，請說明應用何種資料結構？（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 T ree）及 BFS 展開樹（BFS Spanning Tree）（14 分）。
103年公務人員特種考試警察人員考試
103年公務人員特種考試一般警察人員考試
103年特種考試交通事業鐵路人員考試試題 代號：71070
等 別：高員三級鐵路人員考試
類 科：資訊處理
科 目：資料結構
全一張
（
背面
）
六、請推算下圖中，由節點 S 到其他各點的最短路徑長度以及路徑所需經過的節點。
（10 分）
七、已知使用 Linked List 為Stack 的類別（Class）宣告如下，請寫出其 Delete（Pop）
的函式（Functions）。（10 分）
s
xw
t
vy
z
u
1
1
1
1
1
1
1
10
10
10 10
10
10
template T>
class Node {
friend LinkedStack;
private :
T data;
Node<T> *link;
};
template T>
class LinkedStack {
public :
LinkedStack() {top = 0;}
~LinkedStack();
bool IsEmpty() const {return top == 0;}
bool IsFull() const ;
T Top() const ;
LinkedStack& Add(const T& x);
LinkedStack& Delete(T& x);
private :
Node *top; // pointer to top node
};