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)

Quale di queste cresce più lentamente quando n diventa grande?

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

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

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

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

1. AUn albero ricoprente minimo in O(E log V)
2. BUn ordinamento topologico in O(V²)
3. CI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
4. DI cammini minimi tra tutte le coppie di vertici in O(V³)

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

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

La programmazione dinamica è utile quando un problema presenta:

1. ASottoproblemi sovrapposti e sottostruttura ottima
2. BNessun sottoproblema, quindi si risolve in un solo passo
3. CUn unico ciclo
4. DSolo input casuali

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AConta i cicli con una visita in profondità
2. BEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
3. CDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
4. DControlla se qualche arco ha peso negativo

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. AAl massimo il doppio della dimensione di una copertura dei vertici minima
2. BAl massimo log n volte il minimo
3. CDi qualità ignota rispetto all'ottimo
4. DSempre una copertura dei vertici minima