Università di Roma ``La Sapienza'' - Facoltà di Ingegneria
Corso di Fondamenti di Informatica - A.A.2000/2001
Corso di Laurea in Ingegneria Elettronica N.O.
Appello del 18 giugno 2001 -- 1a prova scritta
tempo a disposizione: 2 ore

Problema 1 (18 punti)

Un sito web mette a disposizione delle play list che sono file contenenti un elenco di brani mp3 con relativo link al sito dove il brano è presente. In particolare ogni record di una play list ha la seguente struttura:

nomebrano  artista  durata  link

dove

  1. Progettare le strutture dati C da utilizzarsi per risolvere i punti 2 e 3. L'eventuale uso di variabili globali va opportunamente motivato.

  2. Per evitare tempi di download per un singolo brano troppo lunghi, si è interessati a selezionare da una play list i brani di durata inferiore ad una certa soglia.

    Progettare una funzione C che prenda come parametri di ingresso

    e costruisca e restituisca in modo opportuno alla funzione chiamante una lista collegata, rappresentata tramite strutture (allocate dinamicamente) e puntatori, contenente tutti i record di nf relativi ai brani di durata inferiore alla soglia s. I brani devono comparire nella lista nello stesso ordine in cui compaiono nel file.

  3. I lettori mp3 sono dotati di una memoria limitata e quindi possono memorizzare solamente brani la cui durata complessiva non deve superare un determinato valore massimo.

    Progettare una funzione C che prenda come parametri di ingresso

    e modifichi l mantenendo i primi record di l la cui durata complessiva è minore di d, ed eliminando i record rimanenti. Si tenga presente che l'eliminazione dei record deve essere fatta liberando la memoria occupata.

Ad esempio, se il file nf contiene la seguente play list: 


all_you_need_is_love    beatles         04:30  http://www.beatles.com/mp3/all_you_need.mp3
jumping_jack_flash      rolling_stones  03:22  http://www.rollingstones.com/downloads/jjf.mp3
symphathy_for_the_devil rolling_stones  11:23  http://www.rollingstones.com/downloads/sd.mp3
tangled_up_in_blue      bob_dylan       05:11  http://www.bobdylan.com/mp3/tub75.mp3
penny_lane              beatles         05:20  http://www.beatles.com/mp3/penny_lane.mp3

la funzione al punto 2, se invocata con la soglia 5:15, deve costruire la seguente lista: 


        +-----------+----+       +-----------+----+       +-----------+----+
        |all_you... |    |       |jumping... |    |       |tangled... |   /|
   ---->|beatles    | ---------->|rolling... | ---------->|bob_dylan  |  / |
        |4 30 http..|    |       |3 22 http..|    |       |5 11 http..| /  |
        +-----------+----+       +-----------+----+       +-----------+----+
Inoltre, se la funzione al punto 3 viene invocata passandole come parametri tale lista e la durata 8:00, deve eliminare dalla lista solo l'ultimo elemento. Se la durata è invece 3:50, deve eliminare dalla lista tutti gli elementi.

Suggerimento: per i calcoli sui tempi, si consiglia di trasformare minuti e secondi in secondi.

Università di Roma ``La Sapienza''
Facoltà di Ingegneria
Corso di Fondamenti di Informatica - A.A.2000/2001
Corso di Laurea in Ingegneria Elettronica N.O.
Appello del 18 giugno 2001 -- 2a prova scritta
tempo a disposizione: 1 ora


Problema 2 (4 punti)

Descrivere un algoritmo di ordinamento a scelta (utilizzando pseudocodice o codice C) e discuterne la complessità computazionale. Fornire un esempio di vettore per cui l'algoritmo esibisce il comportamento del caso peggiore.


Problema 3 (4 punti)

Si rappresentino in complemento a due il proprio giorno di nascita e le ultime due cifre del proprio anno di nascita e se ne calcolino la somma e la differenza. Utilizzare il minimo numero di bit necessari per non avere overflow nelle operazioni.


Problema 4 (4 punti)

Si consideri il seguente programma C: 


#include <stdio.h>

int cosafa (int x)
{
  if (x == 0)
     return 0;
  else if (x % 2 == 0)
     return x + cosafa(x-2);
  else
     return cosafa(x-1);
}

int main(void)
{
  printf("%d\n", cosafa(5));
}