Re: [理工] [資結]台大96-電機丙

看板Grad-ProbAsk作者 (小犬)時間15年前 (2011/02/06 23:31), 編輯推噓4(4推 0噓 20→)
留言24則, 7人參與, 最新討論串2/2 (看更多)
線代總算突破Vector Space和線性映射的無字天書區， 來幫忙解個演算法qqqqqqqqqq 應該一定會有錯，所以請幫忙揪出錯誤！ ※ 引述《starbury8 (馬不理不思議)》之銘言： : http://www.lib.ntu.edu.tw/exam/graduate/96/96412.pdf : 請問5,6要怎麼判斷?? : 我分別是寫D,C : 還有9,14題 : 以及11的(B)選項 : 謝謝!! 5. 我的想法是這樣的 假設c(n)表示fib(n)「包含其自己在內」，所有fib()的Function Call次數 則透過程式碼的觀察，我們可以得到 c(n) = c(n-1) + c(n-2) + 1 且c1 = 1, c2 = 1 是可以透過離散的遞迴公式去算，但這題是fib(10) 所以可以考慮硬爆結果，得到c(10) = 109（寫過程式了，應該沒錯） 另外請問一下解題的大家，「fib(10) 本身」到底算不算一次Recursive call? 我看了一下後面那題，應該是不算，所以是d沒錯吧？ 6. 這樣先從執行的順序去考慮。考慮把這個遞迴畫成一張圖： 10 / \ 9 8 / \ 8 7 / \ 7 6 (省略...)/ / / \ 4 3 / \ 3 2 / \ 2 1 （樹不是Complete？沒錯，這是故意的，見下面說明） 10的左子樹9，右子樹8表示fib(10)會先呼叫fib(9)再呼叫fib(8)，然後再return自己 於是我們可以把它執行的順序想像成是postorder的順序 所以最先執行到的會是最下面且最左邊的fib(2) 於是我們可以用postorder的順序去慢慢看這是怎麼一回事 fib(2)和fib(1)會先執行，同時他們的值會被記下，然後就換fib(3)了 fib(3)執行完換fib(2)，但他的值已經被記得了，可以直接拿下來！ 所以就不用重算一遍。於是跳到上一層的fib(4)繼續... 然後透過觀察，可以注意圖中右子樹的值在執行到之前都已經被記錄下來了 因此最後畫出來的圖就像圖上這樣，除了樹根以外有16個節點，選(c) 9. 我猜(b)(c)(e) 我的理論如下，不太肯定(e)，歡迎糾正我： (a) X，size是root中所有後代的數量再加一（root自己也要算） (b) O，深度定義是到root的路徑長，x為y的後代，所以x會擁有較大的深度 (c) O，T包含S，S包含R，所以T會包含R吧？（爛講法） (d) X，不對：對一個n-元樹而言，Full指的是所有非葉子的節點都有n個兒子 題目給的是對Perfect tree的定義 (e) O，假設原來是一個高度為n的Complete tree 假如他Level n完全沒有右子樹的後代，那他的右子樹就是高n-2的Perfect tree 反之，他的右子樹就是高為n-1的Complete tree 這題是圖論問題 Orz，建議你趕快找本離散來看？ 11. (b)我猜是True 考慮以下圖，應該會是Size最小的可能... ○ / \\\\ 高=1 ○ [d-1個節點] / 高=2 ○ ... / / ○ 高=h 樹根有最大的Degree d，因此樹的Degree是d 這樣的樹size是h+(d-1)+1，所以應該是True 14. (b)(d)(e)，我對這題有點怕怕的，搞不好有很多陷阱... (a) X，根據不同Order的定義這題的答案會不一樣，但應該都是X 假若採用Knuth的定義，Order為2的B-tree就會是一顆Binary Tree 但考慮以下Order=2的B-Tree，其不為Full Binary Tree: 5 / 3 假若「Order是每個節點中最少需要的Key」 那這棵樹根本就不會是Binary Tree 我原來的解法把Degree和Order搞混了... Orz (b) O，Binary Search Tree的基本規則 (c) X，"trie"就是"prefix tree"（請找Huffman algorithm的介紹） 顯然不是一棵平衡樹 (d) O 2-3 Tree有平衡機制 (e) O 紅黑樹有平衡機制（還很難記！ Q____Q） -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.127.180.190
→
02/07 00:01, , 1F
14.(a) order為2不是表示說key為0~1 指標為1~2嗎@@?
02/07 00:01, 1F
→
02/07 00:09, , 2F
Order 2 的 B-Tree 不是 2-3-4 Tree
02/07 00:09, 2F
→
02/07 00:18, , 3F
Order m = 2 可為分支度為 1 或 2
02/07 00:18, 3F
我把Order跟Degree徹底地搞混了........ Orz 我以為是Degree = 2，感謝 看了一下Wikipedia，Order竟然有三種定義，看樣子是Knuth(1993b)的定義比較主流？ 試著更正了，再有錯請跟我說一下 ※ 編輯: ybite 來自: 122.127.180.190 (02/07 00:48)
推
02/07 00:39, , 4F
謝謝你 你的5 6 11 14都跟我寫的一樣XD
02/07 00:39, 4F
→
02/07 00:40, , 5F
讓我更相信應該是手邊的解答錯了XD
02/07 00:40, 5F
→
02/07 00:41, , 6F
不過離散和資結對於full的定義似乎不一樣?
02/07 00:41, 6F
→
02/07 00:41, , 7F
9(c)(d)還有一點疑慮 手邊的答案這兩個選項都沒有
02/07 00:41, 7F
推
02/07 00:44, , 8F
可以順便幫我看一下離散的18題嗎 上面幾篇 謝謝
02/07 00:44, 8F
→
02/07 01:00, , 9F
B-tree應該terminal node都要在同一 level上吧,我覺得a
02/07 01:00, 9F
→
02/07 01:00, , 10F
有可能是對的
02/07 01:00, 10F
→
02/07 01:23, , 11F
我也覺得(a)真的很可疑...
02/07 01:23, 11F
推
02/07 01:52, , 12F
14題e選項 紅黑樹會平衡嗎 我可以造出不平衡的耶
02/07 01:52, 12F
→
02/07 01:53, , 13F
14題A選項是對的 可以在資料結構原文書上找到
02/07 01:53, 13F
推
02/07 03:24, , 14F
14(a)雖然所有終端節點都會在同一 Level，但不一定每個都有
02/07 03:24, 14F
→
02/07 03:24, , 15F
節點分支度都為 2 呀
02/07 03:24, 15F
→
02/07 03:27, , 16F
14. bde
02/07 03:27, 16F
→
02/07 10:25, , 17F
抱歉離散那題我不太會qqqq
02/07 10:25, 17F
→
02/07 15:32, , 18F
上面我說錯了，正確是 All B-Tree of order 2 are FBT.
02/07 15:32, 18F
→
02/07 21:23, , 19F
如果是True的話那我的反例是錯的嗎？ Orz 我得想想
02/07 21:23, 19F
→
02/03 15:07, , 20F
第五題我認為fib(2)的值不會被記得 因為他在return 1
02/03 15:07, 20F
→
02/03 15:07, , 21F
時 就已經離開程式了
02/03 15:07, 21F
→
02/03 15:17, , 22F
14(d)"2-3"樹不是blanced "binary" tree吧?
02/03 15:17, 22F
→
02/03 15:18, , 23F
他可以有2~3個children(非root) 有看到此篇麻煩幫一下
02/03 15:18, 23F
→
09/11 14:13, , 24F
抱歉離散那題我不太會q https://daxiv.com
09/11 14:13, 24F
‣ 更多 ybite 的文章
文章代碼(AID): #1DJhxVw8 (Grad-ProbAsk)
‣ 更多 ybite 的文章
文章代碼(AID): #1DJhxVw8 (Grad-ProbAsk)