Scheda di esercizi di Strutture dati con soluzioni

Quanti archi ha un albero con n nodi?

1. An + 1
2. B2n
3. Cn − 1
4. Dn

L'altezza di un albero è comunemente definita come:

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

Quale operazione è lenta in un array ma veloce in testa a una lista concatenata?

1. AOttenere la lunghezza di un array di dimensione fissa
2. BAccedere al 5° elemento
3. CLeggere l'ultimo elemento tramite indice
4. DInserire all'inizio

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

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

Come si trova la chiave minima in un albero binario di ricerca?

1. ASi visitano tutte le foglie e le si confronta
2. BSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
3. CSi seguono i figli destri dalla radice finché non c'è più un figlio destro
4. DSi guarda solo la radice

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

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

Perché un server potrebbe scegliere a caso la propria funzione hash da una famiglia universale?

1. APer rendere molto improbabile che un attaccante scelga molte chiavi che collidono tutte
2. BPer garantire che due chiavi non collidano mai, qualunque chiave invii un attaccante
3. CPer rendere ordinata la tabella hash
4. DPer eliminare la necessità di ridimensionare la tabella

In una tabella hash con indirizzamento aperto, perché la cancellazione avviene spesso con un marcatore «lapide» (tombstone)?

1. ALe chiavi cancellate devono essere conservate per sempre per motivi di sicurezza, quindi le posizioni non si possono mai riutilizzare
2. BLe lapidi velocizzano l'hashing
3. CSvuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi
4. DRende la tabella ordinata