Re: [理工] [資結] 95台大電機

[jameschou (DOG)]

※ 引述《QQprob (吃飯睡覺)》之銘言：
: http://www.lib.ntu.edu.tw/exam/graduate/95/416.pdf
: 第4題我聽說的答案是B
: 但實在不知是為何?

這個答案我也會覺得是B

directed主要是因為有transitivity特性
( a≦b , b≦c 則 a≦c 所以a,c關係可省略不記錄 )
acyclic主要是因為有antisymmetry特性
( 不會指回自己 )

小舉個例子好了
比如說四個node 關係如下

  a b c d
a 1   1 1
b   1
c     1
d     1 1

以上符合三個要求的特性
那麼我們記錄只要記錄如下

a -> d -> c  即可

因為有a≦d,d≦c必可推出a≦c,所以就不需要特別去紀錄a≦c
大意應該是這樣 或許我詳細的沒有說很清楚
不過題目問最佳 選這個答案應該是B不會有錯


: 還有第9題
: 我寫的答案是ABC
: 他每個選項等號後面的數字是指放在第k的bucket中的data量吧?
: 但我聽到的答案卻是全部選項都錯了

這題我會用刪去法
首先知道 (50a+b)^2 + 1 = 2500a^2 + 100ab + b^2 + 1
所以 (50a+b)^2 + 1 ≡ b^2 + 1 (mod 100)
因此1~1000中 50一循環可知如果bucket中有 那就必有20的倍數個
因此可刪除 A,D 選項
原PO有選A我想這個部分應該是錯的 你可以驗證1,51,101...,951這20個應該都會放在B[2]

再來看B選項
若B[3]有東西 那就代表i在1~1000中有數字符合 i^2 + 1≡3 (mod 100)
也就是 i^2 + 1 = 100k + 3 (k∈Z)
=> i^2 = 100k+2 = 2(50k+1)
這是不可能的 因為50k+1必為奇數 不含因數2
=> B選項是對的

C選項 因為要找B[26] 也就是 i^2 + 1 ≡ 26 (mod 100)
所以i必為5的倍數 但若為10的倍數則i^2 + 1 ≡ 1 (mod 100)
因此只要找 0 < 10a+5 < 1001 中 (10a+5)^2 + 1 ≡ 26 (mod 100)即可
又(10a+5)^2 + 1 = 100a^2 + 100a + 25+1 = 100(a^2+a)+26
=> (10a+5)^2 + 1 ≡ 26 (mod 100) , ∀a∈Z
因此|B[26]|=100 => C選項是對的

再來是E選項 這個選項對我來說我覺得有點麻煩 不知道有沒有更好的解法
我們知道若要產生十位數與個位數是37 由於個位數為7 故我們的i個位數要為4或6
但是要50個才一循環
所以應該要找出h(4),h(6),h(14),h(16),h(24),h(26)...,h(44),h(46)才能確定有幾個
h(4) = 17
h(6) = 37
h(14) = 97
h(16) = 57
h(24) = 77
h(26) = 77
h(34) = 57
h(36) = 97
h(44) = 37
h(46) = 17
因為 1~50中有2個數放到37
所以1~1000中有40個數放到37
故E選項應該是對的


所以我這題的答案會是BCE


: 最後第14題
: 我覺得B選項也是對的 但聽到的答案中沒有
: 可以幫忙解釋一下B選項哪裡有誤?
: 請大家解惑! 謝謝

首先 => 一定對 這個trivial就不說了
再來若 f(n) = O(g(n)) => ∃c0,n0 當 n≧n0 時 s.t. c0×g(n)≧f(n)
    若 f(n) = Ω(g(n))=> ∃c1,n1 當 n≧n1 時 s.t. c1×g(n)≦f(n)

所以照理來說...
取 n2 = max(n0,n1)     (n2為n0,n1中較大的那個)
=> ∃c2=c0,c3=c1 ,當 n≧n2時 s.t.  c3×g(n) ≦ f(n) ≦ c2×g(n)
=> f(n) = θ(g(n))

所以B選項應該是對的(?)
其實我這題不是很確定 我之前也常常會錯這種觀念題
如有錯誤再麻煩指正一下了 感謝



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.195
推 QQprob:謝謝你~~不過第9題可以再解釋一下50一循環是怎麼得到的嗎XD
→ jameschou:(50a+b)^2 + 1 = 2500a^2 + 100ab + b^2 + 1
→ jameschou:主要是因為2500a^2跟100ab都是100的倍數了
→ jameschou:另外我昨天有看一下你更之前的文章 有默默在下面推文XD
→ jameschou:一題跟prime number有關係的
※ 編輯: jameschou       來自: 140.112.4.195        (09/23 10:58)