Algoritmi e programmazione avanzata

Algoritmi e programmazione avanzata
Compito d’esame
Parte di teoria
24 Febbraio 2014
Non si possono consultare testi e appunti. Durata della prova: 50 minuti.
1 (2.0 punti)
La seguente funzione ricorsiva
void f (int n) {
if (n>=10 || n<0) {
return;
}
printf ("%d ", n);
f (n+1);
f (n+2);
return;
}
viene richiamata mediante l’istruzione f(5).
Riportare l’albero di ricorsione e l’output generato dalla sua esecuzione.
2 (1.0 punti)
Si ordini in maniera ascendente mediante counting-sort il seguente vettore di interi:
3 4 5 2 6 5 4 2 8 1 4 1 8 0
Si indichino i passaggi rilevanti.
4
3 (2.0 punti)
Una coda a priorit`a `e inizialmente vuota e implementata mediante un heap in cui il valore massimo si posiziona sulla
testa della struttura.
Nella seguente sequenza di chiavi intere e caratteri:
10 22 29 71 * * 58 * 34 9 31 * * 14 * 41 27 18
ogni intero deve essere inserito nella coda, e ogni carattere ’*’ corrisponde a una estrazione del valore massimo dalla coda.
Riportare la conﬁgurazione della coda dopo ogni operazione, e la sequenza di valori ritornati durante il procedimento.
4 (2.0 punti)
Un albero binario di 12 nodi, fornisce le seguenti tre
pre-order:
33 41 23
in-order:
23 41
7
post-order: 23
7 11
Disegnare l’albero originario.
sequenze
1
7
1 11
1 41
di visita dei propri vertici:
11 17 19 13
3 27
33 13 19 17 27
3
13 19 27
5
3 17
5
5
33
5 (2.0 punti)
Si supponga di aver memorizzato tutti i numeri compresi tra 1 e 1000 in un albero di ricerca binario e che si stia cercando
il numero 531. Tra le sequenze successive, si determini quali non possono essere le sequenze esaminate durante la ricerca
e ne si motivi la ragione.
500 550 510 540 533 539 532 531
500 600 580 570 510 520 530 540 535 531
570 100 200 300 400 500 660 550 520 525 530 531
610
30 600
60 588 117 519 299 301 477 531
continua
6 (3.0 punti)
Sia dato il grafo orientato rappresentato in ﬁgura:
A
C
B
E
D
F
G
I
L
H
Lo si rappresenti come lista delle adiacenze (0.5 punti) e come matrice delle adiacenze (0.5 punti). Considerando a come
vertice di partenza:
• se ne eﬀettui una visita in profondit`
a, etichettando i vertici con i tempi di scoperta e di ﬁne elaborazione nel formato
tempo1/tempo2 (1.5 punti). Qualora necessario, si trattino i vertici secondo l’ordine alfabetico.
• lo si ridisegni, etichettando gli archi come T (tree), B (back), F (forward), C (cross) (0.5 punti).
Algoritmi e programmazione avanzata
Compito d’esame
Parte di programmazione
24 Febbraio 2014
Non si possono consultare testi e appunti. Durata della prova: 100 minuti.
La parte di programmazione prevede, in alternativa, la risoluzione:
• Dell’esercizio 1 (tradizionale) di valore massimo uguale a 18 punti.
• Degli esercizi 2, 3 e 4 (facilitati) con punteggio complessivo massimo uguale a 12 punti.
Non sono possibili soluzioni miste.
1 (18.0 punti)
Un grafo orientato pesato `e memorizzato su ﬁle mediante l’elenco dei suoi archi.
Ogni riga del ﬁle ha il seguente formato:
idV1 val idV2
che indica che il vertice di identiﬁcatore idV1 `e connesso con un arco orientato di peso val (valore intero) al vertice idV2.
Si osservi che il numero di vertici del grafo `e indeﬁnito e che ciascun vertice `e individuato mediante un identiﬁcatore
alfanumerico di lunghezza massima uguale a 20 caratteri.
La ﬁgura successiva riporta un esempio di ﬁle e della relativa rappresentazione graﬁca del grafo memorizzato.
A 3 Bb
Bb 2 CcC
A 4 dDd
CcC 1 dDd
A
3
2
4
dDd
Bb
1
CcC
Si vuole scrivere un’applicazione C in grado di:
• ricevere il nome di un ﬁle contenente la descrizione del grafo sulla riga di comando.
• leggere il grafo e memorizzarlo in una opportuna struttura dati.
• veriﬁcare se il grafo `e regolare o meno. Un grafo orientato si dice regolare se e solo se tutti i vertici hanno lo stesso
grado di ingresso e di uscita e questi due valori sono uguali tra loro.
• eﬀettuare un’iterazione all’interno della quale viene letto l’identiﬁcatore di un vertice.
– se l’identiﬁcatore letto `e uguale a fine il programma deve terminare.
– in caso contrario il programma deve determinare il cammino semplice con sorgente nel vertice indicato per il
quale la somma dei pesi degli archi `e maggiore. Per tale cammino occorre visualizzare su standard output
l’elenco dei vertici attraversati, l’elenco dei pesi degli archi e il peso totale.
continua
2 (2.0 punti)
Sia dato un vettore di N interi. Si realizzi una funzione ROTATE di shift del vettore a destra o a sinistra di P posizioni,
dove P `e un intero (positivo per shift a destra, negativo per shift a sinistra).
` vietato realizzare lo shift di P posizioni come l’iterazione di P shift da 1 posizione ciascuno, che avrebbe costo O(N ·P ).
E
Si richiede invece un algoritmo O(N ), che operi come segue. Utilizzando un vettore ausiliario di P posizioni, allocato
dinamicamente, l’algoritmo sposta temporaneamente P elementi dal vettore originario. Sposta quindi i rimanenti N − P
elementi nella loro destinazione ﬁnale. I P elementi salvati nel vettore ausiliario sono quindi collocati nella loro destinazione
ﬁnale. La funzione liberi la memoria allocata al termine del procedimento.
3 (4.0 punti)
Una matrice si dice “sparsa” quando la maggior parte delle caselle contiene un valore nullo. Nel caso di una matrice
sparsa, pu`o risultare conveniente l’utilizzo di una struttura dati che allochi dinamicamente memoria per le sole caselle
non nulle.
Si realizzi in C, per una matrice sparsa di numeri reali (float), la funzione di prototipo
void matInsert (matr_t *mat, int r, int c, float val);
che inserisce il valore val nell’elemento di riga r e colonna c della matrice mat.
Il tipo matr t `e una struct che, oltre a contenere le due dimensioni della matrice (numero di righe nr e numero di colonne
nc) punta a un vettore (di dimensione nr) di puntatori a righe, ognuna realizzata mediante una lista, contenente gli
elementi non nulli della riga corrispondente.
Si deﬁnisca la struttura matr t, il tipo struttura utilizzato per implementare le liste lungo le righe della matrice e si scriva
la funzione matInsert.
4 (6.0 punti)
Si scriva una funzione ricorsiva in grado di generare tutte le stringhe di lunghezza N costituite dalle 5 vocali maiuscole
’A’, ’E’, ’I’, ’O’, ’U’. La funzione soddisﬁ inoltre i seguenti vincoli:
• Il valore di N sia ricevuto dal programma sulla riga di comando e sia N ≥ 5.
• Nella stringa generata ogni vocale compaia almeno una volta.
La funzione ricorsiva deve essere tale per cui all’i-esimo livello di ricorsione viene gestito l’i-esima cella della stringa della
soluzione.

Download Report