加載中. ..
PDF
104年公務人員特種考試關務人員考試、
104年公務人員特種考試身心障礙人員考試及
104年國軍上校以上軍官轉任公務人員考試試題 代號：30860 全一張
（正面）
考 試 別： 身心障礙人員考試
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意： 禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、請計算且說明下列片斷程式中 x = x + 1 的執行次數。（每小題 5分，共 10 分）
k = 100000;
while ( k != 10){
k/=10;
x = x + 1;
}
for (i=1; i<=n; i++) {
k=i+1;
do {
x=x+1;
} while (k++ <= n);
}
二、二維陣列 A(0:m-1,0:n-1)，假設 A(3,2)在1110，而 A(2,3)在1115，若每個元素占一
個空間，請推導 A(1,4)所在的位址。（10 分）
三、若堆疊以陣列 st 儲存，請完成堆疊的插入演算法。（10 分）
其中相關宣告為
int st[0:MAX-1];
int top = -1;
四、有一個 n*n的矩陣 A如圖(1)所示。其中在 i<j 時存有不同的資料，但 i
≧
j時aij=0，
試問：
以最小化儲存空間為目標，宜採用何種方式儲存？（5分）
承上，需要
多少空間？（5分）
承上，若以行為主儲存，則在 i<j 時，請推導 aij 儲存的位
置。（5分）
A =
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
−
0...0000
...0000
......0000
...000
...00
...0
,1
334
22423
1141312
nn
n
n
n
a
aa
aaa
aaaa
圖(1)
104年公務人員特種考試關務人員考試、
104年公務人員特種考試身心障礙人員考試及
104年國軍上校以上軍官轉任公務人員考試試題 代號：30860 全一張
（背面）
考 試 別： 身心障礙人員考試
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
五、在一單向鏈結串列中，若節點的定義為：
class Node{
public int data;
public Node next;
}
請寫出刪除指定節點 p的演算法。（10 分）
註：假設第一個節點為開頭節點（head），不存放任何資料。
六、請寫出圖(2)所示二元樹的前序、中序和後序走訪。（6分）
七、資料 20、30、10、50、60、40、45、5
請建立成一棵 AVL 樹，（6分）
請依序
刪除 60 及30，在推導過程需註明旋轉的類別。（6分）
八、若採雜湊搜尋法中的移位折疊相加法，且 m=1000，請推導鍵值 x=123456789 的儲
存位址在那裡？（5分）
九、請推導圖(3)之拓撲排序。（10 分）
十、有一二維陣列 A(-1:5, -4:2)之啟始位址 A(-3,-4) = 100，以列為主排列，請問 A(1,1)所
在位址？（6分）若以行為主排列，請問 A(1,1)所在位址又如何？（6分）（假設陣
列內元素長度都為 1）
圖(2)
圖(3)