Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

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

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

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

1. APop
2. BPeek
3. CPush
4. DEnqueue

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine per livelli
2. BOrdine crescente
3. COrdine di inserimento
4. DOrdine sempre decrescente

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUna lista concatenata non ordinata
2. BUna pila
3. CUn albero binario di ricerca bilanciato
4. DUna tabella hash

Come si trova la chiave minima in un albero binario di ricerca?

1. ASi guarda solo la radice
2. BSi seguono i figli destri dalla radice finché non c'è più un figlio destro
3. CSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
4. DSi visitano tutte le foglie e le si confronta

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

1. AL'altezza è esattamente log₂ n
2. BL'altezza è al massimo 2 log₂(n + 1)
3. CL'altezza è al massimo n / 2
4. DL'altezza è al massimo log₂ n + 1

Un albero di Fenwick (binary indexed tree) su un array di n numeri supporta quali operazioni in O(log n)?

1. ARicerca della mediana in O(1)
2. BInterrogazioni di somme prefisse e aggiornamenti di singoli elementi
3. CInserimento di elementi in qualsiasi posizione
4. DOrdinamento dell'array e ricerca binaria