Laboratorio di Algoritmi e Strutture Dati ESAME FINALE 12/12/2001 (Compito C – prima parte) PRIMA PARTE C.A.1

(1)

Laboratorio di Algoritmi e Strutture Dati ESAME FINALE 12/12/2001

(Compito C – prima parte)

PRIMA PARTE

C.A.1

Si descriva il funzionamento dell’algoritmo heap_sort applicando l’algoritmo alla sequenza

:

<1, 8, 2, 5, 11, 13, 4>

C.A.2

Si descriva il funzionamento dell’algoritmo insertion_sort applicando l’algoritmo alla sequenza:

<1, 8, 2, 5, 11, 13, 4>

C.A.3

La rappresentazione “figlio-sinistro, fratello-destro” di un albero n-ario prevede che ogni nodo sia collagato come in figura:

Si descriva una procedura di vista dell’albero in ampiezza.

C.A.4

Si discuta come va modificata la funzione BuildHeap per la costruzione di un maxheap nel caso in cui la coda di priorità sia implementata con un array e sia memorizzata nelle posizioni comprese tra i due indici head e tail, come nella figura seguente

:

C.B.1

Sia dato un albero n-ario per la rappresentazione dell’albero genealogico di una data persona, definito dalla seguente struttura:

struct nodo { char* nome;

struct nodo ** sons;

int numsons;

};

struct nodo *ancestor;

Si realizzi un programma che determini il tasso di proliferazione media della stirpe (cioè, il numero medio dei figli per ogni genitore), e stampi i nominativi delle persone che presentano un tasso superiore alla media

.

C.C.1

Si discutano i vantaggi dell’uso di funzioni hash universali, e si illustri una possibile implementazione per realizzare una classe di tali funzioni