[理工] 資料結構

[n791116 (DIODE)]

幾題題目

因為沒有答案只好來麻煩版上的大大們了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
→ A4P8T6X9:F T F T F T 第五題是O(n)，因為要看兩點有沒有PATH，
→ A4P8T6X9:最差要找兩次V，第六要看0 1 1 2 3 5 8 13 21 34 55。
推 patabon:第二題我覺得是false f(n)=O(n^c) c=constant
→ patabon:(logn)^k 另k=n => (logn)^n 兩者都取log
→ patabon:一者為log(n^c)=clogn=O(logn) 一者為nloglogn
→ kiki86151:2是false4還沒想到反例其他跟A大差不多2要改O才對
→ kiki86151:4應該T 想一下 因leaf都在同層 d大不管怎插h都是小或等
→ kiki86151:6好像是F吧 費氏數0~11插進去是用chainH(4)=H(5)一樣…
→ mango3888:答案都和A大一樣 第二題洪傑有講過喔 n的不管幾次方都
→ mango3888:比logn幾次方都大 如果沒記錯的話@@ 證明好像要用lim法+
→ mango3888:羅畢達
→ A4P8T6X9:k是常數，哪能用n去代，就算令為"現在"的n，n還會成長阿
→ kiki86151:其實P大那方法有錯 但那題我覺得還是錯的n=O((log)^k)
→ kiki86151:舉log變logn=klogn要O才對好嗎 洪根本錯 裡面錯不少…
→ A4P8T6X9:log((log n )^k) = kloglogn < log n
→ kiki86151:找一下洪1-26範例3e很像不過是O但100台大榜首好像寫T
推 patabon:哦哦，明白A大的意思了，觀念不太清楚，抱歉
→ kiki86151:舉錯是klogn和cn才對 k是any power有指數成長的意思?
→ kiki86151:如果沒有就是T有 應該就要O吧…
感謝各位大大的幫忙 第四題我選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)
推 mango3888:我覺得洪講的很有道理阿= =
→ mango3888:看不懂錯在哪
→ mango3888:那個e的c沒說條件本來就要考慮所有情況不是嗎
→ mango3888:請問那年榜首是拿滿分嗎@@
→ mango3888:不然怎麼確定是T
推 mango3888:同取log的寫法應該會是A大那樣才對吧
→ A4P8T6X9:第一題我覺得是3n，兩邊的point加資料。
→ kiki86151:抱歉洪那是對的 我記錯==因為是poly time 這題是linear
→ kiki86151:c應=1榜首那題是n=O((logn)^k) 他寫T 題目跟這一樣
→ kiki86151:洪那是類似 所以我現在要討論的是上限還下限
題目來說的話應該是討論下限~~

反正下限 小於等於自己 ,上限 大於等於自己就可以了吧?!

感謝各位大大><祝大家新年快樂!!!XD
※ 編輯: n791116         來自: 111.185.251.7        (12/31 17:29)