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 25/02/2003
1a prova scritta

tempo a disposizione: 2 ore

Problema 1 (18 punti)

Ad uno spettacolo televisivo partecipano 10 scienziati, ciascuno identificato nell'ambito dello spettacolo da un codice (intero compreso tra 0 e 9). Il finanziamento della ricerca dei 10 scienziati è affidato al pubblico televisivo, che deve valutare la qualità della ricerca svolta, e assegnare la propria preferenza ad uno degli scienziati (ad esempio, telefonando ad un certo numero e comunicando il codice dello scienziato al quale dare la preferenza). Per ciascuna preferenza ottenuta dal pubblico lo scienziato viene finanziato con un Euro per la sua ricerca. La sequenza di codici degli scienziati che hanno ricevuto preferenze (corrispondente ad esempio alla sequenza di telefonate ricevute) è memorizzata su di un file di testo (per la prova Pascal, di testo o di record, a scelta). I codici nel file sono separati da spazi. Ad esempio, se il contenuto del file è il seguente:

3 1 8 3 8 0 1 1

questo significa che lo scienziato di codice 0 ha ricevuto 1 preferenza, quello di codice 1 ha ricevuto 3 preferenze, quello di codice 3 ha ricevuto 2 preferenze, quello di codice 8 ha ricevuto 2 preferenze, e tutti gli altri non hanno ricevuto alcuna preferenza.


Si richiede di risolvere i seguenti punti:

  1. Progettare le seguenti strutture dati:
    1. una struttura dati per memorizzare i dati di interesse per uno scienziato, che sono: -
      • il nome (stringa di 30 caratteri),
      • l'area in cui svolge ricerca (stringa di 35 caratteri),
      • il numero di preferenze ricevute;
    2. una struttura dati per memorizzare i dati dei 10 scienziati che partecipano allo spettacolo; ad ogni scienziato deve corrispondere (implicitamente od esplicitamente) un codice identificativo tra 0 e 9;
    3. ulteriori strutture dati necessarie per i punti 2 e 3.

  2. Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri: - aggiorni in base al contenuto del file il numero di preferenze nella struttura dati passata, e restituisca tale struttura dati aggiornata all'unità di programma chiamante.

  3. Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri un intero m ed una struttura dati che memorizza i dati relativi ai 10 scienziati che partecipano allo spettacolo, costruisca e restituisca all'unità di programma chiamante una lista (rappresentata tramite strutture/record e puntatori) contenente i dati degli scienziati da eliminare, ovvero che hanno un numero di preferenze minore di m.


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 25/02/2003
2a prova scritta

tempo a disposizione: 1 ora

Problema 2 (4 punti)

Siano aa è il numero dato dalle ultime due cifre del proprio anno di nascita, e xx il numero pari al proprio giorno di nascita incrementato di 20 se è minore di 10. Si eseguano le seguenti operazioni in complemento a 2, scegliendo per ciascuna operazione il numero minimo di bit necessari a rappresentare gli operandi ed il risultato (dire explicitamente quale è tale numero minimo di bit):

  1. aa + xx
  2. aa - xx
  3. xx - aa
Illustrare esplicitamente il procedimento seguito per ottenere la rappresentazione in complemento a due degli operandi.

Problema 3 (4 punti)

Si illustrino i concetti relativi all'algoritmo per la ricerca binaria, e se ne fornisca un'implementazione sotto forma di funzione C/Pascal, assumendo di dover cercare un intero in un vettore di interi. Si discuta inoltre la complessità computazionale dell'algoritmo nel caso migliore e nel caso peggiore.

Problema 4 (4 punti)

Si descriva il tipo di dato pila e si illustrino le sue possibili rappresentazioni in C/Pascal. Per una delle rappresentazioni, si implementi in C/Pascal l'operazione di estrazione di un elemento dalla pila.