[理工] 109 中央 資演選擇對答案

[tinhanho (アーニャ寶)]

板上好像沒有 或者是我找不到QQ

題目 https://rapid.lib.ncu.edu.tw/cexamn/exam/EC02_109_01.pdf

複選
1. ABD
2. C
3. A
4. CD  ABCD
5. A
6. C

是非
7. B
8. B
9. B
10. A
11. B

申論題不太會寫qq

第1題
想法是一個從頂端push 一個從底部push

第2題
▼錯的
for(j=1;j<=n;j++)
    swap...;
    perm(list[i], i+1, n);
    swap...;

▼正確

for(j=i;j<=n;j++)
    swap...;
    perm(list, i+1, n);
    swap...;


第3題
a Kruskal, time:O(ElogE)
b 不會寫 google的-> https://web.ntnu.edu.tw/~algo/SpanningTree2.html

第4題
看板上有一篇說用DP做
但我應該還是寫不出來

自己寫的答案 有錯煩請指正 感激不盡 祝大家金榜題名

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.161.235 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1673536834.A.E8E.html
※ 編輯: tinhanho (36.224.161.235 臺灣), 01/12/2023 23:21:15
→ ping990579: 4.ABCD
好像做錯了 ABCD沒錯 感謝~
→ ping990579: 兩個stack 一個由上往下另一個反之 判斷一下push時top
→ ping990579: 是否一樣為滿
→ ping990579: 第三題我想法是kruskal先找一個mst，然後找剩下的邊
→ ping990579: 最小的加入mst必會產生cycle,在cyle內閃掉最小邊得到
→ ping990579: 次小mst
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 10:55:24
→ ping990579: 我不是用dfs求欸我用定義
→ ping990579: 在圖論中，由一個有向無環圖的頂點組成的序列
→ ping990579: 若且唯若滿足下列條件時，才能稱為該圖的一個拓撲排序
→ ping990579: 序列中包含每個頂點，且每個頂點只出現一次；
→ ping990579: 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑
我用洪毅的indegree來寫 後來有寫出來~ 感謝
圖論的部分不太熟@@  圖論真的蠻難的
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 11:02:18
→ ping990579: 第四題 想法大概是排序s成上升序列 用一個二維陣列c(
→ ping990579: i,j)表示前i個和等於j的方法數 判斷i與j大小關係定義
→ ping990579: 遞迴
→ ping990579: https://imgur.com/cV2PNw0
→ ping990579: 感覺有點像背包那樣吧 有錯請指教
→ ping990579: 不對 是元素個數才對
→ ping990579: 上面是錯的
→ ping990579: https://imgur.com/kfR9SmI
→ ping990579: T(i,j,a)才對 排序多餘的
→ ping990579: 拍謝Mst那題應該沒辦法是次小，我查geek上https://im
→ ping990579: gur.com/ci9D3hu
推 jim881115: 申論2.填空我寫的是:
→ jim881115: for(j=i;j<n;j++)
→ jim881115: swap
→ jim881115: perm(list, i+1, n);
→ jim881115: swap
你是對的 但應該是<=n

https://imgur.com/6KbVUrX
寫題目寫到有點累 摸一下程式
題外話 swap的地方搞有點久 我的指標還是一樣爛 qqqqqq
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 22:34:18