Fondamenti di Informatica
Fondamenti di Informatica
15 Giugno 2017
Esercizio 1 (Punti 15 su 31) (1h e 30 min)
Elena e Marta hanno svolto un periodo di volontariato presso un centro del banco alimentare. Entrambe avevano il compito di censire le derrate alimentari contenute in alcuni scatoloni posti in due diverse stanze. Le ragazze sono state molto efficienti, e hanno creato un file ciascuna.
Elena ha creato un file binario
elena.bin
, dove ha scritto le giacenze dei prodotti
negli scatoloni affidati a lei riportando, per ciascun prodotto:
- il nome del prodotto (stringa di 50 char),
- il numero di scatole (intero).
Ad esempio, per il prodotto cracker si ha:
"cracker" 439
perché ci sono 439 scatole di cracker.
Marta, invece, ha creato un secondo file, di testo,
marta.txt
, dove fortunatamente ha riportato per ciascun prodotto
trovato negli scatoloni affidati a lei
lo
stesso tipo di informazione.
Ad esempio:
| "cracker" 40 |
| "pasta" 100 |
| "tonno" 80 |
se ci sono 40 scatole di cracker, 100 di pasta e 80 di tonno.
Nessuno dei due file risulta ordinato, e uno stesso prodotto può comparire in entrambi i file.
Si realizzi un programma C, contenente almeno le seguenti funzioni, rispettivamente dedicate a:
-
a partire dai file
elena.bin
e
marta.txt
, creare un albero binario di ricerca T in memoria centrale che contiene i dati di tutti i prodotti (in copia unica come nome, e con numero di scatole come somma dei numeri nei due file), ordinato in base al nome del prodotto; la funzioneA riceve come parametri:
- il puntatore ai file,
- il puntatore a T (inizializzato a
NULL
nel
main
),
più eventuali parametri a scelta, e restituisce il puntatore radice di T;
- stampare il contenuto ordinato di T a video; la funzioneB riceve come parametri:
più eventuali parametri a scelta, e restituisce
void
;
- stampare su file di testo
output.txt
l'albero T ; la funzioneC riceve come parametri:
- il puntatore a T,
- il puntatore a file di uscita,
più eventuali parametri a scelta, e restituisce
void
.
-
DOMANDA PER A+B
- caricare i primi 100 elementi (coppie prodotto e intero) del file
marta.txt
in un opportuno array di strutture.
- mostrare a video il contenuto dell'array.
- ordinare l'array in base al nome del prodotto utilizzando la funzione
qsort
.
NOTA BENE:
Si consegnino i sorgenti e il file di uscita generato.
È possibile utilizzare librerie C (ad esempio per le stringhe). Nel caso si strutturi a moduli l'applicazione qualunque libreria utente va riportata nello svolgimento.
Esercizio 2 (Punti 3 su 31) (15 min)
NOTA BENE:
Per questo esercizio si consegni la soluzione in un file
teoria.txt
.
Sia data la seguente funzione
fun
che riceve un carattere e una lista ordinata in senso crescente di caratteri
int fun(char i, list L)
{ if (L==NULL) return 0;
else if (i==L->value) return (1);
else
if (i>L->value) return fun(i,L->next);
else return 0;
}
Si indichi cosa fa la funzione
fun
e se ne valuti la complessità asintotica come numero di test
i==L->value
. Si motivi adeguatamente, individuando gli eventuali casi (migliore, peggiore e medio).
File translated from
TEX
by
TTH,
version 4.08.