Esercizio 1. (6 punti) Spiegare brevemente (massimo 10 righe) perché è difficile eseguire le operazioni di cancellazione nelle tabelle hash a indirizzamento aperto.

Esercizio 2. (9 punti) Data la sequenza di chiavi intere 20, 10, 30, 40, 25, 50, 45, 28, costruire un albero AVL per inserzioni successive, disegnando l'albero dopo l'inserzione di ogni chiave e indicando il nodo critico prima di ogni rotazione.

Esercizio 3. (15 punti) Dato un grafo orientato $G\; =\; (V,\; E)$ con $n$ vertici e $m$ archi rappresentato con liste di adiacenza, si deve stabilire per tre vertici dati $x,\; y,\; z\; in\; V$ se $y$ si trova su un percorso da $x$ a $z$.

1. Descrivere brevemente la struttura di un algoritmo efficiente per risolvere tale problema.
2. Realizzare tale algoritmo sotto forma di funzione booleana in Pascal o pseudocodice, con parametri di ingresso $x,\; y,\; z$.
3. Valutare e motivare la complessità asintotica della soluzione proposta.

Soluzione dell'esercizio 1. Si veda il libro di testo. La difficoltà nel gestire la ricompattazione della tabella suggerisce di marcare logicamente come estratto ciascun elemento cancellato.

Soluzione dell'esercizio 2. Legenda del nodo: (h = altezza, f = fattore di bilanciamento, k = chiave). La struttura dell'albero è ruotata di 90 gradi in senso antiorario:

• Inserimento di 20

    (h=0, f=0, k=20)
  

• Inserimento di 10

    (h=1, f=1, k=20)
                   \ (h=0, f=0, k=10)
  

• Inserimento di 30

                   / (h=0, f=0, k=30)
    (h=1, f=0, k=20)
                   \ (h=0, f=0, k=10)
  

• Inserimento di 40

                                    / (h=0, f=0, k=40)
                   / (h=1, f=-1, k=30)
    (h=2, f=-1, k=20)
                   \ (h=0, f=0, k=10)
  

• Inserimento di 25

                                    / (h=0, f=0, k=40)
                   / (h=1, f=0, k=30)
                                    \ (h=0, f=0, k=25)
    (h=2, f=-1, k=20)
                   \ (h=0, f=0, k=10)
  

• Inserimento di 50

                                                     / (h=0, f=0, k=50)
                                    / (h=1, f=-1, k=40)
                   / (h=2, f=-1, k=30)
                                    \ (h=0, f=0, k=25)
    (h=3, f=-2, k=20)
                   \ (h=0, f=0, k=10)
  
  Nodo critico : 20		Rotazione: DD
  
                                    / (h=0, f=0, k=50)
                   / (h=1, f=-1, k=40)
    (h=2, f=0, k=30)
                                    / (h=0, f=0, k=25)
                   \ (h=1, f=0, k=20)
                                    \ (h=0, f=0, k=10)
  

• Inserimento di 45

                                    / (h=1, f=1, k=50)
                                                     \ (h=0, f=0, k=45)
                   / (h=2, f=-2, k=40)
    (h=3, f=-1, k=30)
                                    / (h=0, f=0, k=25)
                   \ (h=1, f=0, k=20)
                                    \ (h=0, f=0, k=10)
  
  Nodo critico : 40		Rotazione: DS
  
                                    / (h=0, f=0, k=50)
                   / (h=1, f=0, k=45)
                                    \ (h=0, f=0, k=40)
    (h=2, f=0, k=30)
                                    / (h=0, f=0, k=25)
                   \ (h=1, f=0, k=20)
                                    \ (h=0, f=0, k=10)
  

• Inserimento di 28

                                    / (h=0, f=0, k=50)
                   / (h=1, f=0, k=45)
                                    \ (h=0, f=0, k=40)
    (h=3, f=1, k=30)
                                                     / (h=0, f=0, k=28)
                                    / (h=1, f=-1, k=25)
                   \ (h=2, f=-1, k=20)
                                    \ (h=0, f=0, k=10)
  

Soluzione dell'esercizio 3.

1. Usiamo la seguente proprietà: y è sul percorso da x a z se e solo se y è raggiungibile da x e z è raggiungibile da y. Effettuiamo perciò una visita a partire da x e, non appena raggiungiamo y, ripartiamo con una nuova visita da y cercando di raggiungere z (riazzerando le informazioni ausiliarie della prima visita).

2. Soluzione in pseudocodice PERCORSO(x,y,z) che usa una procedura DFS-VISIT-M(u,d) di visita in profondità modificata. DFS-VISIT-M si ferma non appena raggiunge il vertice d a partire dal vertice u, colorando il vertice d di nero.

   PERCORSO( x, y, z ) 
   1. foreach u in V do colore[u] := bianco
   2. DFS-VISIT-M( x, y )
   3. if colore[y] = bianco then return false   // esce con fallimento :-(
   4. foreach u in V do colore[u] := bianco     // ri-inizializza i colori 
   5. DFS-VISIT-M( y, z )
   6. if colore[z] = bianco then return false   // esce con fallimento :-(
   7. return true     // supera tutti i controlli ed esce con successo :-)
   
   DFS-VISIT-M( u, d )
   1. colore[u] := grigio;
   2. foreach v in ListaAdiacenza(u) do
   4.    if colore[v] = bianco then 
   5.       if (v = d) 
   6.          then colore[v] = nero
   7.               return ":-)"        // raggiunge d e termina la visita
   8.          else DFS-VISIT-M( v, d ) // altrimenti  continua  la visita
   9. colore[u] := nero
   

3. Al caso pessimo ogni arco viene attraversato due volte e quindi la complessità è lineare, cioè O(n + m).