1
Algoritmi e Programmazione Avanzata
Esame del 22 settembre 2003
Parte I (teoria)
Tempo: 45 minuti, NON è possibile consultare libri o appunti.
Esercizio 1 (2 punti)
Sia data la sequenza di interi, supposta memorizzata in un vettore:
13 40 38 22 26 39 12 29 67 20 53 31
Si esegua sul vettore l’algoritmo di Insertion Sort, riportando i passaggi fondamentali.
Esercizio 2 (2 punti)
Si effettuino secondo l’ordine specificato le seguenti operazioni su un BST supposto inizialmente vuoto (+ inserzione, - cancellazione):
+2 +13 +21 +5 +7 +9 +6 +10 +14 -21 -13 + 17 -6 Esercizio 3 (2 punti)
Sia data la sequenza di chiavi SETTEMBRE, dove ciascun carattere rappresenta una chiave ed è individuato dal suo ordine progressivo nell’alfabeto (A=1, ..., Z=26).
Si inserisca detta sequenza in una tabella di hash di dimensione 13 utilizzando il linear chaining.
Esercizio 4
Sia dato il seguente grafo orientato:
B C
D E
A
F
G
H I
J K
L M
Punto a (2 punti)
Si disegnino la matrice di adiacenza e la lista di adiacenza del grafo.
2 Punto b (3 punti)
Si visiti il grafo in profondità ed in ampiezza, considerando A come vertice di partenza. Si indichi la sequenza di visita dei vertici nei due casi. Qualora necessario, si trattino i vertici secondo l’ordine alfabetico.
Esercizio 5 (4 punti)
Sia dato il seguente grafo orientato pesato. 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.
A
H
G
I C F
E
B
D
3
2
2 3
5
2 3
4
1 5
3 3 2
6 1
7
1
J
3
3
3
Parte II (programmazione)
Tempo: 60 minuti, è possibile consultare libri o appunti.
Si scriva un programma C che calcola l’accoppiamento ottimo per 10 giocatori di bridge. Ogni persona ha espresso una serie di preferenze, elencando in ordine di preferenza decrescente gli altri giocatori. Il programma trova l'assegnazione che rispetta nel modo complessivamente migliore le preferenze espresse.
Il programma esegue le seguenti operazioni:
• Leggere da tastiera le preferenze di ogni persona, sotto forma di 10 righe, ciascuna composta da 9 interi (seprati da uno spazio). Il primo numero sulla riga i-esima rappresenta il compagno di gioco più “desiderato” dalla persona i-esima, l'ultimo quello meno desiderato.
• Calcolare l'abbinamento ottimale, ossia quello che massimizza la funzione A = Σ f(i), dove f(i) è una funzione che per la persona i-esima vale 10 se la persona è stata assegnata con il compagno più desiderato, 9 se è stata assegnata al compagno corrispondente alla seconda scelta, e così via. La sommatoria è estesa a tutte le 10 persone. Nel caso ottimo (non sempre possibile) la funzione A assume il valore 100.
• Visualizza l'abbinamento ottimo, stampando su video le 5 coppie di numeri (identificativi delle persone) che risultano dall'abbinamento.
Esempio
Supponendo che il numero di persone coinvolte sia 4, si ipotizzi che il programma legga le seguenti righe
2 4 3 3 1 4 2 4 1 1 2 3
L'abbinamento ottimale è: 1-4 (7 punti) 2-3 (8 punti).
1 4 2 3
