Scheda di esercizi di Strutture dati con soluzioni

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

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

La profondità di un nodo in un albero è:

1. AIl numero di archi dalla radice a quel nodo
2. BIl numero di archi da quel nodo alla foglia più profonda
3. CIl numero di figli di quel nodo
4. DIl numero di nodi del suo sottoalbero

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AMaggiori del valore del nodo
2. BUguali al valore del nodo
3. CMinori del valore del nodo
4. DIn ordine casuale

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

1. Ai/2 e i/2 + 1
2. B2i + 1 e 2i + 2
3. Ci + 1 e i + 2
4. D2i e 2i + 1

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

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

Quale tipo di dato astratto usa l'algoritmo di Dijkstra per scegliere il prossimo vertice da elaborare?

1. AUna coda FIFO
2. BUna coda con priorità di minimo
3. CUna pila
4. DUn insieme senza ordinamento

Quale proprietà mantiene ogni B-albero perfettamente bilanciato?

1. ALe chiavi sono memorizzate solo nella radice
2. BOgni nodo ha esattamente due figli
3. COgni nodo memorizza una sola chiave
4. DTutte le foglie sono alla stessa profondità

Quale proprietà deve soddisfare un albero rosso-nero?

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