Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanto vale log₂ 1024?

1. A512
2. B32
3. C12
4. D10

Quali sono i tre passi di un algoritmo divide et impera?

1. AOrdina, cerca, restituisci
2. BLeggi, calcola, scrivi
3. CIndovina, verifica, ripeti
4. DDividi, risolvi (impera), combina

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

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

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

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

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

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

1. ASempre una copertura dei vertici minima
2. BDi qualità ignota rispetto all'ottimo
3. CAl massimo il doppio della dimensione di una copertura dei vertici minima
4. DAl massimo log n volte il minimo

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. ASolo quel problema passerebbe in P
2. BOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
3. CTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
4. DIl problema della fermata diventerebbe decidibile