[理工] 資料結構

看板Grad-ProbAsk作者 (DIODE)時間12年前 (2013/12/30 00:21), 編輯推噓4(4推 0噓 25→)
留言29則, 4人參與, 最新討論串4/17 (看更多)
幾題題目 因為沒有答案只好來麻煩版上的大大們了QQ (true or false) 1.The memory usage for doubly linked list is O(n^2), where n is the number of element in the list. 這題我覺得是false 應該只有O(n)吧@@? 2.Let f(n) be a linear function of n .Then f(n)= Ω((logn)^k)for any power of k. 這題我覺得是true 可是 因為 Ω的定義 雖然是下限 但是只能差常數倍 所以覺得怪怪的 3.Given a complete binary tree.Let's perform the post-order traversal from the root and number the nodes with numbers starting from 1.For a node with number k, its parent must be numbered 2k or 2k+1. 這題我選false 4.The height of a 2-3-4 tree must be smaller than or equal to the height of a 2-3 tree with the same data. 這題我選false 5.Given an arbitary directed graph , it takes O(2^n)time to determine whether there exist a path between two nodes , where n is the number of nodes. 這題我選false 應該是O(1)吧@@?! 6.Let f(n) be the Fibonacci series where f(0)=0 and f(1)=1 .Let H be a hash with 10 buckets, and let |H(i)| denote the number of elements in the i's bucket,for i=0 to 9. If we insert the first 12 numbers of Fibonacci series, that is ,f(0) to f(11), into the hash H with the following hash function "h(n)=n^2%10".Then |H(4)|>|H(5)|. 這題我覺得是true h(n)=n^2%10 我是用0,1,2,3,....,11去代 不知道對不對 以上 麻煩大家了!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.185.251.7
→
12/30 00:29, , 1F
F T F T F T 第五題是O(n)，因為要看兩點有沒有PATH，
12/30 00:29, 1F
→
12/30 00:30, , 2F
最差要找兩次V，第六要看0 1 1 2 3 5 8 13 21 34 55。
12/30 00:30, 2F
推
12/30 01:02, , 3F
第二題我覺得是false f(n)=O(n^c) c=constant
12/30 01:02, 3F
→
12/30 01:03, , 4F
(logn)^k 另k=n => (logn)^n 兩者都取log
12/30 01:03, 4F
→
12/30 01:05, , 5F
一者為log(n^c)=clogn=O(logn) 一者為nloglogn
12/30 01:05, 5F
→
12/30 01:24, , 6F
2是false4還沒想到反例其他跟A大差不多2要改O才對
12/30 01:24, 6F
→
12/30 02:01, , 7F
4應該T 想一下 因leaf都在同層 d大不管怎插h都是小或等
12/30 02:01, 7F
→
12/30 02:13, , 8F
6好像是F吧 費氏數0~11插進去是用chainH(4)=H(5)一樣…
12/30 02:13, 8F
→
12/30 02:45, , 9F
答案都和A大一樣 第二題洪傑有講過喔 n的不管幾次方都
12/30 02:45, 9F
→
12/30 02:45, , 10F
比logn幾次方都大 如果沒記錯的話@@ 證明好像要用lim法+
12/30 02:45, 10F
→
12/30 02:45, , 11F
羅畢達
12/30 02:45, 11F
→
12/30 10:08, , 12F
k是常數，哪能用n去代，就算令為"現在"的n，n還會成長阿
12/30 10:08, 12F
→
12/30 11:52, , 13F
其實P大那方法有錯 但那題我覺得還是錯的n=O((log)^k)
12/30 11:52, 13F
→
12/30 11:53, , 14F
舉log變logn=klogn要O才對好嗎 洪根本錯 裡面錯不少…
12/30 11:53, 14F
→
12/30 12:03, , 15F
log((log n )^k) = kloglogn < log n
12/30 12:03, 15F
→
12/30 12:04, , 16F
找一下洪1-26範例3e很像不過是O但100台大榜首好像寫T
12/30 12:04, 16F
推
12/30 12:05, , 17F
哦哦，明白A大的意思了，觀念不太清楚，抱歉
12/30 12:05, 17F
→
12/30 12:13, , 18F
舉錯是klogn和cn才對 k是any power有指數成長的意思?
12/30 12:13, 18F
→
12/30 12:13, , 19F
如果沒有就是T有 應該就要O吧…
12/30 12:13, 19F
感謝各位大大的幫忙 第四題我選TRUE但是打成falseQQ 另外想請問一下 第一題FALSE 想請問那應該是多少?!每一個node增加一個link的欄位 所以頂多是O(n+n)=O(n) 不知道對不對?! ※ 編輯: n791116 來自: 111.185.122.223 (12/30 12:56) ※ 編輯: n791116 來自: 111.185.122.223 (12/30 13:08)
推
12/30 13:28, , 20F
我覺得洪講的很有道理阿= =
12/30 13:28, 20F
→
12/30 13:28, , 21F
看不懂錯在哪
12/30 13:28, 21F
→
12/30 13:28, , 22F
那個e的c沒說條件本來就要考慮所有情況不是嗎
12/30 13:28, 22F
→
12/30 13:28, , 23F
請問那年榜首是拿滿分嗎@@
12/30 13:28, 23F
→
12/30 13:28, , 24F
不然怎麼確定是T
12/30 13:28, 24F
推
12/30 13:37, , 25F
同取log的寫法應該會是A大那樣才對吧
12/30 13:37, 25F
→
12/30 13:46, , 26F
第一題我覺得是3n，兩邊的point加資料。
12/30 13:46, 26F
→
12/30 13:52, , 27F
抱歉洪那是對的 我記錯==因為是poly time 這題是linear
12/30 13:52, 27F
→
12/30 13:52, , 28F
c應=1榜首那題是n=O((logn)^k) 他寫T 題目跟這一樣
12/30 13:52, 28F
→
12/30 13:52, , 29F
洪那是類似 所以我現在要討論的是上限還下限
12/30 13:52, 29F
題目來說的話應該是討論下限~~ 反正下限 小於等於自己 ,上限 大於等於自己就可以了吧?! 感謝各位大大><祝大家新年快樂!!!XD ※ 編輯: n791116 來自: 111.185.251.7 (12/31 17:29)
‣ 更多 n791116 的文章
文章代碼(AID): #1Im4loyP (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 4 之 17 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共17篇)
‣ 更多 n791116 的文章
文章代碼(AID): #1Im4loyP (Grad-ProbAsk)