 |
vlaste |
Tecnoclassico
Registered: Jun 2004
Posts: 472 (0.06 al dì)
Location: Estrema periferia
Corso: Informatica
Anno: terzo... bis
Time Online: 3 Days, 5:56:07: [...]
Status: Offline
Edit | Report | IP: Logged |
 SECONDO COMPITINO
Posto il testo del secondo compitino... magari può servire...
Esercizio 1
Eseguire l’algoritmo Quicksort sull’input
4, 2, 6, 0, 1, 7, 8, 9, 3, 5
mettendo in evidenza gli scambi eseguiti e assumendo sempre come pivot il primo elemento della sequenza corrente.
Esercizio 2
a) Definire la nozione di albero di ricerca binaria e descrivere ad alto livello due procedure ricorsive, la prima per la ricerca di un elemento in tale struttura e l’altra per l’inserimento di un nuovo elemento.
b) Descrivere ad alto livello due procedure non ricorsive per eseguire le medesime operazioni.
Esercizio 3
a) Descrivere una procedura del tipo divide et impera per il calcolo dell’espressione
X = a1 * a2 + a2 * a3 + a3 * a4 + ... + an-1 * an
su input n, a1, a2, … , an.
b) Assumendo il criterio di costo uniforme, valutare in funzione di n il tempo di calcolo e lo spazio di memoria richiesti dalla procedura su input n, a1, a2, … , an.
c) Supponendo che ogni ai sia un intero di k bit, fornire una valutazione O-grande del tempo di calcolo e dello spazio di memoria richiesti dalla procedura secondo il criterio logaritmico, in funzione dei parametri n e k.
|
Polsy
Attachment: 
Attachment: 
