Algoritmi e Programmazione Avanzata
Compito di teoria – 19 settembre 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:
44 16 88 22 8 69 36 5 12 53 61 72
– 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
(4 punti)Sia data la sequenza di chiavi S1A1NFER1R2A2GO1S2TO2 dove ciascun carattere è individuato dal suo ordine progressivo nell'alfabeto (A=1, ..., Z=26). Si definisca una funzione di hash per l'utilizzo di una tabella di hash e si riporti la struttura di una tabella di hash di dimensione 19, inzialmente supposta vuota, in cui avvenga l'inserimento della sequenza di cui sopra supponendo di utilizzare l'open addressing con probing lineare.
Esercizio 3
(1+5 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.
I voti saranno comunicati tramite email (da riportare in stampatello sul compito), contestualmente alla data e luogo per la registrazione.
3
D
G F
B
E C
A
1
3
4 3
1
5
3
5 2
