Fondamenti di Informatica

Fondamenti di Informatica

Prof. M. Gavanelli, E. Lamma

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: 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:
  1. 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: più eventuali parametri a scelta, e restituisce il puntatore radice di T;
  2. stampare il contenuto ordinato di T a video; la funzioneB riceve come parametri: più eventuali parametri a scelta, e restituisce void ;
  3. stampare su file di testo output.txt l'albero T ; la funzioneC riceve come parametri: più eventuali parametri a scelta, e restituisce void .
  4. DOMANDA PER A+B
    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.