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 09/09/2002
1a prova scritta

tempo a disposizione: 2 ore

Problema 1 (18 punti)

In un'agenzia di un servizio corriere le richieste giornaliere di ritiro di pacchi da spedire sono memorizzate su di una lista collegata (rappresentata tramite strutture/record e puntatori) in memoria centrale. Per ogni richiesta la lista contiene un elemento che specifica:

• l'orario in cui è stata effettuata la richiesta (rappresentato tramite due campi interi, uno per le ore ed uno per i minuti);
• il nome del mittente (stringa di al più 20 caratteri);
• l'indirizzo del mittente (stringa di al più 40 caratteri);
• la sigla della provincia di destinazione (stringa di 2 caratteri).

La lista è già ordinata per orario crescente.

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 richieste e la sigla P di una provincia, scriva su di un file (per la prova Pascal: di testo o di record, a scelta) l'orario, il nome e l'indirizzo del mittente di tutte le richieste in L destinate alla provincia P, una richiesta per riga.

   Il nome del file deve essere ottenuto concatenando la sigla della provincia P con l'estensione ``.txt''.

3. Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri la lista L delle richieste di spedizione ed un orario T (specificato attraverso ore e minuti), elimini dalla lista L tutte le richieste effettuate più tardi di T, liberando la memoria occupata dagli elementi eliminati. Nell'eliminare gli elementi dalla lista, si deve tenere conto del fatto che la lista è ordinata per orario crescente.

   Per le richieste rimaste in L, la funzione deve inoltre restituire in un opportuno vettore (con una componente per ogni ora della giornata) il numero di richieste effettuate in ciascuna ora della giornata. In altre parole, la componente h del vettore deve contenere il numero di richieste effettuate tra h:00 e h:59.

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 09/09/2002
2a prova scritta

tempo a disposizione: 1 ora

Problema 2 (4 punti)

Siano G ed M rispettivamente il giorno ed il mese di nascita del candidato. Dopo aver convertito in binario G ed M, effettuare (in binario in complemento a 2), le operazioni G+M, G-M e M-G, utilizzando in tutti e tre i casi il minimo numero di bit per rappresentare correttamente operandi e risultato.

Problema 3 (4 punti)

Quali informazioni sono contenute in ciascun record della pila dei record di attivazione. Descrivere la gestione della pila dei record di attivazione in C (risp. Pascal) nel caso di funzione ricorsiva. Si consideri l'esempio del fattoriale di 3.

Problema 4 (4 punti)

Si consideri un albero binario i cui nodi sono etichettati con interi, rappresentato attraverso strutture (risp. record) e puntatori. Si forniscano le opportune dichiarazioni di tipo e l'implementazione in C (risp. Pascal) di algoritmi di ricerca appropriati ai seguenti casi:

1. l'albero è un albero binario di ricerca;
2. non vi è alcuna assunzione sull'occorrenza degli interi nell'albero.

Si discuta e si confronti la complessità computazionale dei due algoritmi.