Corso di Fondamenti di Informatica - A.A. 2001/2002
Corsi di Laurea in Ingegneria Elettronica N.O. e V.O. e
Telecomunicazioni V.O.

Appello del 11/11/2002
1a prova scritta

tempo a disposizione: 2 ore

Problema 1 (18 punti)

Una macchina erogatrice di bibite mantiene le informazioni sulle bibite disponibili in una lista in memoria centrale, rappresentata tramite strutture/record e puntatori. Ciascun elemento della lista contiene:

• il nome della bibita (stringa di al più 20 caratteri);
• il numero di erogazioni della bibita ancora disponibili nella macchina (intero positivo);
• la data di scadenza della bibita (rappresentata attraverso una struttura/record a tre campi interi, per giorno, mese e anno).

Si richiede di risolvere i seguenti punti:

1. Progettare le strutture di dati da utilizzarsi per risolvere i punti 2 e 3.

2. Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri
   • la lista L delle bibite disponibili,
   • una data D ed
   • il nome di un file,
   scriva sul file (per la prova Pascal il file può essere di testo o di record, a scelta), uno per riga, i nomi delle bibite la cui quantità disponibile sia minore di 10, oppure che sono scadute. Una bibita si intende scaduta se la sua data di scadenza precede la data D. Per le bibite scadute, accanto al nome della bibita, deve venire scritto ``scaduta''. Per le altre bibite deve venire scritto il numero di erogazioni ancora disponibili.

3. Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri la lista L delle bibite disponibili ed il nome di una bevanda,
   • decrementi di uno il numero di erogazioni disponibili, se la bevanda è presente nella lista. Inoltre, se tale numero diventa 0, l'elemento corrispondente deve essere eliminato dalla lista, rendendo disponibile la memoria occupata;
   • stampi su standard output un opportuno messaggio di bevanda non disponibile, se la bevanda non è presente nella lista.

Corso di Fondamenti di Informatica - A.A. 2001/2002
Corsi di Laurea in Ingegneria Elettronica N.O. e V.O. e
Telecomunicazioni V.O.

Appello del 11/11/2002
2a prova scritta

tempo a disposizione: 1 ora

Problema 2 (4 punti)

Si consideri il numero decimale dato dalle ultime due cifre del numero di matricola. Se tale numero è minore di 50, si aggiunga 50. Sia N il numero risultante (per esempio, se le ultime due cifre sono 57, N è 57, mentre se le ultime due cifre sono 36, N è 86). Scrivere le rappresentazioni in complemento a due di N e di -N, utilizzando il minimo numero di bit sufficienti. Mettere chiaramente in evidenza il procedimento usato per rispondere al quesito.

Problema 3 (4 punti)

Si descriva un algoritmo di ordinamento di un vettore a scelta (utilizzando pseudocodice o codice C/Pascal) e si illustrino le diverse fasi dell'ordinamento sull'esempio di un vettore di almeno 8 elementi. Si scelga il vettore di esempio in modo che sia significativo, ovvero che metta in evidenza le operazioni effettuate dall'algoritmo nelle singole fasi.

Si discuta inoltre la complessità computazionale dell'algoritmo nel caso migliore e nel caso peggiore, descrivendo per quali vettori si verificano questi casi.

Problema 4 (4 punti)

Si implementi una funzione C/procedura Pascal, che, preso in ingresso un albero binario in cui nodi sono etichettati con interi, stampi su standard output le etichette dei nodi che non sono foglie. L'ordine con cui vengono stampati i nodi deve essere quello risultante da una visita in preordine dell'albero.

Si illustri l'output della funzione sull'esempio di un albero bilanciato di esattamente 12 nodi.