Mathematical Engineering - Informatica A

Second partial exam

Informatica A – a.a. 0 8/0 9 – Secondo Appello – 9/6/200 9 Cognome ________________________________ Matricola _______________________ Nome ________________________________ Firma _______________________ Istruzioni • Non separate questi fog li. Scrive te la soluzione solo sui fogli distribuiti , utilizzando il retro delle pagine in caso di necessità . Cancella te le parti di brutta (o ripudiate) con un tratto di penna . • Ogni parte non cancellata a penna sarà considerata parte integrante della sol uzione. • È possibile scrivere a matita (e non ricalcare al momento della consegna!). • È vietato utilizzare calcolatrici o telefoni . Chi tenti di farlo ved rà annullata la sua prova. • È ammessa la consulta zion e di libri e appunti , purché con pacata discrezione e senza disturbare. • Qualsiasi tentativo di comunicare con altri studenti comporta l’espulsione dall’aula. • È possibile ritirarsi senza penalità . • Non è possibile lasciare l’aula conservando il tema della prova in corso. • Tempo a disposizione: 2 h 30 m Valore degli esercizi, voti parziali e voto finale: Esercizio 1 ( 2 punti ) __________ Esercizio 2 ( 6 punti ) __________ Esercizio 3 ( 5 punti ) __________ Esercizio 4 ( 6 punti ) __________ Esercizio 5 ( 6 punti ) __________ Esercizio 6 ( 5 punti ) __________ Totale: ( 30 punti ) _________ 2 Esercizio 1 - Algebra di Boole, Aritmetica Binaria, Codifica delle Informazioni (2 punti) (a) Si costruisca la tabella di verità della seguente espressione booleana in quattro variabili , badando all a precedenz a tra gli operatori logici. Eventualmente si aggiungano le par entesi (1 punto). ( ( not A ) or not ( ( not B ) and C ) ) or ( A and B ) (b) Si stabilisca il minimo numero di bit sufficiente a rappresentare in complemento a due i numeri A = 35 dec e B = –114dec , li si converta , se ne cal colino la somma (A+B) e la differenza (A –B) in complemento a due e si indichi se si genera riporto sulla colonna dei bit più significativi e se si verifica overflow (1 punto). 3 Esercizio 2 ( 6 punti ) Si considerino le seguenti definizioni di funz ioni void fun(Lista lis1,Lista lis2) { if (lis1==NULL) return; else if (lis1 ->next != NULL) fun(lis1 ->next,lis2); else lis1 ->next=lis2; } void foo(Lista lis1, Lista lis2) { fun(fun(lis1,lis2),fun(lis1,lis2)); } Si spieghi brevemente cos a fanno le funzioni fun e foo. 4 Esercizio 3 ( 5 punti ) Il seguente schema descrive una base di dati relativa a d una catena di autolavaggi che intende avviare un programma di fidelizzazione dei propri clienti. CLIENTE (COD CLI, NOME , CITTÀ ) VEICOLO (TARGA , TIPO , COD CLI) IMPIANTO (LOCALITÀ , NUMERO LINEE , DATA APERTURA ) LAVAGGIO (TARGA , DATA , ORA MINUTO , LOCALITÀ , COSTO ) 1. Scrivere una query SQL che e strae il Nome dei clienti di Bergamo che non hanno mai lavato un motociclo (un veicolo di Tipo ”Motociclo”) . 2. Form ulare in Algebra Relazionale, Calcolo Relazionale , Datalog e SQL l’interrogazione che per ogni cliente restituisce il primo lavaggio effettuato . 5 6 Esercizio 4 ( 6 punti ) Si progetti e codifichi una funzione C che riceve in ingresso un a list a definit a typedef struct Node { int numero; struct Node * next; } Nodo; typedef Nodo * Lista; che contiene solo valori positivi. Definiamo picchi della lista quei valori che sono preceduti e seguiti nella lista da valori più piccoli della loro metà. Il primo e l’ultimo elemento della lista non possono essere picchi. Ad esempio nella lista 4 9 12 36 16 23 87 34 18 64 33 36 e 87 sono picchi (perché 36/2=18, 18>12 e 18>16 e 87/2=43,5, 43,5>23 e 43,5>34) Si progetti e codifichi una funzione C c he riceve in ingresso un a list a definit a come sopra e restituisce il numero di picchi che la lista contiene. int picchi(Lista lis) { int n=0; while(lis!=NULL && lis ->next!=NULL && lis ->next ->next!=NULL) { if((float)( lis->valore ) < (float) ( lis->next ->valore )/2 && (float)(lis ->next ->next ->valore) < (float) (lis ->next ->valore)/2) n++; lis=lis ->next; } return n; } 7 8 Esercizio 5 ( 6 punti ) Si consideri la seguente struttura dati : typedef struct Dat aT { int giorno; int mese ; int anno; } Da ta; typedef struct Interprete T { char * cognome; char * nome; char * cittadinanza ; } Interprete ; typedef Interpret e * ListaInterpreti ; typedef struct Concerto T { ListaInterpreti Lista, Data data, int prezzoBiglietto, struct Node * next; } Concerto ; typedef Concerto * Lista Concerti ; Si codifichi una funzione che , ricev uta in ingresso una lista di co ncerti restituisce la somma dei prezzi dei biglietti di tutti i concerti che hanno tra gli interpreti almeno un italiano (un italiano ha il campo Cittadinanza=”ITA”). Si consiglia fortemente l’utilizzo di funzioni ausiliarie. int isIta(ListaInterpreti c) { if(strcmp(“ITA”,c ->cittadinanza)==0) return 1; return 0; } int hasIta(ListaInterpreti c) { if(c==NULL) return 0; if(isIta(c)) return 1; return hasIta(c ->next); } int totIta(ListaConcerti lc) { int totDopo; if(lc==NULL) return 0; totDopo=totIta(lc ->next); if( hasIta(lc ->Lista) return totDopo+lc ->prezzoBiglietto else return totDopo; } 9 10 Esercizio 6 ( 5 punti ) Si consideri la seguente definizione di un albero binario (binario=con due rami in ogni nodo): typedef struct EL { int dato; struct EL * left, struct EL * right; } node; typedef node * tree; Si definisce livello di un nodo la sua distanza dalla radice. Si scriva una funzione che prende in ingresso un albero binario e restituisce 1 se tutti i nodi di livell o pari contengono un numero pari e tutti i nodi di livello dispari contengono un numero dispari. int f(tree t,int livello) { if(t==NULL) return 1; if(livello%2!=t ->dato%2) return 0; return f(t ->left,livello+1) && f(t ->right,livello+1); } 11 12