104年 - 104年身障特考三等資料結構#42783

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

試卷資訊

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

選擇題 (0)

申論題 (11)

⑴ 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，

試問：1.以最小化儲存空間為目標，宜採用何種方式儲存？（5 分）2.承上，需要

多少空間？（5 分）3.承上，若以行為主儲存，則在 i<j 時，請推導 aij 儲存的位

置。（5 分）

五、在一單向鏈結串列中，若節點的定義為： 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）