Algoritmi e Programmazione Avanzata
Compito di teoria – 13 maggio 2008
Tempo: 30 minuti, NON è possibile consultare libri o appunti.
Si indichi, sul compito consengato in classe, il proprio indirizzo email per la comunicazione della valutazione della prova scritta
Esercizio 1
(5 punti)Sia data la sequenza di interi, supposta memorizzata in un vettore:
21 17 51 31 41 52 61 6 36 15 39 19
– 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+2 punti)Si effettuino secondo l’ordine specificato le seguenti operazioni su un BST supposto inizialmente vuoto (+ indica una inserzione, - una cancellazione):
+14 +3 +2 +15 +28 +9 +6 +10 +4 -9 +8 -14 Si riporti il risultato delle visite in pre-order, post-order e in-order su tale albero.
Esercizio 3
(1+4 punti)Sia dato il seguente grafo orientato e pesato:
– Si disegnino la matrice di adiacenze e la lista di adiacenze del grafo.
– Si determinino i valori di tutti i cammini minimi che collegano il vertice A con ogni altro vertice mediante l’algoritmo di Dijkstra. Si assuma, qualora necessario, un ordine alfabetico per i vertici e gli archi. Si riportino i passaggi dell'algoritmo in modo da evincere l'ordine di analisi dei nodi e le operazioni di aggiornamento dei cammini minimi.
3 A
K G
L H
C B
1 3 5
1 2 1
4
3
2
