Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale del merge sort nel caso peggiore?

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

Un problema si dice di solito trattabile se:

1. ANon ha soluzione
2. BPuò essere risolto in tempo costante
3. CPuò essere risolto solo provando ogni possibilità
4. DPuò essere risolto in tempo polinomiale

Come si chiama una crescita O(2ⁿ)?

1. ALogaritmica
2. BPolinomiale
3. CLineare
4. DEsponenziale

Che cosa significa che un problema ha una sottostruttura ottima?

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

Quale algoritmo di ordinamento è stabile?

1. AMerge sort
2. BSelection sort (versione tipica)
3. CQuicksort (tipica versione in loco)
4. DHeap sort

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

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

Quale definizione della classe NP è corretta?

1. AProblemi che non sono polinomiali
2. BProblemi che nessun algoritmo può risolvere
3. CProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato
4. DProblemi che non si possono risolvere in tempo polinomiale

Qual è il tempo di esecuzione dell'algoritmo di Dijkstra con uno heap binario su un grafo con V vertici ed E archi?

1. AO(V + E)
2. BO((V + E) log V)
3. CO(V × E)
4. DO(V³)