Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

1. ACoppie chiave–valore individuate da una funzione hash
2. BUna stringa di lunghezza fissa
3. CSolo una lista ordinata
4. DUn albero con chiavi ordinate

Che cosa fa una funzione hash in una tabella hash?

1. AOrdina le chiavi della tabella
2. BCifra i valori della tabella
3. CConta quante chiavi sono memorizzate
4. DAssocia una chiave a un indice della tabella

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

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. AMatrice di adiacenza
2. BLista di adiacenza
3. CUn heap binario di archi
4. DUn unico array ordinato di vertici

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

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

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

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

Che cosa fa uno splay tree dopo ogni accesso?

1. ARicolora i nodi lungo il cammino di ricerca
2. BRicostruisce l'intero albero in forma bilanciata
3. CPorta con rotazioni il nodo acceduto fino alla radice
4. DSposta il nodo acceduto in una foglia

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