作者ybite (小犬)
看板Grad-ProbAsk
標題Re: [理工] [資結]台大96-電機丙
時間Sun Feb 6 23:31:40 2011
線代總算突破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
→ dy957:14.(a) order為2不是表示說key為0~1 指標為1~2嗎@@? 02/07 00:01
→ koehie:Order 2 的 B-Tree 不是 2-3-4 Tree 02/07 00:09
→ koehie:Order m = 2 可為分支度為 1 或 2 02/07 00:18
我把Order跟Degree徹底地搞混了........ Orz 我以為是Degree = 2，感謝
看了一下Wikipedia，Order竟然有三種定義，看樣子是Knuth(1993b)的定義比較主流？
試著更正了，再有錯請跟我說一下
※ 編輯: ybite 來自: 122.127.180.190 (02/07 00:48)
推 starbury8:謝謝你 你的5 6 11 14都跟我寫的一樣XD 02/07 00:39
→ starbury8:讓我更相信應該是手邊的解答錯了XD 02/07 00:40
→ starbury8:不過離散和資結對於full的定義似乎不一樣? 02/07 00:41
→ starbury8:9(c)(d)還有一點疑慮 手邊的答案這兩個選項都沒有 02/07 00:41
推 starbury8:可以順便幫我看一下離散的18題嗎 上面幾篇 謝謝 02/07 00:44
→ dy957:B-tree應該terminal node都要在同一 level上吧,我覺得a 02/07 01:00
→ dy957:有可能是對的 02/07 01:00
→ ybite:我也覺得(a)真的很可疑... 02/07 01:23
推 cksh3300110:14題e選項 紅黑樹會平衡嗎 我可以造出不平衡的耶 02/07 01:52
→ cksh3300110:14題A選項是對的 可以在資料結構原文書上找到 02/07 01:53
推 koehie:14(a)雖然所有終端節點都會在同一 Level，但不一定每個都有 02/07 03:24
→ koehie:節點分支度都為 2 呀 02/07 03:24
→ koehie:14. bde 02/07 03:27
→ ybite:抱歉離散那題我不太會qqqq 02/07 10:25
→ koehie:上面我說錯了，正確是 All B-Tree of order 2 are FBT. 02/07 15:32
→ ybite:如果是True的話那我的反例是錯的嗎？ Orz 我得想想 02/07 21:23
→ ken10311120:第五題我認為fib(2)的值不會被記得 因為他在return 1 02/03 15:07
→ ken10311120:時 就已經離開程式了 02/03 15:07
→ ken10311120:14(d)"2-3"樹不是blanced "binary" tree吧? 02/03 15:17
→ ken10311120:他可以有2~3個children(非root) 有看到此篇麻煩幫一下 02/03 15:18