Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

1. ACoppie chiave–valore individuate da una funzione hash
2. BUna stringa di lunghezza fissa
3. CUn albero con chiavi ordinate
4. DSolo una lista ordinata

In un grafo, che cos'è un ciclo?

1. AUn cammino che inizia e finisce nello stesso vertice
2. BUn arco di peso zero
3. CUn cammino che visita ogni vertice
4. DUn vertice senza archi

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

1. APush
2. BEnqueue
3. CInsert
4. DDequeue

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

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

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in preordine?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. AScansione lineare (linear probing)
2. BScansione quadratica (quadratic probing)
3. CConcatenamento separato (separate chaining)
4. DDoppio hashing (double hashing)

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

1. AO(n)
2. BEsattamente O(log n)
3. CO(n²)
4. DO(α(n)), l'inversa della funzione di Ackermann, praticamente costante

In un buffer circolare, front == rear può significare sia vuoto sia pieno. Qual è un modo comune per distinguere i due casi?

1. AMemorizzare front e rear nella stessa variabile
2. BSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto
3. CRendere la dimensione del buffer una potenza di due
4. DMantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata