Università di Roma “La Sapienza” (sede di Latina) Corso di Laurea in Ingegneria (settore dell'Informazione)
A.A. 2004­05
Esame di Algoritmi e strutture dati – 5 settembre 2005
Esercizio 1 (6 punti)
T 1=3
Risolvere con almeno due metodi diversi la seguente relazione di ricorrenza
⌊ ⌋
2⋅n
T n=T
3
1
Esercizio 2 (6 punti)
La funzione per il quicksort è la seguente:
public static void qs(int[] a, int l, int r ) {
if (l < r){
int p = partition(a,l,r);
qs(a,l,p-1);
qs(a,p+1,r);
}
}
i. Costruire, con i seguenti numeri 20, 12, 31, 3, 18, 70, 15 un caso peggiore per l'algoritmo del
quicksort in cui la scelta del pivot viene effettuata prendendo sempre l'elemento più a sinistra dell'array. Scrivere in
forma di albero di ricorsione, la sequenza delle chiamate ricorsive con l'evidenziazione del pivot.
ii. Scrivere il corpo della funzione int partition(int[] a, int l ,int r).
Esercizio 3 (6 punti)
i. Illustrare la struttura dati Coda la sua interfaccia pubblica e la sua rappresentazione mediante array circolare.
ii. Scrivere una funzione (esterna alla classe Coda) Coda CopiaCoda(Coda c) che effettui una copia della coda
c. La funzione non può far uso di strutture ausiliarie (trane la coda risultato) e deve lasciare la coda c immutata.
Esercizio 4 (6 punti)
Si considerino le classi BTNode e BTree che implementano
rispettivamente il nodo di un albero binario e un albero binario.
Aggiungere un metodo livk alla classe BTree che restituisca il
numero di nodi di livello k dell'albero. Si supponga che la radice
abbia livello 0.
public class BTNode {
private Object key;
private BTNode leftChild;
... consueti costruttori e metodi get/set di
accesso agli attributi
}
public class BTree {
private BTNode root = null;
...
}
Esercizio 5 (6 punti)
4
2
2
3
6
3
3
1
1
7
2
2
1
i. mostrare l'evoluzione dell'algoritmo di Dijkstra quando il nodo
origine è il nodo 4;
1
Dato il grafo pesato rappresentato nella figura:
4
2
1
Illustrare l'algoritmo di Dijkstra e la sua complessità in funzione
della rappresentazione del grafo.
5
ii. mostrare, al termine di ciascuna iterazione dell'algoritmo, il valore
provvisorio della distanza di ciascun nodo dal nodo origine e l'insieme dei
nodi per i quali la distanza calcolata è quella definitiva. Per far ciò completare
la tabella indicata (ogni colonna corrisponde ad una iterazione dell'algoritmo
e contiene le distanze calcolate dell'algoritmo, ogni riga ad un nodo del grafo;
nell'intestazione delle colonne indicare l'insieme dei nodi con la distanza
definitiva).
4
{}
{...}
{...}
inf
...
...
2
inf
...
...
3
inf
...
...
4
0
...
...
5
inf
...
...
...
...
...
...
2
8
2
9
1
1
di
Università di Roma “La Sapienza” (sede di Latina) Corso di Laurea in Ingegneria (settore dell'Informazione)
A.A. 2004­05
Esame di Algoritmi e strutture dati – 5 settembre 2005
Esercizio 1 (6 punti)
T 1=T 2=T 3=1
Risolvere con almeno due metodi diversi la seguente relazione di ricorrenza
T n=3⋅T
⌊ ⌋
n
n⋅log n
4
Esercizio 2 (6 punti)
La funzione per il quicksort è la seguente:
public static void qs(int[] a, int l, int r ) {
if (l < r){
int p = partition(a,l,r);
qs(a,l,p-1);
qs(a,p+1,r);
}
}
i. Costruire, con i seguenti numeri 20, 12, 31, 3, 18, 70, 15 un caso migliore per l'algoritmo del
quicksort in cui la scelta del pivot viene effettuata prendendo sempre l'elemento mediano dell'array. Scrivere in
forma di albero di ricorsione, la sequenza delle chiamate ricorsive con l'evidenziazione del pivot.
ii. Scrivere il corpo della funzione int partition(int[] a, int l ,int r).
Esercizio 3 (6 punti)
i. Illustrare la struttura dati Pila la sua interfaccia pubblica e la sua rappresentazione mediante array.
ii. Scrivere una funzione (esterna alla classe Pila) Pila CopiaPila(Pila p) che effettui una copia della pila
p. La funzione può far uso di strutture ausiliarie e deve lasciare la pila p immutata.
Esercizio 4 (6 punti)
Si considerino le classi BSTNode e BSTree che implementano
rispettivamente il nodo di un albero binario e un albero binario di
ricerca.
Aggiungere un metodo compresi alla classe BSTree che
restituisca il numero di nodi dell'albero compresi tra un estremo
inferiore a e un estremo superiore b entrambi di tipo
Comparable.
public class BSTNode {
private Comparable key;
private BSTNode leftChild;
... consueti costruttori e metodi get/set di
accesso agli attributi
}
public class BSTree {
private BSTNode root = null;
...
}
Esercizio 5 (6 punti)
4
2
2
3
6
3
3
1
1
7
2
2
1
iii. mostrare l'evoluzione dell'algoritmo di Dijkstra quando il nodo
origine è il nodo 1;
1
Dato il grafo pesato rappresentato nella figura:
4
2
1
Illustrare l'algoritmo di Dijkstra e la sua complessità in funzione
della rappresentazione del grafo.
4
5
iv. mostrare, al termine di ciascuna iterazione dell'algoritmo, il valore
provvisorio della distanza di ciascun nodo dal nodo origine e l'insieme dei
nodi per i quali la distanza calcolata è quella definitiva. Per far ciò completare
la tabella indicata (ogni colonna corrisponde ad una iterazione dell'algoritmo
e contiene le distanze calcolate dell'algoritmo, ogni riga ad un nodo del grafo;
nell'intestazione delle colonne indicare l'insieme dei nodi con la distanza
definitiva).
{}
{...}
{...}
0
...
...
2
inf
...
...
3
inf
...
...
4
inf
...
...
5
inf
...
...
...
...
...
...
2
8
2
9
1
1
di