[理工] [資結]-96台大資工軟體設計 對答(含演算法部分)

[taitin (小南)]

我自己寫的答案

希望跟大家討論一下正確性

http://www.lib.ntu.edu.tw/exam/graduate/96/96419.pdf


1-a.  empty(B)
1-b.  !empty(A)
1-c.  v=pop(A)
1-d.  push(v,B)
1-e.  v=pop(B)

2-a
          A
         / \
        C   B
       /   / \
      F   E   D
      \      / \
       J    H   G
           /
           K



3-a index
3-b index+i-1
3-c index+1
3-d index+i-2
3-e B[j-i]+B[j-i+1]

4-a (m+1)I
4-b N(I+P)+P

          (M+1)I-P
4-C  N > -----------
            I+P

5-a
       (應該要化成兩個框框，方便起見就不畫了)

       Eric->Jimmy___
               ^_____|   (指自己....抱歉不會畫QQ)

 Harry  ---      Adam
           \       |
           V       V
 Joe    ---> Tom->Mary-->Kevin->Lucy___
 George ----^      ^        ^      ^____|
            John---|        |
                     Barry__|

5-b
     Mary colleages

     John Tom Harry Joe George  Adam Barry Kevin Lucy



6-a theta(nlgn)
6-b theta(3^n)
6-c theta(n^5)
6-d theta(lgn)
6-e theta(lgn)


7-a len[i,j]=len[i-1,j-1]+1
7-b len[i,j]=max{len[i-1,j],len[i,j-1]}


8-a  4
8-b  6
8-c  -7


希望有寫這份的可以一起討論~

歡迎寄信或回(推)文



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.218.42
推 nickboy0211:可以請你解說一下巴斯卡三角形那題你怎麼推出來的嗎？
→ nickboy0211:謝謝！
→ taitin:首先觀察到最後一句話 index=index+i 而i=1~n 可得知
                                                              ^^剛打錯
→ taitin:index為每列的列首 ex 第三列列首為4=1(初始)+1+2
→ taitin:因此利用index的特性，且知道列首及列尾都是1
→ taitin:因此 3a  index  3b index+i-1(i為第i列故有i個數)
→ taitin:因此 從第二個 到倒數第二個要加上一行的數 得 3c 3d
→ taitin:而加的數為減掉該列數的數字跟下一個數字
→ taitin:ex B[8]=B[8-4]+B[8-4+1] 因此可以得到3e
※ 編輯: taitin          來自: 61.230.218.42        (01/25 23:54)
→ nickboy0211:感謝您的回履。
推 polomoss:第一題我一直在想為何不用回復，把B的再丟回A
推 polomoss:1-d push(v,B)才對吧?  還有1-a 應該B要為空才繼續做?
感謝樓上提醒..我發現我打錯XD，如果有困擾大家的，真抱歉。已修正
推 polomoss:3-a 我答案只用i表達 (i^2-i)/2 +1  3-b (i^2+i)/2
應該是一樣的，我一開始也這樣寫，後來發現index比較好用
推 polomoss:第4題哪裡有L，我只看到I
看來是我眼殘了....已修正
→ polomoss:5-b 我覺得只有barry
因為他說同事是所有只要同一個super boss的都是同事，所以下面那整個群組的
superboss都是同事....我是這樣想的啦，包含lucy也是
→ polomoss:6~8沒錯
※ 編輯: taitin          來自: 140.113.37.176       (01/26 08:56)
→ polomoss:我還是覺得5-b應該只有barry
→ polomoss:感覺改題老師應該不希望改那麼多名子，一個挺適當的
→ polomoss:而且其他人都是MARY的下屬，感覺層級上就有差，不為同事
→ polomoss:不過這大概也沒有正解@@
哈..XD
→ polomoss:1-a答案我覺得改成 !empty(A)比較好
→ polomoss:B是用來輔助的，應該都是空的
可是這樣1-a不就多餘了嗎？
因為有while了阿

看一個例子  queue Q 利用這個演算法
           add (1,Q)   add (2,Q)   delete() add(3,Q) delete() delete()
 依據FIFO  應該是 1 2 3

可是如果改 !empty(A)

stack A  裡為 2 1 ，delete()時 stack B 為 1 2 ，pop(B) 輸出1
add(3,Q) stackA 裡有 3，非空，delete()時 stack 變 3 2 pop(B)輸出 3

這樣就有問題了



※ 編輯: taitin          來自: 114.44.234.233       (01/26 17:45)
推 tureday:7-a 應該是len[i,j]=len[i-1,j-1]+1才對吧？
→ tureday:上一次算完串列的個數再加一..ai＝bj串列會增加一個
推 yesa315:可能少打了吧
感謝樓上兩位，已修正
※ 編輯: taitin          來自: 140.113.7.249        (02/06 17:59)
推 rockmanray:Eric Jimmy畫反了吧