Esercizio di esame 26/3/2002

Canale A-L (Liberatore)/ Parte I

Esercizio 1

Scrivere un metodo (non statico) da inserire nella classe Lista, che controlla se la lista è ordinata. Il metodo non ha parametri (a parte l'oggetto di invocazione) e restituisce un booleano che vale true se la lista è ordinata, ossia se il primo elemento è maggiore del secondo, il secondo è maggiore del terzo, ecc. Il metodo non deve stampare nulla.

Soluzione

Il metodo deve controllare se ogni elemento della lista è minore o uguale a quello che lo segue. L'algoritmo è semplicemente:

per ogni elemento della lista, se è maggiore di quello seguente, ritorna false
alla fine della scansione, ritorna true

La prima versione usa il normale ciclo di scansione: s.getVal() è l'elemento che si trova nell'oggetto puntato da s. Per trovare l'elemento successivo: s.getNext() è il riferimento all'oggetto che segue, quindi s.getNext().getVal() è l'intero che si trova dentro.

  public boolean inOrdine() {
    Catena s=c;

    while(s!=null) {
      if(s.getVal()>s.getNext().getVal())
        return false;
      s=s.getNext();
    }

    return true;
  }

Vanno ora considerati i casi particolari. Per il momento, la catena vuota non crea problemi (verrà rivista più avanti). Al contrario, ci sono dei problemi quando si arriva all'ultimo elemento della lista. Infatti, quando s è il riferimento all'ultimo elemento della lista, s.getNext() vale null.

Il problema è anche abbastanza chiaro intuitivamente: dato che confronto ogni elemento con il successivo, non posso fare l'ultimo confronto usando l'ultimo elemento (che non ha un elemento successivo). Mi devo quindi fermare quando s è un puntatore al penultimo elemento. In altre parole, quando arrivo alla condizione s.getNext()==null, allora s punta all'ultimo elemento, e quindi si deve uscire:

  public boolean inOrdine() {
    Catena s=c;

    while(s.getNext()!=null) {
      if(s.getVal()>s.getNext().getVal())
        return false;
      s=s.getNext();
    }

    return true;
  }

Rientra a questo punto in gioco il problema della lista vuota. In questo caso, infatti, s vale inizialmente null, per cui la verifica di condizione s.getNext()!=null produce un errore, dato che s.getNext() è equivalente a null.getNext().

Occorre quindi mettere un controllo sulla lista vuota prima di iniziare il ciclo.

  public boolean inOrdine() {
    Catena s=c;

    if(s==null)
      return true;

    while(s.getNext()!=null) {
      if(s.getVal()>s.getNext().getVal())
        return false;
      s=s.getNext();
    }

    return true;
  }

Si vede poi facilmente che, nel caso di lista di un solo elemento, non ci sono difficoltà: il ciclo non viene mai eseguito dato che s.getNext() vale inizialmente null.

Esercizio 2

Scrivere un metodo di programma che prende come argomento un albero e restituisce il numero dei suoi nodi che hanno un solo figlio. Per esempio, il seguente albero ha due nodi in queste condizioni (il 4 e il -48), per cui va restituito 2.

L'albero che segue non ha nodi con un solo figlio, per cui va restituito 0.

Soluzione

Come quasi tutti i problemi sugli alberi, la soluzione è ricorsiva. In questo caso, il numero di nodi che soddisfano la condizione si determina in questo modo: si calcolano quelli dei due sottoalberi, e si somma 1 se la radice ha un solo figlio.

  static int contaUnici(Albero a) {
    if(a==null)
      return 0;

    int x=contaUnici(a.getSinistro());
    int y=contaUnici(a.getDestro());

    if( (a.getSinistro()==null) && (a.getDestro()!=null) )
      return x+y+1;

    if( (a.getSinistro()!=null) && (a.getDestro()==null) )
      return x+y+1;

    return x+y;
  }