Scheda di esercizi di Algoritmi e complessità con soluzioni

Scheda di esercizi di Algoritmi e complessità gratuita e stampabile: 8 esercizi dal livello facile a quello d’esame, con le soluzioni. Stampala o salvala come PDF.

Nuova schedaEsercitati online con i suggerimenti

Per i docenti: gratuita da stampare, copiare e usare in classe. Ogni nuova scheda ha nuovi valori e le sue soluzioni. Un link a ExamProblems nella pagina del corso è molto apprezzato.

Nome: ____________________   Data: ____________

1.Facile

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

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

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

  1. AMerge sort
  2. BHeap sort
  3. CBubble sort
  4. DQuicksort
3.Facile

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

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

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

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

La visita in ampiezza (BFS) su un grafo non pesato trova:

  1. AL'albero ricoprente minimo
  2. BUn ordinamento topologico in tutti i grafi
  3. CI cammini minimi in numero di archi dal nodo di partenza
  4. DI cammini minimi in grafi che contengono archi con peso negativo
6.Media

Qual è la complessità temporale del calcolo dell'n-esimo numero di Fibonacci con una tabella bottom-up?

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

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3), circa n1,585
  3. CΘ(n²)
  4. DΘ(n3)
8.Difficile

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

  1. ANessuna delle due varianti
  2. BLo zaino 0/1, in cui gli oggetti si devono prendere sempre interi
  3. CEntrambe le varianti
  4. DLo zaino frazionario, in cui gli oggetti si possono dividere

Soluzioni

  1. 1. C · O(2ⁿ)
  2. 2. C · Bubble sort
  3. 3. B · O(log n)
  4. 4. A · O(n log n)
  5. 5. C · I cammini minimi in numero di archi dal nodo di partenza
  6. 6. D · O(n)
  7. 7. B · Θ(nlog₂ 3), circa n1,585
  8. 8. D · Lo zaino frazionario, in cui gli oggetti si possono dividere

Soluzioni complete passo passo: esercitati su questo argomento su examproblems.com.