Pages: [1]   Go Down
Print
Author Topic: domanda esame 20 febbr.  (Read 673 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« on: 20-02-2012, 21:13:15 »

la domanda numero 5 diceva così:

sia T un albero binario di ricerca in cui non può essere eseguita alcuna rotazione a sinistra di alcun nodo. Allora

a. T ha un solo nodo
b. L'altezza di T è al più 2log n
c. La radice contiene il valore massimo
d. Il valore massimo si trova in una foglia...


ora quello che ho pensato io è la seguente:
se ha un solo nodo, non è possibile effettuare rotazioni rotazioni ne  a sinistra ne a destra.. quindi la risposta A potrebbe essere......

e può essere che i valori siano minori della radice e quindi anche la risposta C potrebbe essere....



cosa ne pensate? qualcuno mi può aiutare a comprendere la soluzione giusta??

grazie
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #1 on: 20-02-2012, 21:40:31 »

Se non è possibile eseguire la LeftRotate su alcun nodo vuol dire che nessun nodo ha un figlio destro, di conseguenza l'unica cosa che mi viene da pensare è che dato che per trovare il massimo ci si sposta più a destra possibile, in questo caso non ci si può spostare a destra quindi il massimo si trova nella radice. Per la risposta A, è vero che T potrebbe avere un solo nodo ma non è una condizione necessaria, quindi la A non è sempre valida. la B non può essere perche in questo caso l'altezza può essere anche n, e la D neanche dato che per il ragionamento di prima penso che il max si trovi nella radice.. buh almeno credo  boh
Logged
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #2 on: 21-02-2012, 17:22:28 »

Quale delle seguenti è vera:
a) n^{3}=\Theta ((n + \log n)^{3})
b) n^{3}=\Theta ((n +n \log n)^{3})
c) n^{3}=\Theta ((n \log n)^{3})
d) n^{3}=\Theta (n^{3+\log n})

So che bisogna svolgere i vari cubi di binomio, ma poi non so continuare, qualcuno mi può aiutare facendomi vedere qualche esempio..
Grazie.
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #3 on: 21-02-2012, 18:50:15 »

Se non è possibile eseguire la LeftRotate su alcun nodo vuol dire che nessun nodo ha un figlio destro, di conseguenza l'unica cosa che mi viene da pensare è che dato che per trovare il massimo ci si sposta più a destra possibile, in questo caso non ci si può spostare a destra quindi il massimo si trova nella radice. Per la risposta A, è vero che T potrebbe avere un solo nodo ma non è una condizione necessaria, quindi la A non è sempre valida. la B non può essere perche in questo caso l'altezza può essere anche n, e la D neanche dato che per il ragionamento di prima penso che il max si trovi nella radice.. buh almeno credo  boh
Risposta corretta.
Logged
Pages: [1]   Go Up
Print
Jump to: