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

Quanto vale log₂ 1024?

  1. A32
  2. B12
  3. C512
  4. D10
2.Facile

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Qual è la complessità temporale della ricerca binaria in un array ordinato?

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

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

  1. AIl merge sort è già O(n)
  2. BIl merge sort non ha una struttura ricorsiva
  3. CI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
  4. DLa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
5.Media

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

  1. AIl greedy usa 3 monete; l'ottimo è 2
  2. BIl greedy usa 4 monete; l'ottimo è 3
  3. CIl greedy usa 3 monete; l'ottimo è 3
  4. DIl greedy usa 2 monete; l'ottimo è 2
6.Media

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

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

Qual è il tempo di esecuzione dell'algoritmo di Dijkstra con uno heap binario su un grafo con V vertici ed E archi?

  1. AO((V + E) log V)
  2. BO(V + E)
  3. CO(V³)
  4. DO(V × E)
8.Difficile

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

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

Soluzioni

  1. 1. D · 10
  2. 2. B · O(n)
  3. 3. A · O(log n)
  4. 4. C · I suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
  5. 5. A · Il greedy usa 3 monete; l'ottimo è 2
  6. 6. B · O(d(n + k))
  7. 7. A · O((V + E) log V)
  8. 8. B · Θ(n log² n)

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