-
*
3 +
4 1
/
5 2
Prova scritta del 3 settembre 2018 di Fondamenti di Informatica I (prof. Montessoro) + Fondamenti di Informatica II (prof. Di Gaspero)
Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 3 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
Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
Esercizio 1 (13 punti)
Si consideri il seguente tipo di dato struct persona
{
char nome[32];
int interessi[N];
};
che rappresenta una persona, in cui in vettore interessi rappresenta il valore tra 1 e 10 che la persona attribuisce ai suoi N interessi (ad es. cinema, calcio, . . . ). La costante N e gli interessi rappresentati sono uguali per tutte le persone.
Si scriva la funzione una funzione che riceva come parametri una variabile p di tipo struct persona, un vettore vp di tipo struct persona e la dimensione n del vettore. La funzione deve stampare gli indici delle persone (una o più) in vp che hanno la minima differenza di interessi con p.
La minima differenza, che dovrà essere calcolata da una funzione ausiliaria, si calcola come media delle differenze in valore assoluto tra i valori di pari indice.
Ad esempio, se il vettore contiene i dati riportati a lato (con N = 4 e n = 5) e la persona p ha interessi 1, 2, 3 e 5,
la funzione deve stampare gli indici 0 e 2 (corrispondenti a Maria e Paolo), con i quali la media delle differenze è minima, pari a 0.25.
Esercizio 2 (13 punti)
Un modo per rappresentare le espressioni aritmetiche è attraverso degli alberi binari in cui ciascuna sottoespressione corrisponde ad un sottoalbero in cui l’operatore aritmetico utilizzato è la radice del sottoalbero e le ulteriori sottoespressioni (costanti numeriche oppure sottoespressioni complesse) sono rappresentati dai sottoalberi sinistro e destro.
Ad esempio l’espressione 3 * (4 + 1) - 5 / 2 è rappresentata dall’albero riportato nella figura.
Vogliamo definire l’implementazione di un tipo di dato astratto espressione che gestisca le strutture dati necessarie per questa rappresentazione. Per farlo, c’è la necessità di adattare la definizione dei nodi di un albero binario, che
chiameremo nodo_espressione, in modo da rappresentare entità di tipo differente (numeri interi e operatori).
Le operazioni possibili sono le seguenti:
• espressione crea_espressione(): crea una nuova espressione vuota
• void rimpiazza_albero(espressione* e, nodo_espressione *r) modifica l’espressione e, rimpiazzando il nodo_espressione attualmente memorizzata nel descrittore distruggendo l’albero attualmente presente e rimpiazzandolo con quello passato alla funzione; in particolare se il nodo_espressione passato come parametro è NULL il risultato dovrà essere un espressione vuota
• int calcola_risultato(espressione e) calcola il risultato dell’espressione eeffettuando tutte le operazioni descritte nell’albero; ad esempio nel caso dell’espressione in figura il risultato dovrà essere 13
• void elimina_espressione(espressione* e): elimina le strutture dati utilizzate nella memorizzazione dell’espressione e
nome interessi Maria 1 3 3 5 Giulio 2 4 4 6 Mario 1 2 3 4 Paola 2 3 1 2 Paolo 2 3 1 7
In aggiunga si considerino le seguenti operazioni sulla struttura nodo_espressione
• nodo_espressione* crea_costante(int valore) che crea un nodo_espressione che rappresenta la costante il cui valore è passato come parametro
• nodo_espressione* crea_operazione(char operatore, nodo_espressione* se_sx, nodo_espressione* se_dx) a partire da due sottoespressioni crea una nuova espressione con alla radice l’operatore passato come parametro
1. Si definisca il descrittore per il tipo di dato espressione (in altre parole la typedef struct {}
espressione e la struct nodo_espressione)
2. Si implementino in linguaggio C le operazioni di manipolazione 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.
Esercizio 3 (4 punti)
Scrivere una funzione in linguaggio C verifica_dispari(g, s) che, dato un grafo diretto gnei cui vertici v è memorizzato un dato intero v.dato, verifica se, dato un vertice sorgente s, tutti i nodi raggiungibili da s hanno un valore dispari nel campo dato. Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true, in caso contrario la funzione dovrà restituire il valore false.
