Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa descrive il tempo di esecuzione nel caso medio?

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

Come si chiama una crescita O(2ⁿ)?

1. ALineare
2. BPolinomiale
3. CEsponenziale
4. DLogaritmica

Quale di questi tempi di esecuzione è polinomiale?

1. AO(nⁿ)
2. BO(2ⁿ)
3. CO(n!)
4. DO(n³)

Che cosa significa che un problema ha una sottostruttura ottima?

1. AOgni sottoproblema ha la stessa dimensione
2. BIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
3. CUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
4. DIl problema si può risolvere in tempo costante

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

Quale algoritmo di ordinamento è stabile?

1. AMerge sort
2. BHeap sort
3. CSelection sort (versione tipica)
4. DQuicksort (tipica versione in loco)

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + n log n?

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

Come si confrontano n! e 2ⁿ per n grande?

1. An! è O(n²)
2. Bn! cresce più velocemente di 2ⁿ
3. C2ⁿ cresce più velocemente di n!
4. DCrescono allo stesso ritmo