Algoritmi e Strutture Dati I
Quarto Appello -- 28 Giugno 1999

PARTE I

Esercizio 1. (8 punti) Un albero binario completo è caratterizzato dall'avere le foglie tutte allo stesso livello e i nodi interni con esattamente due figli. Dimostrare per induzione che un albero binario completo di altezza k ha 2k foglie e 2k - 1 nodi interni.

Esercizio 2. (7 punti) Dato lo heap:

 40   20   30   15   12   18   10   7   9   1 

riportare la configurazione dello heap dopo ogni scambio di chiavi, per realizzare le tre operazioni:
  1. inserire 32
  2. inserire 35
  3. eliminare 40.

PARTE II

Esercizio 3. (7 punti) In riferimento alle funzioni hash con indirizzamento aperto a scansione lineare, spiegare brevemente:

  1. cosa sono gli agglomerati (o cluster);
  2. perché gli agglomerati di lunghezza maggiore tendono a crescere più velocemente degli altri quando vengono effettuate delle inserzioni successive.

Esercizio 4. (8 punti) Dato un grafo non orientato G = (V, E), si deve eliminare un vertice w con tutti gli archi ad esso incidenti.

  1. Assumendo che il grafo sia rappresentato con liste di adiacenza, realizzare tale operazione sotto forma di procedura in Pascal o pseudocodice, con parametri di ingresso w e G. Valutare e motivare la complessità asintotica della soluzione proposta.
  2. Descrivere a parole l'operazione quando il grafo è invece rappresentato con matrici di adiacenza, e determinarne la complessità.

Roberto Grossi, Luglio 1999