Scheda di esercizi di Algoritmi e complessità con soluzioni

Come si chiama una crescita O(2ⁿ)?

1. ALogaritmica
2. BEsponenziale
3. CPolinomiale
4. DLineare

Quale classe di complessità cresce più rapidamente per n grande?

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

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. AQuicksort
2. BMerge sort
3. CBubble sort
4. DHeap sort

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

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

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
2. BL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
3. CL'insertion sort è O(n log n) nel caso peggiore
4. DL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi

Quale algoritmo trova un albero ricoprente minimo aggiungendo ripetutamente l'arco più economico che non forma un ciclo?

1. AFloyd-Warshall
2. BAlgoritmo di Dijkstra
3. CAlgoritmo di Prim a partire da un nodo
4. DAlgoritmo di Kruskal

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. ALe funzioni hash sono lente
2. BLe chiavi devono prima essere ordinate
3. CMolte chiavi possono collidere nello stesso bucket
4. DGli array hanno accesso O(n)