Mathematical Engineering - Informatica A

First partial exam

Politecnico di Milano Dipartimento di Elettronica e Informazione 1 Informatica A – a.a. 0 7/0 8 – 16 /11 /20 07 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.  È possibi le scrivere a matita (e non occorre ricalcare al momento della consegna!).  È vietato utilizzare calcolatrici , telefoni o pc . Chi tenti di farlo ved rà annullata la sua prova.  È ammessa la consulta zion e di libri e appunti , purché con pacata discrezione e sen za 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: 2h 30min Valore indic ativo degli esercizi, voti parziali e voto finale: Esercizio 1 ( 2 punti ) __________ Esercizio 2 ( 3 punti ) __________ Esercizio 3 ( 5 punti ) __________ Esercizio 4 ( 4 punti ) __________ Totale: ( 14 punti ) __________ 2 Esercizio 1 - Algebra di Boole, Aritmetica Binaria , Codifica delle Informazioni (2 punti) (a) Si costruisca la tabella di verità della seguent e espressione booleana in quattro variabili , badando all a precedenz a tra gli operatori logici . Eventualmente si aggiungano le parentesi (1 punto). ( A or (not B) or C ) and ( (not A ) and C or B ) (b) Si stabilisca il minimo numero di bit suff iciente a rappresentare in complemento a due i numeri A  115 dec e B  –37 dec , li si converta , se ne calcoli no la somma (A+B) e la differenza (A –B) in complemento a due e si indic hi se si genera riporto sulla colonna dei bit più signif icativi e se si verif ica overflow (1 punto). 3 Esercizio 2 - Puntatori - (3 punti ) Date le seguenti dichiarazioni e assegnamenti: int main(){ int x, y, z; int *p1, *p2; int **pp1, **pp2; x=4; y=2*x; p1=&y; z=*p1+3; printf(“%d”,z); p2=&z; pp1=&p1; *p2=3; printf(“%d”,*p2); pp2=pp1; **pp2=*p1; printf(“%d”,**pp2); printf(“%d”,x); printf(“%d”,y); printf(“%d”,z); } Scrivere i valori stampati dalle sei ch iamate alla funzione printf nel codice sovrastante. Output prima printf: _______________________________________ Output seconda printf: _______________________________________ Output terza printf: _______________________________________ Out put quarta printf: _______________________________________ Output quinta printf: _______________________________________ Output sesta printf: _______________________________________ 4 Esercizio 3 - Linguaggio C (5 punti) Dato un array quotX di 36 5 valori interi, che rappresentano le quotazioni nell’anno solare corrente del titolo azionario X, si vuole realizzare un programma i n linguaggio C in grado di: a) Inizializzare il contenuto dell’array quotX con valori letti da standard input che devono esser e compresi tra 1 e 100 (estremi inclusi), scartando eventuali valori fuori dall’intervallo (1 punto). b) Salvare in una opportuna/e variabile di tipo struttura (di cui si chiede anche la def inizione d el tipo) la quotazione massima e il primo giorno (espresso come posizione nell’array) in cui tale quotazione è stata memorizzata ( 2 punto) c) Determinare e stampare a video il numero di periodi dell’anno in cui il titolo si è mantenuto costante (ossia, quante volte la medesima quotazione si è presentata in giorni suc cessivi) (2 punti). o Ad esempio, se le quotazioni fossero 10 10 15 14 12 12 12 8 12 12 ….. il titolo avrebbe avuto 3 periodi di quotazione costante. 5 6 Esercizio 4 - Sintesi di codice (4 punti) Le matrici quadrate N x N possono essere naviga te in diversi modi. Due modi tradizionali sono il nested loop e il merge scan. Il nested loop è la navigazione riga per riga (o colonna per colonna), come esemplif icato sotto (nella matrice i numeri rappresenta no l’ordine di navigazione). a) Si scriva una funzione che riceve in input due matrici quadrate A e B e un intero k. A e B sono matrici NxN e k è compreso tra 1 e NxN (non serve verif icare, k è garantito essere compreso tra 1 e NxN) . La funzione deve attraversare, secondo l'o rdine del nested loop per righe , le prime k posizioni sia di A che di B e restituire il numero di interi uguali che si trovano nella stessa posizione in A e in B. (2 punti). Esempio : c on k=12 e le matrici restituisce 4, perché sono uguali l’8 in posizione (1,2), l’87 in (1,4 ), il 9 in (1,7) e il 45 in (2,2). int quantiUgualiConNestedLoop(int A[][N], int B[][N], int k) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6 8 13 87 78 5 9 23 12 45 32 12 5 8 12 87 56 6 9 11 13 45 11 32 7 Il metodo merge scan invece è quello che si muove lungo le diagonali partend o dal punto più in alto a sinistra, come esemplif icato sotto (nella matrice i numeri rappresentano l’ordine di esplorazione ). b) Si scriva una funzione che riceve in input due matrici quadrate A e B e un intero k. A e B sono matri ci NxN e k è compreso tra 1 e NxN (non serve verif icare, k è garantito essere compreso tra 1 e NxN) . La funzione deve attraversare, secondo l'ordine del merge scan, le prime k posizioni sia di A che di B e restituire il numero di interi uguali che si trova no nella stessa posizione in A e in B. (2 punti). Esempio, con k=1 2 e le matrici restituisce 3, perché sono uguali il 3 in posizione (1,4), il 32 in (2,2) e il 10 in (4,1). int quantiUgualiCon MergeScan(int A[][N], int B[][N], int k) 1 2 4 7 11 16 22 29 3 5 8 12 17 23 30 37 6 9 13 18 24 31 38 44 10 14 19 25 32 39 45 50 15 20 26 33 40 46 51 55 21 27 34 41 47 52 56 59 28 35 42 48 53 57 60 62 36 43 49 54 58 61 63 64 23 45 12 3 11 2 32 1 65 1 9 10 3 43 87 3 9 1 32 3 100 2 54 10 8