[理工] [DS]99師大 軟體基礎(自寫版)

[justbelieve (呆)]

1.  b
2.  4
3.  (1+2+...n)/n
4.  (1+2+...n)/n
5.  n/n = 1
6.  (1+2+...n)/n
7.  3564280971
8.  10
9.            5
            /   \
          7       16
        /   \    /   \
      31    82  49    44
     /
    62

10. 右子樹不變    左子樹變成     3
                               /   \
                             10      75
                            /   \
                           20    60

11. a.  ABDEGHCF
    b.  ABCDEFGH
    c.  ABDEGHCF
    d.  ABCDEFGH    //其實我寫這小題感覺很怪,因為有沒有加那條edge
                      感覺都沒啥差

12. a.  計算n個點的complete binary tree的高度
    b.  log n
    c.

13. 有點不是很懂在幹嘛

14. LCS(演算法沒啥看......正在惡補中)



麻煩有寫的在來互相訂正討論一下囉



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.117.65.116
推 orzreynold:1.a 11.a.ABDECFGH b.ABCDEFGH
→ orzreynold:加了那一邊，你DFS的E就要走到C拉
→ orzreynold:則BFS就是一層一層下來
→ ms70831:想問一下為什麼12是在說計算N個點的complete BT 高度??
→ justbelieve:12.其實我是帶點進去看,n=1 =>1,n=2 =>2,...n=7 =>3
→ justbelieve:你可以畫圖出來看看會比較清楚
→ justbelieve:o大的意思是說order類似優先權?越前面越先追蹤?
→ justbelieve:所以加CE邊後,C的order高於G,所以先往C那條走過
→ justbelieve:另外,1.log n可以被消去嗎?為什麼bound是O(n^3)?
推 orzreynold:6n^3/logn+1=O(n^3)比較好一點。其實你選b，a有何不可
→ orzreynold:另外，11題他有說明order是照字母
推 pigcat1315:DFS  我寫ABDEGHCF
→ DavyBlue:第一題我還是比較prefer選b 最接近
推 orzreynold:其實洪逸他最後改成a
→ sneak: 第一題我還是比較pre https://daxiv.com