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 di questi tempi di esecuzione è polinomiale?

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

Qual è la complessità temporale del merge sort nel caso peggiore?

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

Qual è l'O grande di 3n² + 5n + 2?

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

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

  1. ACirca n
  2. BCirca n / 2
  3. CCirca log₂ n
  4. DCirca √n
6.Media

La programmazione dinamica è utile quando un problema presenta:

  1. ASottoproblemi sovrapposti e sottostruttura ottima
  2. BSolo input casuali
  3. CUn unico ciclo
  4. DNessun sottoproblema, quindi si risolve in un solo passo
7.Difficile

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

  1. AΘ(n³)
  2. BΘ(n2)
  3. CΘ(n² log n)
  4. DΘ(nlog₂ 7), circa n2,81
8.Difficile

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

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

Soluzioni

  1. 1. C · O(n³)
  2. 2. C · O(n log n)
  3. 3. B · O(n²)
  4. 4. B · O(n log n)
  5. 5. C · Circa log₂ n
  6. 6. A · Sottoproblemi sovrapposti e sottostruttura ottima
  7. 7. D · Θ(nlog₂ 7), circa n2,81
  8. 8. A · O(n)

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