Mathematical Engineering - Informatica A

Second partial exam

Informatica A – a.a. 10 /11 – Seconda Prova in Itinere Cognome ________________________________ Matricola _______________________ Nome ________________________________ _______ Istruzioni • Non separate questi fogli. Scrivete la solu zione solo sui fogli distribuiti , utilizzando il retro delle pagine in caso di necessità. Cancellate le parti di brutta (o ripudiate) con un tratto di penna . • Ogni parte non cancellata a penna sarà considerata parte integrante della soluzione. • È possibile s crivere a matita (e non ricalcare al momento della consegna!). • È vietato utilizzare calcolatrici o telefoni . Chi tenti di farlo vedrà annullata la sua prova. • È ammessa la consultazione 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: 1h :15m per recupero prima prova + 2 h per seconda prova RECUPERO PRIMA PROVA Esercizio 1.1 ( 6 punti ) __________ Esercizio 1.2 ( 6 punti ) __________ Esercizio 1.3 ( 2 punti ) __________ Totale: ( 14 punti ) __________ SECONDA PROVA Esercizio 2.1 ( 4 punti ) __________ Esercizio 2.2 ( 2 punti ) __________ Eser cizio 2.3 ( 6 punti ) __________ Esercizio 2.4 ( 4 punti ) __________ Totale: ( 16 punti ) __________ Voto finale: __________ Esercizio 1.1 ( 6 punti ) – RECUPERO PRIMA PROVA Un archivio musicale è organizzato nel seguente modo: gli artisti sono disposti in un array e sono ordinati per nome; ogni artista ha associata un array di album organizzati per anno e a parità di anno per ordine alfabetico; ogni album contiene un array di canzoni ordinate per posizione all ’interno dell ’album. Le strutture dati utilizzate sono l e seguenti: typedef struct Song { char * titolo; int durata; int pos; int valido; } Canzone; typedef Canzone Sequenza Canzoni [1000] ; typedef struct Album { char * titolo; int n_canzoni; int anno; SequenzaC anzoni canzoni ; int valido; } Disco; typedef Disco SequenzaDischi[1000]; typedef struct Singer { char * nome; int n_dischi; Sequenz aDischi dischi; int valido; } Artista; typedef Artista Sequenz aArtisti [1000] ; Il campo “valido” p resente in tutte le struct serve a dire se la casella dell’array contiene contenuto valido (nel caso l’attributo ha valore 1) o è da considerarsi vuota (nel caso l’attributo ha valore 0). Si codifichi in C l a seguent e funzion e: int invalida Canzone ( Sequen zaArtisti artisti, char * artista, char * disco, char * canzone) che invalida dal catalogo la canzone qualora questa esista e restituisce 0 in caso di esito positivo, -1 in caso di canzone non esistente. Qualora la canzone sia l ’unica del disco, occorre in oltre invalidare il disco. Infine, se il disco invalidato dovesse essere l ’unico esistente dell ’artista, è necessario invalidare l’artista stesso. Conseguentemente, vanno opportunamente aggiornati i contatori del numero di canzoni e di dischi. 3 Esercizio 1.2 ( 6 punti ) – RECUPERO PRIMA PROVA Si scriva una funzione che riceve in ingresso un vettore di N numeri interi (N è una costante prefissata). Esso contiene dei valori sempre positivi o nulli (mai negativi). Una posizione contenente il numero 0 è da considerare vuota, cioè non contenente alcun valore. La funzione deve calcolare e stampare a video la media dei valori e poi deve modificare i valori che distano più di del 10% del valore della media dalla media stessa mettendoli a 0. La procedura deve esse re ripetuta fino a che non ci sono più valori che vengono modificati. 5 Esercizio 1. 3 ( 2 punti ) – RECUPERO PRIMA PROVA Si costruisca la tabella di verità della seguente espressione booleana. (not A) and ( A and (C or B) ) Si stabi lisca il minimo numero di bit sufficiente a rappresentare in complemento a due i numeri A = -116 e B = –127, li si converta, se ne calcoli la somma (A+B) in complemento a due e si indichi se si genera riporto sulla colonna dei bit più significativi e se si verifica overflow. Esercizio 2.1 ( 4 punti ) - SECONDA PROVA Descrivere il comportamento della funzione m. Determinare cosa verrebbe stampato invocando m(12) e m(14560) #define M 16 … void m(int k) { int* h = (int*) malloc(sizeof(int) * M); f(h + M - 1, k, 0); g(h, M); if (h) free(h); } void f(int * a, int b, int c) { if (c == M) return; c++; *(a) = b % 2; a--; f(a, b/2, c); } void g(int* d, int e) { if (e) { printf("%d ",*d); d++; g(d, e - 1); } else printf(" \n"); } 7 Esercizio 2.2 ( 4 punti ) SECONDA PROVA Sia dato il seguente database relazionale, relativo ad un archivio musicale: ARTISTA ( NomeArtista , DataDiNascita, Genere) ALBUM ( TitoloAlbu m, NomeArtista , Anno) CANZONE ( Titolo , TitoloAlbum , Durata, Posizione) Si assuma che il campo Durata contenga la durata della canzone espressa in secondi. Si scriva in SQL l’interrogazione che estrae gli album di artisti rock realizzati nel 2010 e la loro durata complessiva [2 punt i] Si scriva in SQL l’interrogazione che estrae l’elenco degli artisti le cui canzoni hanno tutte durata inferiore a 4 minuti [2 punti] 9 Esercizio 2.3 ( 4 punti ) SECONDA PROVA Un archivio musicale è organizzato nel seguente mod o: gli artisti sono disposti in una lista e sono ordinati per nome; ogni artista ha associata una lista di album organizzati per anno e a parità di anno per ordine alfabetico; ogni album consta di una lista di canzoni ordinate per posizione all ’interno del l’album. Le strutture dati utilizzate sono le seguenti: typedef struct Song { char * titolo; int durata , pos; struct Song * next; } Canzone; typedef Canzone * ListaCanzoni; typedef st ruct Album { char * titolo; int n_canzoni , anno; ListaCanzoni canzoni; struct Album * next; } Disco; typedef Disco * ListaDischi; typedef struct Singer { char * nome; int n_dischi; ListaDischi dischi; struct Singer * next; } Artista; typedef Artista * ListaArtisti; Si codifichi in C l a seguent e funzion e: int discoPiuLungo(ListaArtisti artisti, int anno) che restituisce la durata del disco più lungo in un determinato anno [ 1 punt o]. Si codifichi in C l a seguent e funzion e: int inserisciCanzone(ListaArtisti Lis , char *artista, char *disc, i nt anno, char *canzone, int durata, int pos izione) che inserisce la canzone qualora l ’artista esista e restituisce 0 in caso di esito positivo, -1 in caso negativo. In particolare, occorre aggiungere il disco qualora questo non esista o aggiornare la list a di canzoni del disco qualora esista. Conseguentemente, vanno opportunamente aggiornati i contatori del numero di canzoni e di dischi. Infine, la funzione ha esito negativo qualora esista un album con medesimo titolo e anno diverso, canzone con medesimo t itolo all ’interno dell ’album o un ’altra canzone nella medesima posizione [3 punti]. 11 Esercizio 2.4 ( 4 punti ) – SECONDA PROVA Si consideri la seguente definizione di un albero binario: typedef struct ET { char * dato; struct ET * left; struct ET * right; } treeNode; typedef treeNode * tree; e la seguente definizione di lista: typedef struct EL { char * dato; struct EL * next; } listNode; typedef listNode * list; Si as suma che gli elementi della lista siano ordinati alfabeticamente. Si codifichi in C l a seguent e funzion e: int contains (tree t, char * word) che restituisce 1 se l ’albero contiene la parola data, 0 altrimenti [ 2 punt i]; Si codifichi in C l a seguent e fun zion e: int isContained (tree, t, list l) che restituisce 1 se almeno una parola in ogni livello dell ’albero è contenuta nella lista [2 punti]. 13