Algoritmi e Programmazione Avanzata
Compito di teoria – 9 luglio 2007
Tempo: 30 minuti, NON è possibile consultare libri o appunti.
Esercizio 1
(5 punti)Sia data la sequenza di interi, supposta memorizzata in un vettore:
45 31 24 9 98 90 5 13 88 77 23 65
– Si eseguano i primi 2 passi dell’algoritmo di quicksort per ottenere un ordinamento ASCENDENTE. NB: i passi sono da intendersi, impropriamente, come in ampiezza sull’albero della recursione, non in profondità. Si chiede, pertanto, che siano ritornate le 2 partizioni del vettore originale e le due partizioni di ciascuna delle partizioni trovate al passo precedente.
Esercizio 2
(3 punti)Si effettuino secondo l’ordine specificato le seguenti operazioni su un BST supposto inizialmente vuoto (+ indica una inserzione, - una cancellazione):
+34 +21 +27 +25 +15 +72 +10 +54 +63 -72 +43 +26 +29 -21
Esercizio 3
(4 punti)Sia dato il grafo non orientato e pesato definito in figura
Si determini un albero ricoprente minimo del seguente grafo non orientato pesato, ritornando come risultato l'albero ed il valore del peso minimo, applicando l'algoritmo di Prim. Si riportino i singoli passi dell'algoritmo da cui si evinca il taglio sul grafo e la scelta dell'arco leggero.
Esercizio 4
(3 punti)Si fornisca la definizione di heap e se ne descrivano le proprietà principali. Che relazione c'è tra il numero di nodi e l'altezza di un heap?
I voti saranno comunicati tramite email (da riportare in stampatello sul compito), contestualmente alla data e luogo per la registrazione.
A B C
D E
F
G
7
5 9
15
8
7
6 8
11
9 5
