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. BCoda (queue)
3. CPila (stack)
4. DAlbero binario

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

1. ADati, un puntatore al nodo successivo e un puntatore al nodo precedente
2. BDati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo
3. CDue copie dei dati e un solo puntatore
4. DDati e soltanto un puntatore al nodo successivo

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. CDue chiavi uguali vengono memorizzate due volte
4. DLa tabella esaurisce la memoria

In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

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

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

1. A1
2. B2
3. C0,5
4. DNon c'è un massimo

L'eliminazione di un nodo con due figli da un albero binario di ricerca avviene di solito:

1. ARimuovendo l'intero sottoalbero
2. BRicostruendo da zero il sottoalbero sottostante e reinserendo tutte le chiavi che conteneva
3. CSostituendolo con il suo successore in ordine (o predecessore) ed eliminando quel nodo
4. DScambiandolo con la radice

Quale proprietà deve soddisfare un albero rosso-nero?

1. AOgni nodo deve essere rosso
2. BLa radice deve essere rossa
3. COgni nodo rosso deve avere figli rossi, quindi i nodi rossi formano sempre catene ininterrotte fino alle foglie
4. DOgni cammino da un nodo alle sue foglie discendenti contiene lo stesso numero di nodi neri