Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che usa sempre la ricorsione
2. BUn algoritmo che gira su molti processori
3. CUn algoritmo che tira a indovinare una risposta a caso
4. DUn algoritmo che prova tutte le possibili soluzioni candidate

Accedere a un elemento di un array tramite indice richiede:

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

Che cos'è un algoritmo?

1. AUna sequenza finita di passi ben definiti che risolve un problema
2. BUn linguaggio di programmazione progettato per scrivere formule matematiche
3. CQualsiasi programma con un'interfaccia grafica
4. DUna struttura dati che memorizza numeri

Una funzione esegue un ciclo di n iterazioni e poi, separatamente, un altro ciclo di n iterazioni. Qual è la sua complessità temporale?

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ACostante
2. BLineare
3. CEsponenziale
4. DLogaritmica

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Un problema è NP-completo se:

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

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

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