Mathematical Engineering - Informatica A

First partial exam

Politecnico di Milano Dipartimento di Elettronica e Informazione Informatica A – a.a. 0 7/0 8 – Primo Appello – 25 /2/200 8 Cognome ________________________________ Matricola _______________________ Nome ________________________________ Firma _______________________ Istruzioni • Non separate questi fogl i. 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 uz ione. • È 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 ( 5 punti ) __________ Esercizio 3 ( 4 punti ) __________ Esercizio 4 ( 10 punti ) __________ Esercizio 5 ( 5 punti ) __________ Esercizio 6 ( 3 punti ) __________ Totale: ( 29 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). ( A and ( B or ( not C ) ) ) or ( ( A and ( not C ) ) or B ) (b) Si stabilisca il minimo numero di bit sufficiente a rappresentare in complemento a due i numeri A = 46 dec e B = –108 dec , li si converta , se n e calcolino 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 ( 5 punti ) Il seguente schema rappresenta le informa zioni riguardo all e elezioni (con un sistema elettorale di fantasia) : CANDIDATO ( CodiceFiscale , Cognome , Nome , NomeListaDiAppartenenza, PosizioneInLista, VotiRaccolti ) LISTA ( Nome , Simbolo ) 1. Scrivere in tutti e tre i linguaggi formali e in SQL l’inter rogazione che estrae i l candidato che ha raccolto personalmente il maggior numero di voti . 2. Scrivere in SQL l’interrogazione che estrae la lista i cui candidati hanno raccolto complessivamente più voti. SELECT Nome, Cognome FROM Candidato WHERE VotiRaccolti >= all SELECT VotiRaccolti FROM Candidato SELECT Nome FROM Lista JOIN Candidato ON NomeListaDiAppartenenza = Nome GROUP BY Nome HAVING sum(VotiRaccolti) >= all SELECT sum(VotiRaccolti) FROM Lista JOIN Candidato ON NomeListaDiAppartenenza = Nome GROUP BY Nome 4 5 Esercizio 3 ( 4 punti ) Si imple menti una funzione che riceve in input una matrice NxM di float. Definito “picco” un numero circondato in tutte le otto posizioni intorno solo da numeri inferiori alla sua metà, la funzione conta il numero di “picchi” della matrice (attenzione a gestire co rrettamente gli elementi ai bordi della matrice) . 6 Esercizio 4 ( 10 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; La funzione deve verificare se l’andamento della lista è ondulatorio, cioè se non capita mai che tre numeri consecutivi siano in ordine crescente o decrescente. La funzione restituisce 1 se l’andamento è ondulatorio, 0 altrimenti . La funzione sia così definita: int ondulatoria (Lista lis); #include #include typedef struct Node { int numero; struct Node * next; } Nodo; typedef Nodo * Lista; int Dimensione( Lista lista) { int count = 0; Lista cur = l ista; while (cur!= NULL ) { cur = cur ->next ; count++; } return count; } int ondulatoria( Lista lis){ if(Dimensione (lis)< 3) printf ("ERR: lista troppo corta" ); while (lis ->next ->next !=NULL ){ if(lis ->numero < lis ->next ->numero && lis ->next ->numero < lis ->next ->next ->numero ) return 0; else if ((lis ->numero < lis ->next ->numero && lis ->next ->numero < lis ->next ->next ->numero )) return 0; } return 1; } 7 Una lista è ondulatoria cres cente se mai tre numeri consecutivi sono in ordine crescente o decrescente ma sempre il primo e il terzo di tre consecutivi sono in ordine crescente. Defin ire una funzione che accetta come parametri una lista e restituisce 1 se la condizione è verificata, 0 altrimenti . La funzione sia così definita: int ondulatoriaCrescente (Lista lis); #include #include typedef struct Node { int numero; struct Node * next; } Nodo; typedef Nodo * Lista; int Dimensione( Lista lista) { int count = 0; Lista cur = lista; while (cur!= NULL ) { cur = cur ->next ; count++; } return count; } int ondulatoria( Lista lis){ if(Dimensione (lis)< 3) printf ("ERR: lista troppo corta" ); while (lis ->next ->next !=NULL ){ if(lis ->numero < lis ->next ->numero && lis ->next ->numero < lis ->next ->next ->numero ) return 0; else if ((lis ->numero < lis ->next ->numero && lis ->next ->numero < lis ->next ->next ->numero )) return 0; } return 1; } int ondulatoriaCrescente( Lista lis){ if(Dimensione (lis)< 3) printf ("ERR: lista troppo corta" ); if(ondulatoria (lis)== 0) while (lis ->next ->next !=NULL ){ if(lis ->numero < lis ->next ->next ->numero ) return 1; } return 0; } 8 Definiamo prefisso di lunghezza p di una lista la lista ottenuta prendendo i primi p elementi della lista nello stesso ordine della lista originaria. Ad esempio data la lista -> 5 -> 6 -> 9 -> 2 -> 4 -> 1 il prefisso di lunghezza 3 è -> 5 -> 6 -> 9 Avendo a disposizione il tipo typedef struct NodeList { Lista lis ; struct Node List * next; } NodoLista; typedef NodoLista * ListaDiListe; Definire un a funzione ListaDiListe generaListaPrefis si (Lista lis , int k ); ch e ricevuta in input una lista e un intero k restituisce la lista delle k liste costruite prendendo i k prefissi di lunghezza compresa tra 1 e k. 9 Esercizio 5 ( 5 punti ) Si consideri no due list e concatenat e semplic i di dati , un a contenente dati di persone e relative patenti, una contenente dati di multe. La struttura della list e è: typedef struct Date { int giorno; int mese ; int anno; } Data; typedef struct Item { int numeroDiPatente ; char * cognome; char * nome; char * professione; int punti; struct Item * next } Patente; typedef Patente * ListaDiPatenti; typedef struct Node { int numeroDiPatente ; int puntiTolti; Data data; struct Node * next; } Multa ; typedef Multa * Lista DiMulte ; La lista di multe è ordinata per data. Si supponga di avere a dis posizione una funzione (che non deve essere codificata, ma solo usata) che riceve in input due date e restituisce la loro distanza in giorni , definita: int distanza(Data d1, Data d2); Si ricorda inoltre che la fun zione int strcmp(char *s1, char *s2); rest ituisce un intero minore, uguale o maggiore di 0 a seconda che s1 sia rispettivamente minore, uguale o maggiore di s2. Si codifichi una funzione che , ricev uta in ingresso una lista di patenti e una lista di multe, proceda a modificare il campo punti delle patenti dei multati togliendo i punti previsti dalla multa e, a quelle persone che già avevano preso una multa negli ultimi 30 giorni, tolga ulteriori due punti . 10 11 Esercizio 6 ( 3 punti ) Si consideri la seguente definizione di un albero binario (binari o=con due rami in ogni nodo): typedef struct EL { int dato; struct EL * left, struct EL * right; } node; typedef node * tree; Si scriva una funzione che prende in ingresso un albero binario completo (tutti i nod i o sono foglie o hanno 2 figli, tutte le foglie sono alla stessa profondità) e un array di dimensione N (con N sufficientemente grande da superare sempre per ipotesi che non serve verificare il numero di nodi dell’albero). Si faccia in modo che gli eleme nti dell’albero vengano inseriti nell ’array in modo da soddi sfare le seguenti proprietà (tenendo conto che le posizioni si contano da 0) : 1. I figli dell’elemento che si trov erà nell ’array nella posizione i si trov eranno nell ’array nelle posizioni 2i+1 e 2i+ 2. 2. Il padre dell’elemento che si trov erà nell ’array nella posizione i si trov erà (se esiste) nell ’arr ay nella posizione (i - 1)/2 . Introdurre tutte le funzioni che si ritiene possano servire a rendere la soluzione più modulare, chiara e leggibile . 12 13