Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: varPippo on 11-03-2010, 12:08:30



Title: Info appello del 8 Marzo
Post by: varPippo on 11-03-2010, 12:08:30
Ragazzi chi ha le risposte corrette del suddetto compito?


Title: Re:Info appello del 8 Marzo
Post by: KiLLing Spree on 18-03-2010, 16:11:16
1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d


Title: Re:Info appello del 8 Marzo
Post by: xaviorx on 30-03-2010, 09:56:24
1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d

Perchè la 7 è d?


Title: Re:Info appello del 8 Marzo
Post by: Neds on 08-04-2010, 16:28:24
1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d

Perchè la 7 è d?

la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???


Title: Re:Info appello del 8 Marzo
Post by: cock86 on 10-04-2010, 15:33:29
Quote
la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???
vediamo di regionarci!
i nodi interni sono tutti i nodi dell'albero escluse le foglie nil.
la b-altezza è il numero di nodi neri che si incontrano nel cammino dalla radice ad una qualunque foglia.
il numero massimo di nodi si ha quando abbiamo alternativamente: livello nero-rosso....nero-rosso-nero e l'albero è bilanciato, e cioè quando h=2bh-1.
ad altezza h il numero massimo di nodi interni è (2^h)-1.
Giusto?
quindi.... prova a correggere!


Title: Re:Info appello del 8 Marzo
Post by: Neds on 12-04-2010, 11:38:37
Quote
la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???
vediamo di regionarci!
i nodi interni sono tutti i nodi dell'albero escluse le foglie nil.
la b-altezza è il numero di nodi neri che si incontrano nel cammino dalla radice ad una qualunque foglia.
il numero massimo di nodi si ha quando abbiamo alternativamente: livello nero-rosso....nero-rosso-nero e l'albero è bilanciato, e cioè quando h=2bh-1.
ad altezza h il numero massimo di nodi interni è (2^h)-1.
Giusto?
quindi.... prova a correggere!

quindi bh=3 da sostituire a  h=2bh-1=2*3 -1=5 che dobbiamo sostituire a (2^h)-1=(2^5)-1=31 e questa sarebbe la risposta c del compito, però quella corretta è la d, cioè 63  .penso


Title: Re:Info appello del 8 Marzo
Post by: cock86 on 12-04-2010, 12:05:03
il 63 mi fa pensare ad un 64-1= 2^6-1; quindi magari il problema sta in quale altezza considerare. La radice e altezza 0 o 1?non ricordo quale consideri il prof.


Title: Re:Info appello del 8 Marzo
Post by: cock86 on 12-04-2010, 12:09:29
eureka! mi sembra di ricordare che il numero dei nodi è 2^(h+1)-1. Poichè partiamo dalla radice che ha h=0.
di cinseguenza, se h = 5, numero nodi sarà n=2^(h+1)-1=2^(5+1)-1=2^6-1=64-1=63=D.