Scheda di esercizi di Strutture dati con soluzioni

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BLa lunghezza del cammino più lungo che parte da esso
3. CIl numero di archi a esso collegati
4. DIl numero di vertici del grafo

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

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

In un albero, che cos'è una foglia?

1. AIl nodo con il valore più grande
2. BUn nodo senza genitore
3. CUn nodo con esattamente un figlio
4. DUn nodo senza figli

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. ANon c'è un massimo
2. B2
3. C1
4. D0,5

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

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

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel suo figlio destro, sempre
2. BNel suo genitore, sempre
3. CNel nodo più a sinistra del suo sottoalbero destro
4. DNel nodo più a destra del suo sottoalbero sinistro

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

1. ARicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi
2. BRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti
3. CNon usa memoria aggiuntiva
4. DMemorizza le chiavi senza ordine

Che cosa fa uno splay tree dopo ogni accesso?

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