Mathematical Engineering - Informatica A

Second partial exam

Politecnico di Milano Dipartimento di Elettronica e Informazione Informatica A – a.a. 0 8/0 9 – Second a Prova in Itinere – 26 /1/200 9 Cognome ________________________________ Matricola _______________________ Nome ________________________________ Firma _______________________ Istruzioni • Non separate questi 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 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 dis crezione 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: 3 h Val ore degli esercizi, voti parziali e voto finale: RECUPERO PRIMA PROVA Esercizio 1 ( 8 punti ) __________ Esercizio 2 ( 6 punti ) __________ Totale: ( 14 punti ) _________ SECONDA PROVA Esercizio 3 ( 4 punti ) __________ Esercizio 4 ( 4 punti ) __________ Esercizio 5 ( 3 punti ) __________ Eserc izio 6 ( 5 punti ) __________ Totale: ( 16 punti ) _________ Voto finale: _________ Esercizio 1 ( 8 punti ) – RECUPERO PRIMA PROVA Si definisca una funzione che riceve in input un array a di 10 interi e una matrice m di 32x32 interi . L’array contiene una serie di interi tutti a 1 o a 0. La funzione calcola il numero decimale corrispondente alla codifica binaria rappresentata dalla sequenza di 1 e 0 dei primi 5 elementi dell’array e pone questo numero in una variabile intera x. Quindi calcola il numero decimale cor rispondente alla codifica binaria rappresentata dalla sequenza di 1 e 0 dei rimanenti 5 elementi dell’array e pone questo numero in una variabile y . Infine la funzione considera gli elementi della riga con indice x in m e controlla se tra questi quelli maggiori di m[ x][y] s iano di più di quelli minori di m[ x][y]. Se questo è il caso, il programma restituisce 1, altrimenti 0 . Esercizio 2 ( 6 punti ) – RECUPERO PRIMA PROVA Si progetti e codifichi una funzione C che riceve in ingresso un array a di i nteri non negativi . La funzione calcola il numero degli elementi dell’array che godono della seguente proprietà: il valore dell’elemento è pari al numero di elementi con valore inferiore considerando solo quelli in posizione precedente. Ad esempio, si cons ideri il seguente vettore: 1 2 1 3 6 4 14 In questo caso solo i due numeri in grassetto (il 3 e il 4) soddisfano la proprietà descritta. Quindi la funzione restituisce 2. Soluzione int contaPrec(int a [],int p) { int i=0,cont=0; for(i=0;iProx; } Punt = malloc(sizeof(Nodo)); Punt –>partitaIva = pi; strcpy(Punt –>nome,n); Punt –>numeroSingole = ns; Punt –>numeroDoppie = nd; Punt –>Prox = Pu ntCor; if (PuntPrec != NULL ) { /* Inserimento interno alla lista */ PuntPrec –>Prox = Punt; return lis ; } else return Punt; /* Inserimento in testa alla lista */ } Lista f(Lista lis) { Lista lisnew=NULL; while(lis!=NULL) { if(lis ->numeroDoppie >lis ->numeroSingole) lisnew=insInOrd(lisnew,lis ->partitaIva,lis ->nome,lis ->numero Singole,lis ->numeroDoppie) lis=lis ->next; } return lisnew; } Esercizio 4 ( 4 punti ) - SECONDA PROVA La funzione di prototipo Lista f(Lista A, Lista B) riceve due liste di interi e restituisce una nuova lista (allocata allo scopo) costituita da tutti gli interi della lista A (nell'ordine in cui appaiono in A) che non sono nella lista B seguiti da tutti gli interi della lista B (ne ll'ordine in cui appaiono in B) che non sono nella lista A. Si noti che le liste A e B possono contenere dei duplicati ; di conseguenza anche la lista risultante può contenere duplicati. Ad esempio, se A contiene gli interi 1,3,2,5,3,4,5 (in quest'ordine) e B contiene gli interi 4,2,6,6,4 (in quest'ordine) allora la lista risultante conterrà gli interi 1,3,5,3,5,6,6 (in quest'ordine). Si usi questa definizione di lista: typedef struct N { int valore; struct N * next; } Nodo; typedef Nodo * Lista; Si d ia una codifica ricorsiva della funzione f. Si consiglia e si apprezza il ricorso ad eventuali funzioni ausiliarie. Lista copia(Lista a) { Lista tmp; if(a==NULL) return NULL; tmp=(Nodo *)malloc(sizeof(Nodo)); tmp ->valore=a ->valore; tmp ->next=copi a(a ->next); return tmp; } int VerificaPresenza(Lista lis, int Elem){ if ( lis==NULL ) return 0; if ( lis –>valore == Elem ) return 1; return VerificaPresenza(lis –>next, Elem); } ListaDiElem eliminaPrimo (ListaDiElem Lista, int Elem ) { ListaDiElem PuntTemp; if ( ! ListaVuota (Lista) ) if ( Lista –>Info == Elem ) { PuntTemp = Lista ->Prox); free(Lista); return PuntTemp; } else { Lista –>Prox = eliminaPrimo (Lista –>Prox, Elem); return Lista; } else return Lista; } ListaDiElem eliminaTutti (ListaDiElem Lista, int Elem ) { ListaDiElem PuntTemp; if ( ! ListaVuota (Lista) ) if ( Lista –>Info == Elem ) { PuntTemp = Lista ->Prox); free(Lista); return eliminaTutti( PuntTemp ); } else { Lista –>Prox = eliminaTutti (Lista –>Prox, Elem); return Lista; } else return Lista; } Lista f(Lista a,Lista b) { Lista c=copia(a); Lista d=copia( b); c=f2(c,d ); } Lista f2(Lista c,Lista d){ if(c==NULL) return d; if(d==NULL) return c; if(verificaPresenza(c,d ->valore)==1) { elimina Tutti (c,d ->valore); elimina Tutti (d,d ->valore); } else { c= insInFondo(c,d ->valore); eliminaPrimo(d,d ->valore); } f2(c,d); } Esercizio 5 ( 3 punti ) SECONDA PROVA Si consideri la seguente d efinizione 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; Codificare una funzione che riceve in input due alber i e restituisce 1 se i due alberi sono identici , 0 altrimenti . int f(tree t1,tree t2) { if(t1==NULL && t2==NULL) return 1; if(t1==NULL || t2==NULL) return 0; return(t1 ->dato==t2 ->dato && f(t1 ->right,t2 ->righ t) && f(t1 ->left,t2 ->lef t) } Eserci zio 6 ( 5 punti ) - SECONDA PROVA Il seguente schema descrive i dati di un social network e consiste di due tabelle (chiavi in maiuscolo): Utente(CODICE, Nome, Score) Raccomanda(CODUTENTE, CODRACCOMANDATO) Utente con codice, nome e indice di gradime nto nel social network (Score). L'utente con codice CodUtente raccomanda l'utente con codice CodRaccomandato. 1) Scrivere una query, in tutti i linguaggi formali e in SQL visti a lezione, che determina l'utente con lo score più elevato 2) Scrivere una q uery Datalog che estrae i nomi degli utenti che, indirettamente, raccomandano se stessi, ossia per i quali esiste una catena di raccomandazioni "ciclica". Ad esempio, se Piero raccomanda Mario, Mario raccomanda Luca e Luca raccomanda Piero, allora Piero, M ario e Luca fanno parte dell'output della query. 3) Scrivere una query in SQL che determina il nome della persona che ha più raccomandazioni