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

Appello del 08/04/2002 - 1a prova scritta

tempo a disposizione: 2 ore

Problema 1 (18 punti)

Una scuola di lingue offre 20 corsi di lingua distinti. Ogni corso è identificato da un codice numerico (intero compreso tra 0 e 19). Le informazioni sui partecipanti iscritti ai corsi sono contenute in un file di testo (prova Pascal: di testo o di record, a scelta). Per ogni partecipante sono specificati (separati da spazi bianchi):

• il cognome (stringa di 15 caratteri non contenente spazi bianchi intermedi);
• tre codici di corsi a cui è iscritto il partecipante. Ogni partecipante può essere iscritto ad al più 3 corsi offerti dalla scuola. Se il partecipante è iscritto a meno di 3 corsi, i rimanenti codici sono pari a -1.

Ad esempio, il contenuto di un file di partecipanti potrebbe essere il seguente:

Rossi          12  8 14
Bianchi         7 -1 -1
Verdi           2  0 -1
Aranci         14 19  0
Neri            8  2 14

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 funzioni/procedure Pascal) che, preso in ingresso il nome di un file di partecipanti, restituisca alla funzione (o procedura) chiamante una opportuna struttura di dati che memorizza per ogni corso il numero di partecipanti iscritti. Si noti che il numero di partecipanti iscritti ad un corso potrebbe anche essere 0, ad esempio per il corso 13 nell'esempio di sopra.
3. Progettare una funzione C (o funzioni/procedure Pascal) che, preso in ingresso il nome di un file di partecipanti ed un codice c di un corso, costruisca e restituisca alla funzione (o procedura) chiamante una lista, rappresentata tramite strutture (o record) e puntatori, con tutti i cognomi dei partecipanti al corso c. L'ordine degli elementi nella lista è irrilevante.

   Ad esempio, per il file di sopra ed il corso 14, deve essere restituita la lista costituita dagli elementi (Rossi, Aranci, Neri).

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

Appello del 08/04/2002 - 2a prova scritta

tempo a disposizione: 1 ora

Problema 4 (4 punti)

Considerare il numero m costituito dalle ultime tre cifre (in decimale) del proprio numero di matricola, ignorando le cifre pari a 0. Fornire le rappresentazioni binaria ed esadecimale di tale numero, illustrando il procedimento seguito per il calcolo. Quante cifre sono necessarie in binario ed in esadecimale?

Considerare poi il numero g dato dal proprio giorno di nascita, a cui si è aggiunto 15 se è minore o uguale a 10. Convertire g in binario e calcolare g-m, effettuando le operazioni in complemento a 2.

Problema 3 (4 punti)

Descrivere l'ordinamento a bolle (bubble-sort). Quale algoritmo fra ordinamento per selezione (selection-sort), e ordinamento a bolle (bubble-sort) conviene usare per ordinare un vettore di elementi che è già ``quasi ordinato''? Considerare ad esempio un vettore in cui solo i primi due elementi sono nell'ordine sbagliato. Motivare la risposta.

Problema 2 (4 punti)

Definire un albero binario di ricerca. Inoltre, dato il seguente albero binario, dire se è un albero binario di ricerca:

      50
     /  \ 
    25  70
   /  \
  10  60
     /  \
    40  65

Motivare la risposta data e, se necessario, modificare l'albero in modo da renderlo un albero binario di ricerca.