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

Un algoritmo O(n²) impiega 1 secondo per n = 1000. Circa quanto impiega per n = 2000?

  1. A8 secondi
  2. B1 secondo
  3. C4 secondi
  4. D2 secondi
2.Facile

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

  1. ALineare
  2. BQuadratica
  3. CCostante
  4. DLogaritmica
3.Facile

Quale di questi tempi di esecuzione è polinomiale?

  1. AO(2ⁿ)
  2. BO(n!)
  3. CO(nⁿ)
  4. DO(n³)
4.Media

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

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

  1. AEsponenziale
  2. BCostante
  3. CLogaritmica
  4. DLineare
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(n²)
  4. DO(2ⁿ)
7.Difficile

Quali sono i costi in tempo e spazio del calcolo dell'n-esimo numero di Fibonacci con un ciclo che conserva solo gli ultimi due valori?

  1. ATempo O(n) e spazio O(1)
  2. BTempo O(2ⁿ) e spazio O(1)
  3. CTempo O(n) e spazio O(n)
  4. DTempo O(log n) e spazio O(n)
8.Difficile

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

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

Soluzioni

  1. 1. C · 4 secondi
  2. 2. A · Lineare
  3. 3. D · O(n³)
  4. 4. D · O(d(n + k))
  5. 5. A · Esponenziale
  6. 6. A · O(n)
  7. 7. A · Tempo O(n) e spazio O(1)
  8. 8. B · Θ(n log² n)

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