Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AMerge sort
2. BBubble sort
3. CInsertion sort
4. DQuicksort

Come si chiama una crescita O(2ⁿ)?

1. ALineare
2. BLogaritmica
3. CPolinomiale
4. DEsponenziale

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

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

Qual è la complessità temporale del quicksort nel caso peggiore?

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

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

1. AO(n log n)
2. BO(d(n + k))
3. CO(dn log k)
4. DO(n²)

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

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

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

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

Come si classifica il problema del commesso viaggiatore?

1. ALa versione decisionale è in P ma quella di ottimizzazione è NP-completa
2. BLa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile
3. CÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
4. DÈ indecidibile