Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale nel caso peggiore dell'insertion sort?

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

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 tempo per un input di lunghezza media
4. DIl valore intermedio tra i tempi di esecuzione nel caso migliore e nel caso peggiore

Che cos'è un algoritmo?

1. AQualsiasi programma con un'interfaccia grafica
2. BUn linguaggio di programmazione progettato per scrivere formule matematiche
3. CUna sequenza finita di passi ben definiti che risolve un problema
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(2ⁿ)
2. BO(log n)
3. CO(n²)
4. DO(n)

Quale algoritmo di ordinamento è stabile?

1. AHeap sort
2. BQuicksort (tipica versione in loco)
3. CSelection sort (versione tipica)
4. DMerge sort

Che cosa significa che un problema ha una sottostruttura ottima?

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

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)

Quale definizione della classe P è corretta?

1. AProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
2. BProblemi che si possono risolvere in parallelo
3. CProblemi che richiedono tempo esponenziale su ogni computer
4. DProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale