Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cosa sono i nodi fratelli?

1. ANodi che hanno lo stesso genitore
2. BNodi privi di figli
3. CNodi alla stessa profondità in sottoalberi diversi
4. DUn nodo e il suo genitore

Che cos'è un grafo pesato?

1. AUn grafo memorizzato su disco
2. BUn grafo con più archi che vertici
3. CUn grafo in cui alcuni vertici sono più pesanti di altri perché hanno più archi
4. DUn grafo in cui ogni arco ha un valore numerico, come un costo o una distanza

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AIl numero totale di archi del grafo
2. BUna riga di V valori booleani
3. CIl cammino minimo verso ogni altro vertice
4. DUna lista dei suoi vertici adiacenti

Quanta memoria utilizza una matrice di adiacenza per un grafo con V vertici?

1. AO(V + E)
2. BO(log V)
3. CO(E)
4. DO(V²)

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

1. AUno stack
2. BSolo una tabella hash
3. CUn heap
4. DUna coda

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUna tabella hash
2. BUna pila
3. CUn albero binario di ricerca bilanciato
4. DUna lista concatenata non ordinata

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

1. AO(n²)
2. BO(α(n)), l'inversa della funzione di Ackermann, praticamente costante
3. CO(n)
4. DEsattamente O(log n)

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

1. AL'altezza è al massimo 2 log₂(n + 1)
2. BL'altezza è esattamente log₂ n
3. CL'altezza è al massimo n / 2
4. DL'altezza è al massimo log₂ n + 1