Scheda di esercizi di Strutture dati con soluzioni

Quale struttura dati funziona secondo il principio «primo a entrare, primo a uscire» (FIFO)?

1. AHeap
2. BAlbero binario
3. CCoda (queue)
4. DPila (stack)

In una tabella hash, che cos'è una collisione?

1. ADue chiavi diverse vengono associate allo stesso indice
2. BUna chiave non può essere sottoposta a hash
3. CLa tabella esaurisce la memoria
4. DDue chiavi uguali vengono memorizzate due volte

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

1. ADequeue
2. BEnqueue
3. CPush
4. DInsert

A che cosa serve un nodo sentinella (fittizio) in una lista concatenata?

1. AA semplificare il codice eliminando i casi particolari in testa o in coda
2. BA memorizzare il numero di elementi
3. CA rendere la lista ordinata
4. DA impedire che la lista cresca oltre un numero massimo fisso di nodi

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

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

Quale condizione di bilanciamento mantiene un albero AVL in ogni nodo?

1. ATutte le foglie sono esattamente alla stessa profondità
2. BI due sottoalberi di ogni nodo contengono esattamente lo stesso numero di nodi
3. CLe altezze dei sottoalberi sinistro e destro differiscono al massimo di 1
4. DOgni nodo è colorato di rosso o di nero

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

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

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

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