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 notazione descrive un limite superiore della crescita?

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

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

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

Qual è la complessità temporale della ricerca binaria in un array ordinato?

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

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

  1. ACirca 100
  2. BCirca 20
  3. CCirca 500,000
  4. DCirca 1,000
5.Media

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

  1. AΩ(log n)
  2. BΩ(n²)
  3. CΩ(n log n)
  4. DΩ(n)
6.Media

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

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

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

  1. ADopo V − 1 turni controlla se qualche arco può ancora essere rilassato
  2. BControlla se qualche arco ha peso negativo
  3. CEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
  4. DConta i cicli con una visita in profondità
8.Difficile

L'ordinamento topologico è possibile solo per:

  1. AGrafi con pesi negativi
  2. BGrafi orientati aciclici (DAG)
  3. CGrafi non orientati
  4. DGrafi completi

Soluzioni

  1. 1. C · O grande (Big O)
  2. 2. C · O(n²)
  3. 3. B · O(log n)
  4. 4. B · Circa 20
  5. 5. C · Ω(n log n)
  6. 6. D · O(n²)
  7. 7. A · Dopo V − 1 turni controlla se qualche arco può ancora essere rilassato
  8. 8. B · Grafi orientati aciclici (DAG)

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