Mathematical Engineering - Informatica A

Full exam

Informatica A Cognome ________________________________ Matricola _______________________ Nome ________________________________ _______ Istruzioni • Non separate questi fogli. Scrivete la soluzione solo sui fogli distribuiti , utili zzando 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 scrivere a matita (e non ricalcare al mo mento 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 alt ri 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: 2h3 0m Esercizio 1 ( 2 punti ) __________ Esercizio 2 ( 4 punti ) __________ Esercizi o 3 ( 4 punti ) __________ Esercizio 4 ( 16 punti ) __________ Esercizio 5 ( 4 punti ) __________ Totale: ( 30 punti ) __________ Voto finale: __________ Esercizio 1 ( 2 punti ) Si costruisca la tabella di verità della seguente espressione booleana. ( not ( ( A and ( not B ) ) ) or ( ( not A ) and B ) ) or ( C and ( not C ) ) Si stabilisca il minimo numero di bit sufficiente a rappresentare in complemento a due i numeri A = -122 e B = -160, li si converta, s i calcoli A+B in complemento a due e si indichi se si genera riporto sulla colonna dei bit più significativi e se si verifica overflow . 3 Esercizio 2 ( 4 punti ) Il seguente schema descrive la base di dati usata per gestire delle gare automobilistiche su un unico circuito . CONCO RRENTE (Codice , Nome, Cognome) GRADUATORIA (CodiceConcorrente , MediaTempi) GARA (Codice , Nome, NumConcorrenti) ESITO GARA (CodiceGara, CodiceConcorrente , Tempo, Posizione) La tabella Graduatoria contiene le medie delle gare per ogni conco rrente Estrarre i l nome e il cognome dei concorrent i con la media dei tempi inferiore alla media delle medie (2 punti) . Il seguente schema descrive la base di dati usata per gestire delle gare automobilistiche su un unico circuito. CONCORRENTE (Codice , Nome, Cognome) GRADUATORIA (CodiceConcorrente , MediaTempi) GARA (Codice , Nome, NumConcorrenti) ESITO GARA (CodiceGara, CodiceConcorrente , Tempo, Posizione) La tabella Graduatoria contiene le medie delle gare per ogni concorrente Estra rre il nome e il cognome dei concorrenti che sono sempre arrivati ultimi nelle gar e a cui hanno partecipato (2 punti). 5 Esercizio 3 ( 4 punti ) typedef struct n ode { char c[8]; struct n *ne at; } elem ; elem * f( elem * a, char * s ) { elem * n; if( s trlen(s) > 0 ) { n = ( elem *) malloc(sizeof( elem )); n->ne at = a; strcpy( n ->c, s++ ); n->c[1] = ' \0'; *(n ->c) += strlen(s); return f( n, s ); } return a; } void printr( elem * r ) { if( r ) { printf("%s", r ->c); printr( r ->ne at ); } } int main() { char p[] = "AMNG" ; printr( f( NULL, p ) ); return 0; } Si indichi la linea stampata dal programma sullo standard output. Esercizio 4 ( 16 punti ) Due parole p, q si definiscono allacciabili se un su ffisso proprio s di p è anche pre fisso proprio di q, cioè hanno la forma p=w 1s q= sw2 (dove s è proprio se è lungo almeno 2 lettere). Esempi di parole allacciabili : (oca, carina)  ocarina (isola, lamento)  iso lamento (coraggio , raggio)  coraggio (bugiardi, giardino)  bu giardi no (dei farmaci) (spora, radici)  spo radici (imposta, stazione)  impo sta zione (violoncello, ce llophane)  violon cello phane Malgrado le coppie di parole allacciabili più interessanti siano quelle in cui la parola w 1sw 2 (ott enuta fattorizzando il suf - /pre -fisso) è una parola di senso compiuto, anche l’orrenda coppia (violoncello, cellophane) rispet ta la definizione. Esempi di coppie non allacciabili : (violon cell o, cell ulare), (corp o, orazione) Si codifichi in C la funzione int misuraoverlap( char *p, char *q) che restituisce la lunghezza del massimo suf -/pre -fisso proprio in comune tra p e q (cioè la lunghezza di s, se p=w 1s q=sw 2). 7 Si codifichi poi la funzione void allaccia( char *p, char *q, char *t) che riceve due parole p e q come parametri e inserisce nella stringa t la parola ottenuta dall’allacciatura che fattorizza la massima sovrapposizione, oppure la stringa vuota se le parole non sono allacciabili Si considerino delle sequenze di parole rappresentate da liste di stringhe definite come segue typedef struct n d { char * word; struct nd * next; } parola; typedef parola * Sequenza; Allacciando tra loro parole consecutive in una sequenza si può progressivamente ridurne la lunghezza (tanto quanto lo permettono le parole), al limite anche fino a ottenere una sequenz a di una sola parola. Si codifichi in C una funzione ... shrink( ...) che riceve una sequenza come parametro e la modifica riducendola alla sequenza di lunghezza minima, allacciando tutte le parole consecutive allacciabili. Si badi a non lasciare memoria all ocata e non più raggiungibile da alcun puntatore (memory leaks ) Ad esempio si veda come “collassano” le sequenze seguenti: regola →lazio →azione  regolazione antro →tropo →polo →logo →laurea →reato  antropologo →laureato intimi →timida →datori →torio  intimidatorio rostro →zangola →trogolo  rostro →zangola →trogolo 9 11 Esercizio 5 ( 4 punti ) Si consi deri la seguente definizione di un albero ter nario: typedef struct ET { int dato; struct ET * left, * center, * right; } treeNode; typedef treeNode * tree; Si codifichi in C la seguente funzione: int f(tree t) che restituisce 1 se in tutti i cammini dalle foglie alla radice il valore contenuto nel campo “dato” di un nodo (nodo radice escluso) non è superiore a 2 più il valore contenuto nel campo “dato” del padre .