Prova scritta del 25 giugno 2018 di Fondamenti di Informatica II (prof. Di Gaspero) Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 2 ORE
A pena di annullamento immediato della prova:
1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.
2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula
Esercizio 1 (8 punti)
Si consideri un albero binario di ricerca in cui a ciascun nodo n sia associato un valore intero n.dato.
Scrivere un algoritmo (ricorsivo) in linguaggio C che, dato in input il descrittore di un albero binario siffatto, due valori estremi a e b e una coda q, riempia la coda con il valore di tutti i nodi i cui campi dato sono compresi fra a e b (estremi inclusi).
Dire, inoltre, se la seguente affermazione è vera o falsa, spiegandone le motivazioni: “Al termine dell’esecuzione dell’algoritmo da me realizzato la coda q conterrà i valori compresi fra a e b disposti in ordine crescente”.
A titolo d’esempio, si considerino le seguenti due esecuzioni in un dato albero con valori diversi per a e b. I nodi grigi sono quelli che dovranno essere memorizzati nella coda.
Esercizio 2 (12 punti)
Un vettore compatto è una struttura dati sequenziale in cui le eventuali ripetizioni di valori (aventi indici) contigui del vettore sono rappresentate da una coppia (valore, numero di
ripetizioni). Ad esempio, il vettore (tradizionale) {3, 3, 1, 1, 1, 6, 1, 1, 2, 2, 2, 2, 2} può essere rappresentato attraverso questa struttura dati attraverso la sequenza {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5)}.
Vogliamo definire un tipo di dato astratto vettore compatto che implementi questa struttura dati.
Le operazioni possibili sui vettori compatti sono le seguenti:
• vettore_compatto crea_vettore_compatto(): crea un nuovo vettore compatto vuoto
• vettore compatto aggiungi_in_coda(vettore_compatto* v, int a): restituisce un nuovo vettore compatto ottenuto aggiungendo il valore a in coda al vettore (allocando
opportunamente la memoria in modo dinamico)
• int cerca_prima_posizione(vettore_compatto v, int x) restituisce il valore della prima posizione (indice, dunque a partire da 0) in cui apparirebbe il valore x nella
rappresentazione come vettore tradizionale
• elimina_vettore_compatto(vettore_compatto* v): elimina il vettore compatto v liberando la memoria eventualmente allocata dinamicamente
A titolo d’esempio, l’esecuzione di aggiungi_in_coda(v, 2) sul vettore riportato in esempio dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 6)}, viceversa, l’esecuzione di aggiungi_in_coda(v, 5) sullo stesso vettore dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5), (5, 1)}. Per ciò che riguarda la funzione di ricerca, invece, l’esecuzione di cerca_prima_posizione(v, 1) sul vettore riportato in esempio dovrebbe restituire il valore 2, che è l’indice della posizione del primo 1 nella
rappresentazione tradizionale mentre l’esecuzione di cerca_prima_posizione(v, 2) dovrebbe restituire 8, indice della prima occorrenza di 2 nella rappresentazione tradizionale.
1. Si definisca un possibile descrittore per il tipo di dato vettore_compatto (in altre parole la typedef struct {…} vettore_compatto) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione dei vettori compatti descritte in precedenza. Qualora fosse necessario si assuma l’esistenza delle funzioni di manipolazione delle strutture dati utilizzate nel descrittore, scelte fra quelle studiate durante il corso.
3. Si discuta, informalmente, la complessità temporale dell’implementazione delle operazioni di manipolazione espressa in funzione del numero n di sequenze di valori contigui uguali memorizzate nel vettore compatto.
Esercizio 3 (10 punti)
Scrivere una funzione in linguaggio C verifica_negativi(g, s) che, dato un grafo diretto g nei cui vertici v è memorizzato un dato intero v.dato, verifica se, dato un vertice sorgente s, almeno uno dei nodi raggiungibili da s ha un valore del campo dato minore di zero . Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true, in caso contrario la funzione dovrà restituire il valore false.
