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

看板Examination作者bloodyaugust (bloodyaugust)時間11年前 (2014/06/18 20:16)推噓4(4推 0噓 14→)

留言18則, 5人參與討論串1/1

[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處一、有一個 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

06/18 20:52, , 1^F

06/18 20:52, 1^F

→

lordfish62

06/18 20:53, , 2^F

06/18 20:53, 2^F

→

lordfish62

06/18 20:53, , 3^F

06/18 20:53, 3^F