Laboratorio di Algoritmi e Strutture Dati ESAME FINALE 12/12/2001
(compito A – prima parte)
PRIMA PARTE
A.A.1
Si descriva il funzionamento dell’algoritmo heap_sort applicando l’algoritmo alla sequenza:<7, 1, 4, 3, 8, 11, 2>
A.A.2
Si descriva il funzionamento dell’algoritmo insertion_sort applicando l’algoritmo alla sequenza:<7, 1, 4, 3, 8, 11, 2>
A.A.3
Date le seguenti dichiarazioni per la realizzazione di un albero binario, struct nodo {int info;
struct nodo *left;
struct nodo *right;
};
struct nodo *root;
si descriva in linguaggio C l’implementazione dell’operazione di cancellazione di un elemento dall’albero puntato da root (si consideri data l’operazione visita per la ricerca dell’elemento da cancellare). Si indichino inoltre quali parametri devono essere passati alla funzione visita e quali valori devono essere restituiti da essa.
A.A.4
Si consideri una coda implementata tramite una lista circolare come in figuraa partire dalla struttura elementare
struct elem { int info;
struct elem* next;
};
Si scrivano le funzioni insert(struct elem*) e delete(int key) per l’inserimento e la rimozione di un elemento.
A.B.1
Dato un albero n-ario definito con le seguenti dichiarazioni, struct nodo {int info;
struct nodo ** sons;
int numsons;
};
struct nodo *root;
si scriva un programma che elimini dall’albero tutte le ripetizioni, lasciando un solo nodo per ogni chiave ripetuta [si utilizzi la funzione delete dell’esercizio A.A.3 per la cancellazione di un nodo da un albero].
A.C.1
Si descriva la tecnica di realizzazione di un dizionario tramite tabelle ad accesso diretto.15 10 7 21
head tail
