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 ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

  1. ACirca n²
  2. BCirca n
  3. CCirca n / 2
  4. DCirca log₂ n
2.Facile

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Quale notazione descrive un limite inferiore alla crescita?

  1. AΩ (Omega grande)
  2. BO (O grande)
  3. CΘ (Theta grande)
  4. Do (o piccolo)
4.Media

Qual è la complessità temporale di: for i = 1 to n: for j = 1 to i: lavoro O(1)?

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

La programmazione dinamica è utile quando un problema presenta:

  1. AUn unico ciclo
  2. BSolo input casuali
  3. CSottoproblemi sovrapposti e sottostruttura ottima
  4. DNessun sottoproblema, quindi si risolve in un solo passo
6.Media

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

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

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

  1. AMolte chiavi possono collidere nello stesso bucket
  2. BLe funzioni hash sono lente
  3. CGli array hanno accesso O(n)
  4. DLe chiavi devono prima essere ordinate
8.Difficile

Quale affermazione su P e NP è corretta?

  1. ANP significa «non polinomiale»
  2. BLe soluzioni dei problemi NP non possono essere verificate rapidamente
  3. CÈ stato dimostrato che P ≠ NP
  4. DOgni problema in P appartiene anche a NP

Soluzioni

  1. 1. D · Circa log₂ n
  2. 2. C · O(n²)
  3. 3. A · Ω (Omega grande)
  4. 4. C · O(n²)
  5. 5. C · Sottoproblemi sovrapposti e sottostruttura ottima
  6. 6. B · Circa 20
  7. 7. A · Molte chiavi possono collidere nello stesso bucket
  8. 8. D · Ogni problema in P appartiene anche a NP

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