Fondamenti di Informatica

Ambiente e Territorio

Appello del 13-7-1998

Esercizio 1 (18 punti)

Una agenzia di viaggi propone alla clientela un’offerta speciale, in cui vengono proposti a prezzi particolarmente vantaggiosi biglietti aerei da e per alcune città in determinati periodi dell’anno. L’offerta coinvolge N città (non più di 20) ed è descritta da una tabella (delle offerte) di N righe ed N colonne (associate alle città). Il generico elemento (i, j) della tabella può essere vuoto (caso in cui l’agenzia non offre biglietti speciali dalla città associata alla riga i a quella associata alla riga j) oppure può contenere informazioni (l’agenzia offre biglietti speciali dalla città associata alla riga i a quella associata alla riga j). In questo ultimo caso l’elemento della tabella contiene il costo del biglietto (intero positivo) e l’indicazione del periodo (o dei periodi) di validità dell’offerta (uno o più fra i seguenti valori: autunno, natale, pasqua, agosto e sempre. Si noti che un’offerta valida sempre è ovviamente valida anche in autunno, natale, pasqua ed agosto). Un possibile esempio è illustrato in Fig. 1.

La tabella può essere rappresentata tramite una matrice Offerta e un vettore Citta: gli elementi della matrice sono in corrispondenza biunivoca con quelli della tabella, mentre quelli del vettore contengono i nomi delle N città (max 12 caratteri; la città nella cella i corrisponde a quella che nella matrice è associata alla riga i e alla colonna i). Ogni cella della matrice corrispondente a un elemento non vuoto della tabella delle offerte è una struttura con due campi: il primo contiene il costo del biglietto aereo e il secondo punta a una lista i cui elementi definiscono il periodo (o i periodi) di validità dell’offerta. Ad esempio, con riferimento alla situazione illustrata in Fig. 1, l’elemento della seconda riga e prima colonna della tabella delle offerte è rappresentato da una struttura con un campo pari a 900.000 e uno che punta a una lista di due elementi, i cui campi informativi contengono rispettivamente i periodi pasqua e natale.

Si noti che non tutti gli elementi della matrice definiscono necessariamente un possibile viaggio: in particolare, quelli della diagonale principale ovviamente non possono corrispondere a viaggio alcuno (che sarebbe da una città alla città stessa!) e ci possono essere collegamenti da una città a un’altra che non fanno parte dell’offerta speciale e quindi non sono presenti nella tabella delle offerte. Si noti inoltre che la presenza di un’offerta dalla città i alla città j non implica necessariamente la presenza di un’offerta simmetrica dalla città j alla città i.

  1. [2 punti] Definire i tipi di dato C adeguati a risolvere i problemi di cui ai successivi punti (2) e (3).
  2. [9 punti] Scrivere una funzione C (o più) che, ricevendo come parametri la matrice Offerta, il vettore Citta, un intero positivo cmax, che rappresenta il costo massimo del biglietto che un cliente è disposto a pagare, una stringa nomcit, che rappresenta il nome della città di partenza del cliente, e un valore perscel, che rappresenta il periodo prescelto dal cliente, costruisca un file di testo SCELTE.TXT in cui sono contenute tutte le possibili destinazioni (con specificato, per ogni destinazione, il relativo costo del biglietto) raggiungibili con un solo biglietto a partire da nomcit, con costo minore o uguale a cmax e nel periodo perscel.
  3. [7 punti] Scrivere una funzione C (o più) che, ricevendo come parametro la matrice Offerta, elimini tutti i viaggi aventi validità sempre.

 

New York

Parigi

Roma

Londra

New York

   

800.000
natale

Parigi

900.000
pasqua e natale

320000
sempre

 

Roma

850.000
agosto

 

 

Londra

 

360.000
pasqua

300.000
autunno

         

Fig. 1: Esempio di tabella delle offerte (N = 4). Si noti che accanto alle quattro righe e alle quattro colonne della tabella sono indicati i nomi delle città corrispondenti.

 

Fondamenti di Informatica

Ambiente e Territorio

Appello del 13-7-1998

Esercizio 2 (4 punti)

Con riferimento al linguaggio C, si considerino

  1. un tipo (struct) ElementoLista, con campi
    1. info, di tipo int,
    2. prox, di tipo Punt (puntatore a ElementoLista);

  2. una funzione ricorsiva Elimina che, dati una lista collegata ed un valore intero, dovrebbe cancellare dalla lista stessa tutti gli elementi con campo info eguale al valore specificato.

/* dichiarazioni di tipo */

struct elem {

int info;

struct elem *prox;

};

typedef struct elem ElementoLista;

typedef ElementoLista *Punt;

void Elimina(Punt p, int val)

{

if(p->info==val) {

Punt next;

next=p->prox;

free(p);

p=next;

} else

p=p->prox;

Elimina(p,val);

return;

}

Il codice C proposto contiene degli errori semantici. Indicarli, spiegarne l’effetto e correggerli.

 

Esercizio 3 (4 punti)

Descrivere la struttura ed i principali componenti di un elaboratore.

 

Esercizio 4 (4 punti)

Si consideri uno schermo di un elaboratore avente risoluzione 1024´ 1536 pixel, in cui ogni pixel può assumere uno fra 256 colori. In tale schermo è visualizzata una immagine costituita semplicemente da un pentagono regolare, i cui vertici sono descritti da coppie di interi (4 byte).

  1. Indicare la quantità di memoria che richiede la memorizzazione raster dell’intera immagine. È possibile risparmiare memoria adottando un qualche metodo di compressione? Se sì, è lecito aspettarsi un considerevole risparmio? Giustificare le asserzioni.
  2. Stimare la quantità di memoria che richiede la memorizzazione vettoriale dell’intera immagine. Giustificare le asserzioni.