[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
一、有一個 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
這是我在考試時想到的概念，可是因為計算有點複雜結果沒能算出來...
反而還在考試中浪費了一堆時間...
回到家之後花一點時間想想，覺得這個想法應該沒錯，
可是計算也太花時間 = ="
不知道有沒有大大這題有寫出來的?
想知道是我概念錯誤還是純粹計算太慢?
還是有比較容易的解法?

我寫完1,2小題就先寫後面的題目了，寫完才回來寫這一題，可是時間不夠我推算，我就寫一般矩陣的公式，因為其實他題目說的任意i,j 並沒有說是上三角放法，所以我就let it be了 哈哈 有寫總比沒寫好

概念是對的,我如果是老師還是會給分(但我不是XD)有高手能分享樹的最後一小題舉例要怎麼舉嗎?我想了半天湊不出來(思想貧濟...)

樹那個很好舉，我是某個左邊子樹換到右子樹，驗算一下就ok這題便宜阿，我是第二題不小心把^號想成跟x號同等級了實際比+號還小，一整個超噢的，窺這題超麻煩的，驗算很多次

不是要舉兩個嗎@_@(是說我連一個也舉不出來,臨時反應差)

先找根是誰，之後兩兩一組或三三一組排看看，就出來了

恩...那就是我要想比較久了,根應該是A吧(印象),再練練

題目說 ^ 是指數耶，權重應該比較大吧不要嚇我啊@@

我記得上三角又有分左上跟右上..XD題意不清可申訴看看..XD，我想出題老師也沒注意到

^優先權比x低???應該是指數比較高吧，而且是右結合