Scheda di esercizi di Strutture dati con soluzioni

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate
2. BIl numero di elementi memorizzati diviso per il numero di bucket
3. CIl numero di collisioni avvenute finora
4. DIl tempo necessario per caricare la tabella dal disco

La profondità di un nodo in un albero è:

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

Che cosa fa una funzione hash in una tabella hash?

1. AConta quante chiavi sono memorizzate
2. BCifra i valori della tabella
3. CAssocia una chiave a un indice della tabella
4. DOrdina le chiavi della tabella

Quanta memoria usa una lista di adiacenza per un grafo con V vertici ed E archi?

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

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUna visita di un grafo
2. BUna coda di dimensione fissa
3. CUn albero binario di ricerca
4. DUna funzione hash

Che cosa è vero per la matrice di adiacenza di un grafo non orientato?

1. AOgni riga contiene esattamente un 1
2. BLa sua diagonale principale contiene sempre degli uno
3. CÈ simmetrica rispetto alla diagonale principale
4. DÈ sempre triangolare superiore

Senza unione per rango né compressione dei cammini, qual è il costo nel caso peggiore di una singola find in una struttura union-find con n elementi?

1. AO(n)
2. BO(1)
3. CO(log n)
4. DO(α(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. CO(n)
4. DEsattamente O(log n)