Pages: [1] 2   Go Down
Print
Author Topic: domande esame 4 luglio 6cfu  (Read 2385 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« on: 04-07-2012, 19:55:57 »

Sia T un albero R-B. la complessità del miglior algoritmo possibile per stampare in ordine crescente i nodi colorati di rosso è:

io ho messo  Theta(log n)



voi cosa avete messo?
Logged
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #1 on: 04-07-2012, 20:34:23 »

ovviamente ho pensato a una visita inorder.. quindi O(n)
Logged

Aliens Exist
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #2 on: 05-07-2012, 10:28:19 »

Alla domanda 4: quali dei seguenti problemi è Omega(n log n):
-Verificare che un array e ordinata
-costruire un heap
-costruire un albero binario di ricerca
-verificare che un array è una heap.

cosa avete risposto?
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #3 on: 05-07-2012, 10:59:41 »

ragazzi potete scrivere tutte le vostre risposte?cosi' le confrontiamo pc
Logged

Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #4 on: 05-07-2012, 13:49:49 »

Alla domanda 4: quali dei seguenti problemi è Omega(n log n):
-Verificare che un array e ordinata
-costruire un heap
-costruire un albero binario di ricerca
-verificare che un array è una heap.

cosa avete risposto?


albero binario di ricerca
Logged

Aliens Exist
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #5 on: 06-07-2012, 11:22:14 »

Alla seguente domanda:  sia A un array di n elementi reali compresi tra 0 e 1 (uno escluso). Siano x=0.6 e y=0.7 due elementi di A. utilizzando l'algoritmo di ordinamento Bucket sort, per quale valore di n,x e y, non finiscono nello stesso bucket?

a. n=2
b. n=3
c. n=4
d. n=5


il mio ragionamento è stato questo:

Siccome la teoria dice: per ordinare un array A dividiamo l'intervallo [0,1) in n sottointervalli della stessa dimensione, detti i bucket, e poi nel distribuire gli n elementi di input nei bucket.

allora se ci sono n=5 elementi, x e y non cadranno nello stesso intervallo mentre fino a n=4 questo succede... giusto?
Logged
Flyer
Apprendista Forumista
**
Offline Offline

Posts: 100



« Reply #6 on: 06-07-2012, 12:05:31 »

In realtà con n=5 dovrebbero finire nello stesso bucket.
Il testo specifica 1 escluso quindi gli intervalli con n=5 dovrebbero essere:
1: da 0 a 0.19
2: da 0.2 a 0.39
3: da 0.4 a 0.59
4: da 0.6 a 0.79
5: da 0.8 a 0.99

Invece con n=3 gli intervalli dovrebbero essere
1: da 0 a 0.33
2: da 0.34 a 0.66
3: da 0.67 a 0.99
Quindi in questo caso non finiscono nello stesso bucket.
Sempre se non ho sbagliato qualcosa  univ
Logged
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #7 on: 06-07-2012, 12:30:33 »

si anche io ho messo 3
Logged

Aliens Exist
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #8 on: 06-07-2012, 14:49:26 »

mi sa che io ho fatto i conti male....

POTERE POSTARE LE SOLUZIONI DELLE PRIME TRE DOMANDE E DELLA NUMERO 5...GRAZIE
Logged
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #9 on: 06-07-2012, 14:53:31 »

mi sa che io ho fatto i conti male....

POTERE POSTARE LE SOLUZIONI DELLE PRIME TRE DOMANDE E DELLA NUMERO 5...GRAZIE


1 b
2 c
3 d
5 c
Logged

Aliens Exist
sterui
Apprendista Forumista
**
Offline Offline

Posts: 170



« Reply #10 on: 06-07-2012, 15:56:06 »

Ciao 

Io ho risposto

1) d
2) c
3) d
5) d

In particolare per la 5... ho pensato... avendo Radix Sort una complessità di theta(d(n+k)) ed essendo in questo caso k = n^2, la complessita sarebbe theta(n+n^2).
Non so se ho ragionato bene 
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #11 on: 06-07-2012, 16:01:38 »

1 d
2 c
3 d
4 b
5 d
Logged

Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #12 on: 06-07-2012, 16:10:32 »

stiamo parlando del compito da 9?
Logged

Aliens Exist
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #13 on: 06-07-2012, 16:13:07 »

sisi
Logged

sterui
Apprendista Forumista
**
Offline Offline

Posts: 170



« Reply #14 on: 06-07-2012, 16:14:16 »

Io avevo quello da 6cfu. Ma credo che le prime domande siano uguali per tutti 
Logged
Pages: [1] 2   Go Up
Print
Jump to: