Indice
Esercitazione alberi
Esercizio 1: conta occorrenze
Definire il tipo albero_s_t
di un albero binario in cui le etichette sono stringhe di al piu' 20 caratteri. Scrivere una funzione
int conta_occorrenze ( albero_s_t * root, char * s );
che conta le occorrenze della stringa s
nell'albero di radice root
e restituisce tale numero.
Esercizio 2: somma
Definire il tipo albero_d_t
di un albero binario in cui le etichette sono valori di tipo double
. Scrivere una funzione
double somma_le_foglie ( albero_d_t * root);
che restituisce la somma dei valori delle etichette delle sole foglie dell'albero.
Esercizio 3: Alberi binari di ricerca
Un albero binario di ricerca e' un albero in cui in ogni nodo $n$ e' verificata la relazione
$$ E(n_{sx}) \leq E(n) \leq E(n_{dx}) $$
dove $n_{sx}$ e' un qualsiasi nodo dell'albero di sinistra e $n_{dx}$ e' un qualsiasi nodo dell'albero di destra.
Utilizzando il tipo albero_d_t
realizzate le seguenti funzioni:
/* inserisce l'etichetta x nell'albero mantenedolo ordinato, restituisce il puntatore al nuovo albero */ albero_d_t* inserisci_ord ( albero_d_t * root, double x ); /* ricerca l'etichetta x nell'albero analizzando un numero di nodi pari all'altezza dell'albero restituisce 1 se la trova e 0 se non la trova */ int ricerca ( albero_d_t * root, double x ); /* cancella l'etichetta x nell'albero mantenedolo ordinato e deallocando il nodo (difficile!) oppure utilizzando un campo in più nella struttura che indica se il nodo è stato cancellato e restituisce il puntatore al nuovo albero */ albero_d_t* cancella_ord ( albero_d_t * root, double x );
Esercizio 4: Tabelle hash, creazione, inserimento, ricerca
Scrivere un programma che legga da tastiera una sequenza di $n$ interi distinti e li inserisca in una tabella hash di dimensione $2n$ posizioni utilizzando liste monodirezionali per risolvere eventuali conflitti. Utilizzare la funzione hash \[ h(x) = ((ax + b)\%p)\%2 n \] dove $p$ e' il numero primo $999149$ e $a$ e $b$ sono interi positivi minori di 10.000 scelti casualmente. Una volta inseriti tutti gli interi, il programma deve stampare la lunghezza massima delle liste e il numero totale di conflitti.
Definire una funzione C che inserisce un elemento nella tabella e una funzione che effettua la ricerca restituendo 1 se l'intero cercato è presente e 0 altrimenti.
Prima di scrivere il programma chiedersi perche' la tabella ha dimensione $2n$ e non $n$.
Esercizio 5: Visualizzare il movimento con OpenGL
Approfondimenti: (avanzato) Eulero e il problema dei ponti di Koeningsberg
Questo e' il link al problema di Eulero che ha dato origine alla teoria dei grafi. Come si potrebbe rappresentare usando una struttura ricorsiva ?