Prova scritta del 19 luglio 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 uno heap-tree 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 siffatto, due valori estremi a e b e una pila p, riempia la pila 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 e fornendo, nel caso in cui sia falsa, un controesempio:
“Al termine dell’esecuzione dell’algoritmo da me realizzato la pila p 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 heap-tree con valori diversi per a e b. I nodi grigi sono quelli che dovranno essere memorizzati nella pila.
Esercizio 2 (12 punti)
Un modo per rappresentare gli insiemi di valori interi (nel senso matematico di ”collezioni” di valori prive di duplicazioni) è attraverso un vettore dinamico che contiene i valori rappresentati nell’insieme. In particolare, qualora il vettore venga
mantenuto ordinato, le operazioni di verifica dell’appartenenza di un elemento ad un insieme possono essere realizzate in modo efficiente.
Vogliamo definire l’implementazione del tipo di dato astratto insieme che gestisca questa struttura dati attraverso la sua rappresentazione per mezzo di vettori dinamici ordinati.
Le operazioni possibili sugli insiemi sono le seguenti:
• insieme crea_insieme(): crea un nuovo insieme vuoto.
• struct info_rango rango(insieme i, int x): restituisce due informazioni organizzate nella seguente struct:
20
11
7
1
8
5 6
18
13 a = 4 b = 10
15
20
11
7
1
8
5 6
18
13 a = 12 b = 16
15
struct info_rango { int rango;
bool presente;
}
Il campo rango conterrà il rango del valore x nell’insieme i, ovvero il numero di elementi minori di x (alternativamente, la posizione di x nella sequenza ordinata), mentre il campo presente avrà valore true qualora l’elemento x sia presente nell’insieme e false in caso contrario.
* insieme aggiungi(insieme* i, int a): restituisce il descrittore del nuovo insieme ottenuto aggiungendo il valore a (allocando, se necessario, opportunamente la memoria); se tale valore è già presente nell’insieme la funzione non farà alcuna modifica
* void elimina_insieme(insieme* i): elimina l’insieme i liberando la memoria eventualmente allocata dinamicamente.
1. Si definisca un possibile descrittore per il tipo di dato insieme (in altre parole la typedef struct {}
insieme) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione degli insiemi 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. In particolare, si richiede che l’implementazione della
funzione rango() abbia complessità O(log n), con n numero di valori contenuti nell’insieme.
Nota: il rango di un determinato valore x è calcolabile sia nel caso esso sia presente nell’insieme che in caso contrario. Ad
