[理工] [DS] 交大100 DS+algo

[metalalive (想玩音樂)]

http://www.lib.nctu.edu.tw/attach/download/id-765/
一些觀念弄不清楚
想請教一下

第1題
他說求 time complexity of NCTU
答案給 O(n)
想請問 CS(csie , i ,n) 這行的複雜度不用算嗎?


第15題
這算是離散的範圍嗎
asynmetric <--> anti-symmetric & irreflexive
上面的敘述是對的八?
那這樣題目說 asymmetric 且 reflexive 不就不存在?
還是說這邊有什麼地方沒考慮到

第34題,選項C,D
選項敘述說的 "given edge e"
是指G中任意的e? 還是algo K所產生的e ?
看解答,好像傾向後者的敘述
可是我不知道這兩個選項關鍵字在哪 QQ

第36題
請教選項b是錯在後面那一句
...all vertices are in the set {1,2,...k}
是嗎?
翻algo筆記&書 , 它是不是只定義
從i到j的路徑中,只經過1,2...,k
for all i,j = 1...n

題組16的題意為何?
看不懂第45題,題目敘述跟 search 的關係





謝謝!



--
No time to pray....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.78.243
→ louis719:第一題是bottom up建heap的演算法 複雜度是O(n)沒錯
推 pikachu123:15.那題是有問題矛盾
→ pikachu123:34.不曉得你想表達甚麼 題目是說w(e)是e的weight
→ pikachu123:(C)很明顯就是對 kruskal找到的spaning Tree
→ pikachu123:當然都比 G中任何spanning tree的每邊的weight 小
→ pikachu123:36.中繼點才是v1~vk裡 vi跟vj不是
→ Byzantin:誰跟你說6的A是錯的...
→ metalalive:感謝louis719,是bottomup建立heap沒錯,我想起來了
→ metalalive:第六題我看錯了,SORRY
※ 編輯: metalalive      來自: 220.128.126.145      (01/10 14:40)
→ Byzantin:題組16簡單來說就是給你全在同一直線上的node和每對node
→ Byzantin:間的距離(但不知是哪對的) 要你求所有pair的距離
→ metalalive:謝謝Byzantin我在思考一下qq
→ sneak: 題組16簡單來說就是給 https://daxiv.com