Mathematical Engineering - Informatica A

Second partial exam

Politecnico di Milano Dipartimento di Elettronica e Informazione Informatica A – a.a. 0 7/0 8 – Second a Prova in Itinere – 1/2/200 8 Cognome ________________________________ Matricola _______________________ Nome ________________________________ Firma _______________________ Istruzioni • Non separate q uesti fogli. 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 d ella 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 disc rezione 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 ( 3 punti ) __________ Esercizio 3 ( 3 punti ) __________ Esercizio 4 ( 2 punti ) __________ Esercizio 5 ( 5 punti ) __________ Totale: ( 15 punti ) _________ Voto finale: _________ Esercizio 1 ( 2 punti ) Dato il tipo typedef struct { int V[20]; int C; } STR ; Scrivere una funzione con un parametro formale X di tipo STR e un parametro formale MATR di tipo matrice 20x20 interi. La funzione considera i primi C elementi conten uti nel campo V di X e restituisce la somma di quelli tra loro che sono multipli di almeno tre elementi della matrice MATR. Si supponga che il valore del campo C sia sempre compreso tra 0 e 19 (estremi inclusi). Si utilizzino opportune funzioni ausiliarie per dividere il problema in sottoproblemi più semplici. int contaSM seMag3 (int x, MATR m) int i,j,cont=0; for(i=0;inext; return 0; } int conta(Lista V [] ,int N,int x) int i,cont=0; for(i=0;inumero )==0) { printf( “Numero quasi comune %d” ,L ->numero); G=aggiungiInTesta(G,L ->numero); } L=L ->next; } } } Esercizio 3 ( 3 pu nti ) Si consideri una lista concatenata semplice di dati su persone caratterizzate dal loro cognome, dal loro nome e dal codice di iscrizione. La struttura della lista è: typedef struct Node { int codice; char * cognome; char * nome; struct Node * next; } Nodo; typedef Nodo * Lista; Si implementi la funzione di prototipo Lista generaListaOrdinata( Lista lis ); che riceve una lista non ordinata e restituisce una lista contenente gli stessi elementi ma ordinati per cognome e, a parità di cognome, per nome. Si utilizzino opportune funzioni ausiliarie per dividere il problema in sottoproblemi più semplici. Si ricorda che la funzione int strcmp(const char *s1, const char *s2) restituisce un intero minore , uguale o maggiore di 0 a seconda che s1 sia (o i primi n caratteri siano) rispettivamente minore, uguale o maggiore di s2. Esercizio 4 ( 2 punti ) Si consideri la seguente definizione di un albero binario (binario=con due rami in og ni nodo): typedef struct EL { int dato; struct EL * left, struct EL * right; } node; typedef node * tree; Definiamo un albero come "artussiano" se è composto solo da 1. nodi foglia 2. nodi con un solo figlio 3. nodi co n due figli aventi lo stesso numero di discendenti Codificare una funzione che riceve in input un albero e restituisce 1 se l’albero è "artussiano", 0 altrimenti. Nel risolvere il problema è consigliato servirsi di opportune funzioni ausiliarie. int con taNodi ( tree t ) { if ( t == NULL ) return 0; else return (contaNodi(t ->left) + contaNodi(t ->right) + 1); /* c’è anche il nodo corrente */ } int artussiano(tree t) if(t==NULL) return 1; if(t ->left==NULL && t -> right== NULL) //foglia return 1; if(t ->left==NULL) return artussiano(t ->right); if(t -> righ t==NULL) return artussiano(t ->left); return (conta(t ->left)==conta(t ->right) && artussiano(t ->left) && artussiano(t ->right)) Esercizio 5 ( 5 punti ) Il seguente schema rap presenta le informazioni riguardo alla gestione di una videoteca: DVD (Codice DVD , Titolo Film , Regista , Durata ) CLIENTE ( CodiceFiscale , Nome, Cognome, Indirizzo, Telefono, Categoria ) NOLEGGIO ( CodiceFiscale , Codice DVD , Data Inizio , Data Fine, Costo Giornal iero ) 1. Scrivere in tutti e tre i linguaggi formali e in SQL l’interrogazione che estrae i clienti che non hanno mai noleggiato due film de llo stesso regist a. 2. Scrivere in SQL l’interrogazione che estrae il cliente con il maggior numero di noleggi iniziati nel 2007. N=noleggio JOIN DVD N1=noleggio JOIN DVD duenol = PR(Cf) (N JOIN(N.cf=N1.cf && N.Regista=N1. Regiata && N.CodiceDVD!= N1.CodiceDVD ) N1 ) (PR(cf)cliente) -duenol Select distinct codice Fiscale FROM DVD D JOIN NOLEG GIO N ON N.codiceDVD=D.codiceDVD Group by cf , regista Having count(titoloFilm) =1.1.2007 && dataInizio=ALL selec t count(*) From noleggio Where dataInizio>=1.1.2007 && dataInizio