Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanto vale log₂ 1024?

1. A12
2. B32
3. C512
4. D10

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Che cosa significa che un'operazione ha tempo O(1)?

1. AElabora esattamente un elemento per ogni secondo di tempo di esecuzione
2. BIl suo tempo di esecuzione non cresce con la dimensione dell'input
3. CPuò essere eseguita una sola volta
4. DRichiede sempre esattamente un secondo

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Qual è la complessità temporale del quicksort nel caso peggiore?

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

Un problema è NP-completo se:

1. AÈ impossibile da risolvere
2. BÈ al di fuori di NP ma più difficile di tutti i problemi NP, come il problema della fermata
3. CAppartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale
4. DÈ risolvibile in tempo polinomiale

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AControlla se qualche arco ha peso negativo
2. BDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
3. CConta i cicli con una visita in profondità
4. DEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze