Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Accedere a un elemento di un array tramite indice richiede:

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

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(n²)
3. CO(log n)
4. DO(n)

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

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

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

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

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

1. AW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
2. BPerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
3. CPerché n è sempre piccolo
4. DPerché funziona solo per W = 0

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 Kruskal
4. DAlgoritmo di Prim a partire da un nodo