Corso di Fondamenti di Informatica - A.A. 2000/2001
Corsi di Laurea in Ingegneria Elettronica (V.O.) e
Ingegneria delle Telecomunicazioni (V.O.)

Appello straordinario del 21 gennaio 2002 - 1a prova scritta

tempo a disposizione: 2 ore

Problema 1 (18 punti)

Una agenzia di viaggi memorizza su di un file di testo le temperature di località di interesse. Ogni linea del file contiene le seguenti informazioni riguardo ad una località:

• il nome della località, rappresentato da una stringa di 20 caratteri (inclusi eventuali spazi bianchi finali e priva di spazi bianchi interni);
• la temperatura della località, rappresentata da un intero.

Ad esempio un file di temperature potrebbe contenere:

londra              15
vienna              18
roma                32
parigi              22
amsterdam           12
madrid              38

Si chiede di risolvere i seguenti punti:

1. Progettare le strutture dati C (risp. Pascal) da utilizzarsi per risolvere i punti seguenti. L'uso di eventuali variabili globali va opportunamente motivato.
2. Progettare una funzione C (risp. procedura o funzione Pascal) che, preso come parametro il nome di un file di temperature, costruisca e restituisca all'unità chiamante una lista di record contenente un elemento per ogni località nel file. Ogni elemento della lista deve contenere il nome della località ed un codice, stabilito in base alla temperatura della località al seguente modo:
   • `f' se la temperatura è minore di 20;
   • `t' se la temperatura è compresa tra 20 e 30;
   • `c' se la temperatura è maggiore di 30.
   L'ordine degli elementi nella lista è irrilevante.
3. Progettare una funzione C (risp. procedura o funzione Pascal) che, presi come parametri una lista come quella costruita al punto (2) ed il nome di un file, scriva sul file, una per riga, le località con il loro codice per la temperatura, ordinate secondo tale codice. Devono cioè essere scritte sul file prima tutte le località calde (`c'), poi tutte quelle temperate (`t'), ed infine tutte quelle fredde (`f'). L'ordine delle località aventi lo stesso codice di temperatura è irrilevante. Inoltre, la funzione deve cancellare la lista passata come parametro, liberando la memoria occupata dai suoi elementi.

   Ad esempio, per il file di temperature di sopra, il file prodotto potrebbe contenere:

   roma                c
   madrid              c
   parigi              t
   londra              f
   vienna              f
   amsterdam           f
   

Corso di Fondamenti di Informatica - A.A. 2000/2001
Corsi di Laurea in Ingegneria Elettronica (V.O.) e
Ingegneria delle Telecomunicazioni (V.O.)

Appello straordinario del 21 gennaio 2002 - 2a prova scritta

tempo a disposizione: 1 ora

Problema 2 (4 punti)

Convertire giorno, mese, ed anno (a 4 cifre) della propria data di nascita dalla rappresentazione decimale a quella binaria in complemento a 2, utilizzando per ciascuno dei tre numeri il minimo numero di bit necessari per non avere overflow. Sottrarre il mese dal giorno ed il giorno dal mese, utilizzando la rappresentazione binaria in complemento a 2 (se giorno e mese di nascita coincidono, utilizzare al posto del giorno le ultime due cifre dell'anno di nascita).

Problema 3 (4 punti)

Descrivere il tipo di dato albero binario e fornire una sua rappresentazione in C (risp. Pascal). Fornire l'implementazione in C (risp. Pascal) di un algoritmo di visita a scelta.

Qual'è l'altezza massima (in funzione del numero di nodi dell'albero) che la pila dei record di attivazione raggiunge durante l'esecuzione della visita, nel caso migliore ed in quello peggiore?

Problema 4 (4 punti)

Quali delle seguenti affermazioni sono corrette e quali no? Motivare le risposte date.

1. Per poter valutare la complessità di un algoritmo è necessario conoscere la dimensione massima dei dati in ingresso.
2. Dato un certo problema, si considerino un programma A che implementa un algoritmo esponenziale per risolverlo, ed un programma B che implementa un algoritmo polinomiale per risolverlo. Allora il tempo di esecuzione di A è maggiore del tempo di esecuzione di B, per qualsiasi input dato in ingresso ai due programmi.
3. Il costo di esecuzione di un'istruzione dominante è pari al costo di esecuzione dell'intero programma, a meno di un fattore moltiplicativo costante.
4. Un problema ha complessità O(f(n)) se tutti gli algoritmi che lo risolvono hanno complessità O(f(n)).