關於鐵路特考高員三級資料結構第一題 - 考試

[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處


一、有一個 N ×N 的上三角矩陣，每個元素占一個Byte。

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

(2) 總共用多少記憶體空間？（5 分）

(3) 若矩陣第一個元素（0,0）在位址S，請分別以 Row-Major 及

Column-Major Ordering 寫出矩陣任意元素（i, j）所在位址的表示式。（10 分）



(1) 應該是以一維陣列就可以了。

1 2 3
0 4 5 => [1,2,3,4,5,6]
0 0 6


(2) 記憶體只需要 N(N+1)/2 Bytes



(3) 這題就有點可怕了...



Row- Major:

0 1 2 3
4 5 6
7 8
9

應該是 S + 正常矩陣的位置 - 空格的三角形位置

=> S + (Ni + j) - i(i + 1)/2






Column- Major:

0 1 3 6
2 4 7
5 8
9


應該是 S + 正常矩陣的位置 - 空格的梯形位置

=> S + (i + Nj) - (2N - j - 1)j/2





這是我在考試時想到的概念，可是因為計算有點複雜結果沒能算出來...

反而還在考試中浪費了一堆時間...

回到家之後花一點時間想想，覺得這個想法應該沒錯，

可是計算也太花時間 = ="

不知道有沒有大大這題有寫出來的?

想知道是我概念錯誤還是純粹計算太慢?

還是有比較容易的解法?



--