Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo?

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

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 prova tutte le possibili soluzioni candidate
4. DUn algoritmo che tira a indovinare una risposta a caso

Che cosa descrive il tempo di esecuzione nel caso medio?

1. AIl tempo atteso rispetto a una data distribuzione degli input di dimensione n
2. BIl valore intermedio tra i tempi di esecuzione nel caso migliore e nel caso peggiore
3. CIl tempo sul computer più diffuso
4. DIl tempo per un input di lunghezza media

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(n)?

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

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 20
2. BCirca 1,000
3. CCirca 100
4. DCirca 500,000

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché per n grande n³ è minore di n²
2. BSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
3. CSì, ma solo se n è minore di 100
4. DNo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione

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

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

Quali sono i costi in tempo e spazio del calcolo dell'n-esimo numero di Fibonacci con un ciclo che conserva solo gli ultimi due valori?

1. ATempo O(2ⁿ) e spazio O(1)
2. BTempo O(log n) e spazio O(n)
3. CTempo O(n) e spazio O(1)
4. DTempo O(n) e spazio O(n)