Scheda di esercizi di Strutture dati con soluzioni

Che cosa definisce un albero binario?

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

Quale struttura dati è più adatta per la funzione «annulla» (undo) di un editor di testo?

1. ACoda (queue)
2. BPila (stack)
3. CInsieme hash (hash set)
4. DGrafo

Come si chiama l'operazione di una pila (stack) che aggiunge un elemento in cima?

1. APop
2. BPush
3. CEnqueue
4. DPeek

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. Ah²
2. B2^h
3. C2h + 1
4. D2^h+1 − 1

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. ASolo una tabella hash
2. BUna coda
3. CUn heap
4. DUno stack

Un nodo AVL è sbilanciato perché il sottoalbero destro del suo figlio sinistro è diventato troppo alto (caso sinistra-destra). Quale correzione si applica?

1. AUna rotazione a destra sul figlio sinistro, poi una rotazione a sinistra sul nodo
2. BUna singola rotazione a sinistra sul nodo
3. CUna rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo
4. DUna singola rotazione a destra sul nodo

Un segment tree (albero dei segmenti) è tipicamente usato per:

1. AOrdinare stringhe alfabeticamente memorizzando ogni prefisso in un nodo separato dell'albero
2. BMemorizzare gli archi di un grafo
3. CRispondere a interrogazioni su intervalli (come somme su intervalli) e aggiornamenti in O(log n)
4. DImplementare uno stack