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

[bloodyaugust (bloodyaugust)]

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


一、有一個 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





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

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

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

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

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

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

還是有比較容易的解法?



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.223.55.206
※ 文章網址: http://www.ptt.cc/bbs/Examination/M.1403093807.A.D36.html
※ 編輯: bloodyaugust (61.223.55.206), 06/18/2014 20:18:34
推 lordfish62:我寫完1,2小題就先寫後面的題目了，寫完才回來寫這一
→ lordfish62:題，可是時間不夠我推算，我就寫一般矩陣的公式，因為
→ lordfish62:其實他題目說的任意i,j 並沒有說是上三角放法，所以我
→ lordfish62:就let it be了 哈哈 有寫總比沒寫好
→ fatty3321:概念是對的,我如果是老師還是會給分(但我不是XD)
→ fatty3321:有高手能分享樹的最後一小題舉例要怎麼舉嗎?
→ fatty3321:我想了半天湊不出來(思想貧濟...)
推 s89922:樹那個很好舉，我是某個左邊子樹換到右子樹，驗算一下就ok
→ s89922:這題便宜阿，我是第二題不小心把^號想成跟x號同等級了
→ s89922:實際比+號還小，一整個超噢的，窺這題超麻煩的，驗算很多次
→ fatty3321:不是要舉兩個嗎@_@(是說我連一個也舉不出來,臨時反應差)
推 s89922:先找根是誰，之後兩兩一組或三三一組排看看，就出來了
→ fatty3321:恩...那就是我要想比較久了,根應該是A吧(印象),再練練
→ bloodyaugust:題目說 ^ 是指數耶，權重應該比較大吧
→ bloodyaugust:不要嚇我啊@@
→ futureq:我記得上三角又有分左上跟右上..XD
→ futureq:題意不清可申訴看看..XD，我想出題老師也沒注意到
推 lordfish62:^優先權比x低???應該是指數比較高吧，而且是右結合