Algoritmi e Programmazione Avanzata
Compito di teoria – 14 Maggio 2007
Tempo: 30 minuti, NON è possibile consultare libri o appunti.
Esercizio 1
(6 punti)Sia data la sequenza di interi, supposta memorizzata in un vettore:
11, 31, 24, 9, 98, 90, 5, 13, 88, 77, 34, 65
– la si trasformi in un heap, ipotizzando di usare un vettore come struttura dati. Si riportino graficamente i diversi passi della costruzione dell'heap ed il risultato finale. Si ipotizzi che, alla fine, nella radice dell'heap sia memorizzato il valore MINIMO;
– si eseguano su tale heap i primi 2 passi dell'algoritmo di heapsort per ottenere un ordinamento DECRESCENTE.
Esercizio 2
(5 punti)Sia dato il grafo orientato e pesato definito in figura
Si determinino tramite l'algoritmo di Dijkstra i valori di tutti i cammini minimi che collegano il vertice A con ogni altro vertice. Si assuma, qualora necessario, un ordine alfabetico per i vertici visitati.
Esercizio 3
(4 punti)Discutere la complessità dell'algoritmo di ordinamento quicksort in funzione del partizionamento ad ogni passo di ricorsione ed in funzione della scelta del pivot. Quali sono le scelte possibili per il valore del pivot? Come si può comportare l'algoritmo se il vettore è già ordinato?
I voti saranno comunicati tramite la segreteria didattica, contestualmente alla data e luogo per la registrazione.
4
G
F E
D
C B
A
3
5
6 6 4
1
1
4
3 1
