Scheda di esercizi di Strutture dati con soluzioni

L'altezza di un albero è comunemente definita come:

1. AIl numero di figli della radice
2. BIl numero di archi del cammino più lungo dalla radice a una foglia
3. CIl numero totale di nodi dell'albero, contando la radice e ogni foglia
4. DIl numero di foglie dell'albero

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi sottoalbero destro, poi nodo
2. BSottoalbero sinistro, poi nodo, poi sottoalbero destro
3. CSottoalbero destro, poi nodo, poi sottoalbero sinistro
4. DNodo, poi sottoalbero sinistro, poi sottoalbero destro

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

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

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

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

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L), indipendentemente da quante parole sono memorizzate
2. BO(n), dove n è il numero di parole
3. CO(log n), dove n è il numero di parole
4. DO(L × n)

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. AUno stack
2. BUn heap
3. CSolo una tabella hash
4. DUna coda

Perché in un filtro di Bloom standard non si possono semplicemente eliminare gli elementi azzerandone i bit?

1. AI filtri di Bloom memorizzano gli elementi completi, che una volta sottoposti a hash non si possono più ritrovare
2. BQuei bit possono appartenere anche ad altri elementi, il che causerebbe falsi negativi
3. CI bit di un filtro di Bloom non si possono modificare dopo la creazione
4. DL'eliminazione porterebbe il tasso di falsi positivi al 100%

Quale coppia di visite determina sempre un unico albero binario con chiavi distinte?

1. APreordine e postordine
2. BPreordine e ordine simmetrico (inorder)
3. CIl solo preordine
4. DLa sola visita per livelli