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

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

Che cos'è un algoritmo?

  1. AUna sequenza finita di passi ben definiti che risolve un problema
  2. BQualsiasi programma con un'interfaccia grafica
  3. CUn linguaggio di programmazione progettato per scrivere formule matematiche
  4. DUna struttura dati che memorizza numeri
3.Facile

Quale notazione descrive un limite inferiore alla crescita?

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

  1. AO(n)
  2. BO(n²)
  3. CO(log n)
  4. DO(1)
5.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)
6.Media

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

  1. AΘ(n3)
  2. BΘ(nlog₂ 3), circa n1,585
  3. CΘ(n log n)
  4. DΘ(n²)
8.Difficile

Come si confrontano n! e 2ⁿ per n grande?

  1. An! cresce più velocemente di 2ⁿ
  2. Bn! è O(n²)
  3. C2ⁿ cresce più velocemente di n!
  4. DCrescono allo stesso ritmo

Soluzioni

  1. 1. A · O(n)
  2. 2. A · Una sequenza finita di passi ben definiti che risolve un problema
  3. 3. A · Ω (Omega grande)
  4. 4. D · O(1)
  5. 5. C · O(n²)
  6. 6. A · O(n log n + k log n)
  7. 7. B · Θ(nlog₂ 3), circa n1,585
  8. 8. A · n! cresce più velocemente di 2ⁿ

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