Prova scritta del 25 giugno 2018 di Fondamenti di Informatica I (prof. Montessoro) + Fondamenti di Informatica II (prof. Di Gaspero)
Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti 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 1 (10 punti)
L’orario delle lezioni di un corso universitario è rappresentato in un file il cui formato può essere dedotto dall’esempio a lato, dove:
• i nomi dei corsi sono privi di spazi;
• il numero che segue il nome del corso rappresenta il numero di lezioni elencate nel seguito della riga;
• ogni lezione è rappresentata dall’abbreviazione del giorno e dall’intervallo orario, senza spazi (le ore sono sempre numeri interi).
Il numero massimo di corsi è 20, le lezioni si svolgono dal lunedì al venerdì, in orario compreso tra le ore 8 e le 18.
Si scriva un programma in linguaggio C che riceva sulla riga di comando il nome di un file siffatto e stampi le eventuali sovrapposizioni di lezioni.
Relativamente all’esempio sopra riportato il programma dovrà stampare:
sovrapposizione di Fisica con Fondamenti_di_programmazione (LU ore 10) sovrapposizione di Analisi_matematica con Fisica (GI ore 15)
sovrapposizione di Analisi_matematica con Fisica (GI ore 16)
NOTA: si suppongano già disponibili le seguenti funzioni:
void inizializza_matrice (int m[7][24]) /* inizializza tutta la matrice a -1 */
int indice_giorno (char giorno[]) /* riceve il nome abbreviato del giorno e ne restituisce l’indice:
"LU" --> 0, "MA" --> 1, ecc. */
Suggerimento: si rappresentino i corsi in un vettore di stringhe e l’orario settimanale mediante una matrice di interi, uno per ogni ora di ogni giorno, che corrispondono all’indice del nome del corso che viene erogato in tale ora.
Esercizio 2 (12 punti)
Un vettore compatto è una struttura dati sequenziale in cui le eventuali ripetizioni di valori (aventi indici) contigui del vettore sono rappresentate da una coppia (valore, numero di
ripetizioni). Ad esempio, il vettore (tradizionale) {3, 3, 1, 1, 1, 6, 1, 1, 2, 2, 2, 2, 2} può essere rappresentato attraverso questa struttura dati attraverso la sequenza {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5)}.
Fondamenti_di_programmazione 3 LU 8-11 ME 10-12 VE 8-12 Fisica 2 LU 10-12 GI 15-18
Analisi_matematica 2 GI 14-17 VE 13-15
Vogliamo definire un tipo di dato astratto vettore compatto che implementi questa struttura dati.
Le operazioni possibili sui vettori compatti sono le seguenti:
• vettore_compatto crea_vettore_compatto(): crea un nuovo vettore compatto vuoto
• vettore compatto aggiungi_in_coda(vettore_compatto* v, int a): restituisce un nuovo vettore compatto ottenuto aggiungendo il valore a in coda al vettore (allocando
opportunamente la memoria in modo dinamico)
• int cerca_prima_posizione(vettore_compatto v, int x) restituisce il valore della prima posizione (indice, dunque a partire da 0) in cui apparirebbe il valore x nella
rappresentazione come vettore tradizionale
• elimina_vettore_compatto(vettore_compatto* v): elimina il vettore compatto v liberando la memoria eventualmente allocata dinamicamente
A titolo d’esempio, l’esecuzione di aggiungi_in_coda(v, 2) sul vettore riportato in esempio dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 6)}, viceversa, l’esecuzione di aggiungi_in_coda(v, 5) sullo stesso vettore dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5), (5, 1)}. Per ciò che riguarda la funzione di ricerca, invece, l’esecuzione di cerca_prima_posizione(v, 1) sul vettore riportato in esempio dovrebbe restituire il valore 2, che è l’indice della posizione del primo 1 nella
rappresentazione tradizionale mentre l’esecuzione di cerca_prima_posizione(v, 2) dovrebbe restituire 8, indice della prima occorrenza di 2 nella rappresentazione tradizionale.
1. Si definisca un possibile descrittore per il tipo di dato vettore_compatto (in altre parole la typedef struct {…} vettore_compatto) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione dei vettori compatti 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.
3. Si discuta, informalmente, la complessità temporale dell’implementazione delle operazioni di manipolazione espressa in funzione del numero n di sequenze di valori contigui uguali memorizzate nel vettore compatto.
Esercizio 3 (8 punti)
Scrivere una funzione in linguaggio C verifica_negativi(g, s) che, dato un grafo diretto g nei cui vertici v è memorizzato un dato intero v.dato, verifica se, dato un vertice sorgente s, almeno uno dei nodi raggiungibili da s ha un valore del campo dato minore di zero . Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true, in caso contrario la funzione dovrà restituire il valore false.
