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. CSolo una lista ordinata
4. DUn albero con chiavi ordinate

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

1. AEnqueue
2. BDequeue
3. CPush
4. DInsert

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANell'ultima posizione dell'array
2. BNella foglia più a sinistra
3. CNella radice
4. DIn una foglia qualsiasi, da cercare

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. A2
2. B1
3. CNon c'è un massimo
4. D0,5

Hai un riferimento a un nodo a metà di una lista. In quale lista puoi rimuoverlo in O(1)?

1. AUn array ordinato
2. BUn array dinamico
3. CUna lista concatenata semplice
4. DUna lista doppiamente concatenata

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

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

Quale struttura dati permette una cache LRU (least recently used) con get e put in O(1)?

1. AUn singolo array ordinato
2. BSolo un albero binario di ricerca
3. CUna hash map combinata con una lista doppiamente concatenata
4. DSolo uno stack

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

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