Scheda di esercizi di Strutture dati con soluzioni

Che cos'è una deque (coda a doppia estremità)?

1. AUna coda che permette rimozioni solo in fondo
2. BUna coda ordinata per priorità
3. CDue code separate che condividono un array
4. DUna struttura che permette inserimenti e rimozioni a entrambe le estremità

Che cosa fa l'operazione peek (o top) su una pila?

1. ARestituisce l'elemento in fondo alla pila
2. BRestituisce l'elemento in cima senza rimuoverlo
3. CRimuove l'elemento in cima e lo restituisce
4. DRimuove tutti gli elementi dalla pila

Che cosa fa una funzione hash in una tabella hash?

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

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel suo genitore, sempre
2. BNel nodo più a sinistra del suo sottoalbero destro
3. CNel nodo più a destra del suo sottoalbero sinistro
4. DNel suo figlio destro, sempre

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(n²)
3. CO(1)
4. DO(log n)

Come si inserisce un nuovo elemento in un heap binario?

1. ALo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
2. BLo si pone nella radice e lo si fa scendere
3. CLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi
4. DSi ricostruisce da zero l'intero heap

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

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

Quale problema della scansione lineare viene ridotto principalmente dal doppio hashing?

1. ALa necessità di una funzione hash
2. BIl costo O(n) della lettura del valore di una chiave
3. CLa necessità di memorizzare le chiavi nella tabella
4. DL'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate