Scheda di esercizi di Strutture dati con soluzioni

Quale operazione è lenta in un array ma veloce in testa a una lista concatenata?

1. AOttenere la lunghezza di un array di dimensione fissa
2. BLeggere l'ultimo elemento tramite indice
3. CAccedere al 5° elemento
4. DInserire all'inizio

Che cosa fa una funzione hash in una tabella hash?

1. ACifra i valori della tabella
2. BConta quante chiavi sono memorizzate
3. CAssocia una chiave a un indice della tabella
4. DOrdina le chiavi della tabella

Un grafo è composto da:

1. AVertici (nodi) collegati da archi
2. BRighe e colonne
3. CSolo una radice e delle foglie
4. DSolo chiavi e hash

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

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

Una coda è implementata con due pile: push su una pila «in» e pop da una pila «out», che viene riempita da «in» quando è vuota. Qual è il costo ammortizzato per operazione?

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

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

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

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

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

Quale affermazione sull'heapsort è corretta?

1. AOrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
2. BÈ stabile e richiede O(n) memoria aggiuntiva
3. CRichiede tempo O(n) su qualsiasi input
4. DRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra