Esame del 21 luglio 2003

(1)

1

Algoritmi e Programmazione Avanzata

Esame del 21 luglio 2003

Parte I (teoria)

Tempo: 45 minuti, NON è possibile consultare libri o appunti.

Esercizio 1 (2 punti)

Si supponga di voler applicare l’algoritmo di insertion sort al vettore 4 23 12 41 54 10 8 12

Si determini il numero di operazioni di confronto eseguite durante l’esecuzione dell’algoritmo.

Si disegni il BST risultante al termine dell’inserimento dei seguenti valori 40 9 21 25 35 91 8 70 16 14 12 20

Si esegua poi la cancellazione dei valori 91, 9 e 35, e si disegni nuovamente l’albero risultante.

Si consideri una tabella di hash basata su open addressing che utilizza la tecnica del linear probing per risolvere le collisioni. La tabella è inizialmente vuota. Su di essa viene eseguita una sequenza di operazioni di inserimento di elementi con chiave corrispondente alle seguenti stringhe :

orazio, pippo, pluto, paperino, minnie, gastone, qui, quo, qua, paperoga, topolino, paperina,

Si mostri il contenuto della tabella di hash al termine della sequenza di inserimenti, assumendo che la sua dimensione sia pari a M=13 e che la funzione di hash utilizzata corrisponda al resto della divisione tra la somma dei codici ASCII delle lettere componenti la stringa ed il valore M.

Si ricorda che il codice ASCII della lettera ‘a’ è 97 e della lettera ‘z’ è 122.

(2)

2 Esercizio 4

Sia dato il seguente grafo:

E F

I L

A B C D

G H

M N

9

8

5

1

3

2 1

2 3

3 2

7 1

8

2

Punto a (2 punti)

Si disegnino la matrice di adiacenza e la lista di adiacenza del grafo.

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.

Si determini l’albero dei cammini minimi a partire dal vertice A per il grafo di cui sopra utilizzando l’algoritmo di Dijkstra.

(3)

3

Parte II (programmazione)

Tempo: 60 minuti, è possibile consultare libri o appunti.

Si scriva un programma C che risolva il problema del quadrato magico di dimensione 4x4. Un quadrato magico di dimensione N è una matrice in cui sono presenti tutti e soli i numeri tra 1 e N², disposti in modo tale che la somma dei valori su tutte le righe è costante, ed è pari alla somma dei valori su tutte le colonne e sulle due diagonali.

Esempio

Il seguente è un quadrato magico di dimensione 3:

8 3 4 1 5 9 6 7 2