Prova scritta del 3 settembre 2018 di Fondamenti di Programmazione e Strutture Dati e Algoritmi Per studenti di Ing. Elettronica e Ing. Gestionale immatricolati a partire dall’anno 2017-18
DURATA DELLA PROVA: 3 ORE A pena di annullamento immediato della prova:
1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.
2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula
Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
Esercizio 2 (13 punti)
Si consideri il seguente tipo di dato struct persona
{
char nome[32];
int interessi[N];
};
che rappresenta una persona, in cui in vettore interessi rappresenta il valore tra 1 e 10 che la persona attribuisce ai suoi N interessi (ad es. cinema, calcio, . . . ). La costante N e gli interessi rappresentati sono uguali per tutte le persone.
Si scriva la funzione una funzione che riceva come parametri una variabile p di tipo struct persona, un vettore vp di tipo struct persona e la dimensione n del vettore. La funzione deve stampare gli indici delle persone (una o più) in vp che hanno la minima differenza di interessi con p.
La minima differenza, che dovrà essere calcolata da una funzione ausiliaria, si calcola come media delle differenze in valore assoluto tra i valori di pari indice.
Ad esempio, se il vettore contiene i dati riportati a lato (con N = 4 e n = 5) e la persona p ha interessi 1, 2, 3 e 5, la funzione deve stampare gli indici 0 e 2 (corrispondenti a Maria e Paolo), con i quali la media delle differenze è minima, pari a 0.25.
Esercizio 2 (5 punti)
Si consideri una libreria in linguaggio C per manipolare file audio così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define SAMPLE(wave, channel, offset) \ wave.wavedata.sample \ [2 * (offset) + (channel)]
#define FMTPCM 1
#define SAMPLINGRATE 44100
#define CHANNELS 2
#define BITSPERSAMPLE 16
#define LEFT 0
#define RIGHT 1
#define RIFF_ID "RIFF"
#define WAV_ID "WAVE"
#define FMT_ID "fmt "
#define DATA_ID "data"
typedef struct tagRIFFHEADER {
char riffid[4];
dword FileSize;
char waveid[4];
} RIFFHEADER;
typedef struct tagFMTHEADER { char fmtid[4];
dword fmtsize;
word format;
word channels;
dword SampleRate;
dword BytesPerSecond;
word BlockAlign;
word BitsPerSample;
} FMTHEADER;
typedef struct tagWAVEDATA {
char dataid[4];
dword DataSize;
signed short int *sample;
} WAVEDATA;
typedef struct tagWAVE { RIFFHEADER riffheader;
FMTHEADER fmtheader;
unsigned long int numofstereosamples;
WAVEDATA wavedata;
} WAVE;
void WriteWave (WAVE wave, FILE *fp);
WAVE ReadWave (FILE *fp);
WAVE CreateEmptyCDaudioWave (unsigned long int numofstereosamples);
void ReleaseWaveData (WAVE *wave);
L’effetto di “fade out”, spesso presente alla fine delle canzoni di musica leggera, consiste nel ridurre il volume del suono fino a zero, a partire da alcuni secondi prima della fine del brano. L’andamento della diminuzione del volume può essere lineare, esponenziale, logaritmico o presentare profili complessi. Ai fini dell’esercizio si consideri soltanto l’andamento lineare.
nome interessi Maria 1 3 3 5 Giulio 2 4 4 6 Mario 1 2 3 4 Paola 2 3 1 2 Paolo 2 3 1 7
-
*
3 +
4 1
/
5 2
Si scriva una funzione in linguaggio C che riceva come argomenti i puntatori a due file wave (già aperti in modalità “rb” e “wb” rispettivamente) e un numero reale. I due file rappresentano la forma d’onda di ingresso e di uscita, mentre il numero reale rappresenta la durata in secondi dell’effetto di fade out. Il programma deve scrivere nel secondo file la forma d’onda del primo a cui sia applicato tale effetto per il numero di secondi specificato. Se la forma d’onda di ingresso ha durata inferiore al numero di secondi specificato, il programma deve terminare segnalando errore.
Esempio:onda sinusoidale a 20 Hz della durata di 4 secondi (a sinistra) a cui è applicato l’effetto di fade out lineare della durata di un secondo (a destra).
Esercizio 3 (12 punti)
Un modo per rappresentare le espressioni aritmetiche è attraverso degli alberi binari in cui ciascuna sottoespressione corrisponde ad un sottoalbero in cui l’operatore aritmetico utilizzato è la radice del sottoalbero e le ulteriori sottoespressioni (costanti numeriche oppure sottoespressioni complesse) sono rappresentati dai sottoalberi sinistro e destro.
Ad esempio l’espressione 3 * (4 + 1) - 5 / 2 è rappresentata dall’albero riportato nella figura.
Vogliamo definire l’implementazione di un tipo di dato astratto espressione che gestisca le strutture dati necessarie per questa rappresentazione. Per farlo, c’è la necessità di adattare la definizione dei nodi di un albero binario, che
chiameremo nodo_espressione, in modo da rappresentare entità di tipo differente (numeri interi e operatori).
Le operazioni possibili sono le seguenti:
• espressione crea_espressione(): crea una nuova espressione vuota
• espressione rimpiazza_albero(nodo_espressione *r) rimpiazza l’espressione attualmente memorizzata nel descrittore distruggendo l’albero attualmente presente e rimpiazzandolo con quello passato alla funzione; in particolare se il nodo_espressione passato come parametro è NULL il risultato dovrà essere un espressione vuota
• int calcola_risultato(espressione e) calcola il risultato dell’espressione e effettuando tutte le operazioni descritte nell’albero; ad esempio nel caso dell’espressione in figura il risultato dovrà essere 13 In aggiunga si considerino le seguenti operazioni sulla struttura nodo_espressione
• nodo_espressione* crea_costante(int valore) che crea un nodo_espressione che rappresenta la costante il cui valore è passato come parametro
• void rimpiazza_albero(espressione* e, nodo_espressione *r) modifica l’espressione e, rimpiazzando il nodo_espressione attualmente memorizzata nel descrittore distruggendo l’albero attualmente presente e rimpiazzandolo con quello passato alla funzione; in particolare se il nodo_espressione passato come parametro è NULL il risultato dovrà essere un espressione vuota
1. Si definisca il descrittore per il tipo di dato espressione (in altre parole la typedef struct {}
espressione) e la struct nodo_espressione
2. Si implementino in linguaggio C le operazioni di manipolazione descritte in precedenza. Qualora fosse necessario si assuma l’esistenza delle funzioni di manipolazione delle strutture dati utilizzate nel descrittore, scelte fra quelle studiate durante il corso.
