PTT職涯區 / Examination (國家考試)

Re: [考題] 98年地特四等資料處理概要

看板Examination (國家考試)作者 (開弓)時間13年前 (2013/06/08 18:28), 編輯推噓7(7推 0噓 16→)
留言23則, 5人參與, 最新討論串2/3 (看更多)
早上看到這題就覺得你最後答案有點怪 我自己轉一次之後果然有問題XD 你最後的答案與AVL樹定義不符歐 AVL樹的定義包括其子樹也要是AVL樹才對 不然F(n-2)+1就會不正確了XD 最後答案應該是 24 / \ 20 43 / / \ 12 28 55 這樣才對吧？ 可以問一下為什麼最後會挑28作為旋轉軸心嗎？ ※ 引述《grandoph (跟節拍器不合)》之銘言： : [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處 : 輸入資料為:55、43、20、24、28、12 : (二)建立AVL樹 : 轉換過程:http://ppt.cc/pCaf : 想法: : 我在step5的時候，關鍵因子是20和43 : 補習班是用43，然後用LR轉換 : 我是選20，然後用RR方式轉 : 在step6時再轉一遍 : 請問我的作法有問題嗎?? : 請高手替我解答，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 175.111.51.2 ※ 編輯: ARCHERDEVIL 來自: 175.111.51.2 (06/08 18:35)
推
06/08 18:39, , 1F
可是我覺得補習班老師最後答案是對的,原PO最後少做一個RR
06/08 18:39, 1F
→
06/08 18:40, , 2F
選28去轉是因為其他的用LL轉不了@_@"
06/08 18:40, 2F
→
06/08 18:41, , 3F
前面說錯...原PO少做一個LL(左右不分...)
06/08 18:41, 3F
補習班老師那個答案....XD 我先講，他的答案每個步驟都有符合AVL樹的定義 但是第五步轉成那種畸形樣子我完全沒有概念來想像他怎麼轉的 尤其是28原本在24右子樹位置，然後轉完之後跑到左子樹位置去，整個奇蹟XD 但依然符合定義。 如果完全按照LL、RR、LR、RL方式去轉，原PO到第五步跟我都一樣 然後第六步轉到最後的時候我覺得他選錯軸來轉...就這樣而已 ※ 編輯: ARCHERDEVIL 來自: 175.111.51.2 (06/08 18:47)
→
06/08 18:49, , 4F
因為我在step6時,關鍵因子是43，所以LR把28往上轉
06/08 18:49, 4F
推
06/08 18:49, , 5F
我作起來跟A大的答案一樣!!
06/08 18:49, 5F
→
06/08 18:50, , 6F
還有不用一定要用LL阿 你可以用LR(43,24,28挑24往上轉
06/08 18:50, 6F
→
06/08 18:50, , 7F
grandoph你關鍵因子挑錯了
06/08 18:50, 7F
→
06/08 18:51, , 8F
我的確是在最後一步少轉LL 不過我的根節點是28
06/08 18:51, 8F
下面補一下解法好了 PTT手動排圖好囧阿orz 題目是55, 43, 20 ,24, 28, 12 55 55 / 43 55 / 43 / 20 不符定義，選43開始轉 43 / \ 20 55 43 / \ 20 55 \ 24 43 / \ 20 55 \ 24 \ 28 出現定義不符，選24轉 43 / \ 24 55 / \ 20 28 43 / \ 24 55 / \ 20 28 / 12 又出現定義不符 這時候如果把28往上？ 當然不可能... 因為如果把28往上...就會變成這樣... 28 / \ 24 43 / \ 20 55 / 12 還是不符定義 假設你要看01之類的因子... (1)43 / \ (0)24 55 / \ (1) 20 28(1) / 12 會有點類似這樣（其實我根本不知道因子怎麼表示 但是whatever..... 這時候選24就對了...。 因為當24上去的時候，24以下的左右子樹不會亂跑 然後答案就會回歸到我最後答案的狀態.... ....有人要畫一下-1 0 1 之類的圖嗎？其實wiki也有就是了 但我基本上是覺得那個「非常容易混淆」 所以根本不管因子... 實際上也不用管就是了 只要把定義倍好就一定轉得出來 ※ 編輯: ARCHERDEVIL 來自: 175.111.51.2 (06/08 19:13)
推
06/08 18:55, , 9F
根節點不應該是28 你最後一步應該是往最深的地方作LL
06/08 18:55, 9F
推
06/08 19:11, , 10F
看完講義再做一次結果跟此篇答案一樣了@@"
06/08 19:11, 10F
→
06/08 19:15, , 11F
我本來想解釋一下怎麼選因子，但後來我發現太抽象了
06/08 19:15, 11F
→
06/08 19:15, , 12F
抱歉orz
06/08 19:15, 12F
推
06/08 19:16, , 13F
因子=左子樹高度-右子樹高度~
06/08 19:16, 13F
好吧，被你提醒一下我想起來一件事情 我是這樣判斷的...。 首先我們有一株樹長這樣... 43 / \ 24 55 / \ 20 28 / 12 把這棵樹改一下會變成 12 — 20 — 24 — 43 — 55 ｜ 28 這樣就懂了吧XD (2) (1) (0) (1) (2) 12 — 20 — 24 — 43 — 55 ｜ 28(1) 所以選24當作總根..... 讓我解釋的話就會是這樣... ※ 編輯: ARCHERDEVIL 來自: 175.111.51.2 (06/08 19:24)
→
06/08 20:02, , 14F
原po你把43當關鍵轉的時後... 應該是43 24 28 要轉吧
06/08 20:02, 14F
→
06/08 20:02, , 15F
我剛剛看了一下.... 你該不會是逆時針轉...
06/08 20:02, 15F
→
06/08 20:03, , 16F
所以28 上去，然後24跟42分別成為28的左右子節點...？
06/08 20:03, 16F
→
06/08 20:04, , 17F
如果是這樣的話你挑關鍵搞不好沒問題，只是轉錯方向..
06/08 20:04, 17F
推
06/08 20:18, , 18F
推A大真熱心！
06/08 20:18, 18F
→
06/08 20:35, , 19F
這種題目可能有多種旋轉方式嗎？若最後都符合定義？
06/08 20:35, 19F
→
06/08 20:41, , 20F
實做跟畫圖不一樣。實做上 可能。因為最後定義對就對
06/08 20:41, 20F
→
06/08 20:41, , 21F
至於畫圖... 你知道學理派的老頭通常都很頑固的XD
06/08 20:41, 21F
→
06/08 20:42, , 22F
asdd 我就當順便複習了XD
06/08 20:42, 22F
推
06/08 20:58, , 23F
這題有解到我的盲點!! 推~
06/08 20:58, 23F
‣ 更多 ARCHERDEVIL 的文章
文章代碼(AID): #1HimS-7A (Examination)
Examination 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ARCHERDEVIL 的文章
文章代碼(AID): #1HimS-7A (Examination)