Scheda di esercizi di Strutture dati con soluzioni

Che cosa definisce un albero binario?

1. AL'albero ha esattamente due livelli
2. BOgni nodo memorizza un numero binario
3. COgni nodo ha esattamente due figli
4. DOgni nodo ha al massimo due figli

Che cosa fa una funzione hash in una tabella hash?

1. ACifra i valori della tabella
2. BOrdina le chiavi della tabella
3. CConta quante chiavi sono memorizzate
4. DAssocia una chiave a un indice della tabella

Una tabella hash memorizza i dati come:

1. AUn albero con chiavi ordinate
2. BSolo una lista ordinata
3. CCoppie chiave–valore individuate da una funzione hash
4. DUna stringa di lunghezza fissa

Quanta memoria usa una lista di adiacenza per un grafo con V vertici ed E archi?

1. AO(V²)
2. BO(E²)
3. CO(V × E)
4. DO(V + E)

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(log n), per via della ricerca binaria
2. BO(n²), perché ogni elemento si sposta n volte
3. CO(n), perché gli elementi successivi devono essere spostati
4. DO(1), perché l'indice è noto

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUn albero binario di ricerca
2. BUna funzione hash
3. CUna coda di dimensione fissa
4. DUna visita di un grafo

Quale proprietà mantiene ogni B-albero perfettamente bilanciato?

1. AOgni nodo ha esattamente due figli
2. BOgni nodo memorizza una sola chiave
3. CLe chiavi sono memorizzate solo nella radice
4. DTutte le foglie sono alla stessa profondità

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)