Scheda di esercizi di Strutture dati con soluzioni

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e riferimenti a tutti gli altri nodi
2. BSolo dati
3. CDati e un indice
4. DDati e un riferimento al nodo successivo

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

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

In un grafo, che cos'è un ciclo?

1. AUn vertice senza archi
2. BUn cammino che visita ogni vertice
3. CUn cammino che inizia e finisce nello stesso vertice
4. DUn arco di peso zero

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

Gli alberi AVL e gli alberi rosso-neri garantiscono:

1. AChe nessun nodo abbia due figli
2. BUna ricerca in tempo costante in ogni caso
3. CChe le chiavi siano memorizzate in ordine di inserimento
4. DUn'altezza O(log n) tramite il ribilanciamento

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. An (diventa una lista concatenata)
2. B√n
3. C1
4. Dlog₂ n

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. CEsattamente O(log n)
4. DO(n²)

Per ogni elemento di un array vuoi il successivo elemento maggiore alla sua destra, in tempo totale O(n). Quale struttura aiuta?

1. AUna pila che conserva gli elementi in attesa della loro risposta
2. BUna coda che contiene ogni coppia di elementi
3. CUna tabella hash di tutti gli elementi
4. DUn albero binario di ricerca ricostruito per ogni elemento