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

Che cos'è la ricorsione?

  1. AUna funzione che chiama se stessa su input più piccoli
  2. BUn metodo di ordinamento
  3. CUn tipo di struttura dati
  4. DUn ciclo che non termina mai
2.Facile

Quale notazione descrive un limite superiore della crescita?

  1. ATheta grande (Big Theta)
  2. BOmega piccolo (little omega)
  3. CO grande (Big O)
  4. DOmega grande (Big Omega)
3.Facile

Quanto vale log₂ 1024?

  1. A32
  2. B10
  3. C512
  4. D12
4.Media

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

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

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

  1. AO(mn)
  2. BO(2m+n)
  3. CO(m + n)
  4. DO(mn log n)
6.Media

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

  1. ACirca 500,000
  2. BCirca 100
  3. CCirca 20
  4. DCirca 1,000
7.Difficile

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

  1. ASolo quel problema passerebbe in P
  2. BTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
  3. CIl problema della fermata diventerebbe decidibile
  4. DOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
8.Difficile

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

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

Soluzioni

  1. 1. A · Una funzione che chiama se stessa su input più piccoli
  2. 2. C · O grande (Big O)
  3. 3. B · 10
  4. 4. D · O(log n)
  5. 5. A · O(mn)
  6. 6. C · Circa 20
  7. 7. D · Ogni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
  8. 8. D · Θ(n log² n)

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