3 2
-7
9
6 -1
11 21 7
-5
-6
Prova scritta del 5 febbraio 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 (6 punti)
Scrivere una funzione in linguaggio C che, dato un vettore di numeri reali verifica se tale vettore rappresenta correttamente un heap-tree implicito. La funzione deve restituire true qualora il vettore sia una rappresentazione corretta, e false in caso contrario. Si discuta, informalmente, la complessità temporale dell’implementazione espressa in funzione del numero n di elementi del vettore.
Esercizio 2 (12 punti)
Si consideri un albero binario arbitrario (quindi non necessariamente di ricerca) in cui a ciascun nodo n sia associato un valore intero n.dato. Scrivere una funzione (ricorsiva) in linguaggio C che, dato in input un albero binario e un intero k ≥ 0 e una coda, riempia la coda il valore di tutti i nodi che si trovano a profondità maggiore o uguale a k. Se non esistono nodi a profondità maggiore o uguale a k, o l’albero è vuoto, la coda dovrà essere vuota. Ad esempio, se k = 2 e l’albero è quello della figura a lato, la coda dovrà contenere i nodi indicati in grigio (in ordine arbitrario).
Esercizio 3 (12 punti)
Un intervallo di numeri reali [a, b] consiste in tutti i numeri reali compresi fra a e b, estremi inclusi. Un’unione di intervalli [a, b] e [c, d] (con a ≤ c) dà come risultato un singolo intervallo [min{a, c}, min{b, d}], se i due intervalli non sono disgiunti, altrimenti l’insieme risultato può essere descritto come [a, b] ∪ [c, d] se i due intervalli sono disgiunti. Analogamente,
l’operazione di unione applicata ad un insieme di sotto-intervalli [a, b] ∪ [c, d] con un nuovo intervallo [e, f] è data dai risultati dell’unione di [e, f] con uno dei singoli sotto-intervalli costituenti l’unione (qualora non sia da esso disgiunto) oppure è descritto da [a, b] ∪ [c, d] ∪ [e, f], e così via per insiemi di più sotto-intervalli.
Vogliamo definire un tipo di dato astratto intervallo che rappresenti, in modo compatto, un singolo intervallo o un’unione di sotto-intervalli in modo da consentire un’implementazione efficiente delle operazioni descritte in seguito.
Le operazioni possibili sugli intervalli sono le seguenti:
• intervallo crea_intervallo(float a, float b): crea un nuovo intervallo [a, b]
• intervallo unione(intervallo i1, intervallo i2): restituisce un nuovo intervallo rappresentato dall’unione di i1 e i2
• bool appartiene(float x, intervallo i): verifica se x ∈ i
• elimina_intervallo(intervallo* i): elimina l’intervallo (o l’unione di sotto-intervalli) rappresentato da i
1. Si definisca un possibile descrittore per il tipo di dato intervallo (in altre parole l’opportuna typedef struct {…}
intervallo;) e si definiscano le ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione degli intervalli 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 sotto-intervalli di cui è costituito l’intervallo.
