Fondamenti di Informatica

Fondamenti di Informatica

Prof. M. Gavanelli, E. Lamma

5 Luglio 2017

Esercizio (Punti 15 su 31) (1h e 30 min)

Un file di testo, punti1.txt , contiene le coordinate di alcuni punti del piano cartesiano (espresse in centimetri). Ciascuna coordinata è rappresentata da una struttura di due interi positivi, che rappresentano l'ascissa x e l'ordinata y.
Si realizzi un programma C, organizzato in almeno tre funzioni:

Per chi svolge il compito A+B (Ulteriori punti 20 su tot. di 63 per A+B; tempo +30 min):

Nel file punti1.txt  ci le coordinate di, al massimo, 100 punti. Si inseriscano i dati contenuti nel file in un opportuno vettore V di strutture.
Ordinare il vettore V tramite una opportuna chiamata della funzione qsort sul campo ascissa, e a parità di ascissa sul campo ordinata (si noti che è la stessa relazione d'ordine adottata per l'inserimento ordinato nella lista). Stampare poi tutte le coordinate del vettore V ordinato, una coordinata per riga, su file di testo outputAB.txt, da consegnare con il codice sorgente; questa funzione (funzioneAB) riceve come parametri il vettore V e il puntatore al file, più eventuali parametri a scelta, e restituisce void.
NOTA BENE:   Si consegnino i sorgenti, eseguibile e i file di uscita generati. È 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)

Sia data la seguente funzione fun che riceve un carattere e un albero binaro di ricerca di caratteri
int fun(char i, tree T)
{ if (T==NULL) return 0;
  else  if (i==T->value) return 1 + fun(i,T->left); 
        else 
            if (i<T->value) return  fun(i,T->left); 
            else return fun(i,T->right); 
}

Si indichi cosa fa la funzione fun e se ne valuti la complessità asintotica come numero di test i==T->value , nel caso in cui il valore char i passato alla funzione non sia presente nell'albero tree T , e sia:
NOTA BENE:   Si consegni la soluzione in un file teoria.txt .



File translated from TEX by TTH, version 4.08.