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 cosa significa che un'operazione ha tempo O(1)?

  1. AElabora esattamente un elemento per ogni secondo di tempo di esecuzione
  2. BIl suo tempo di esecuzione non cresce con la dimensione dell'input
  3. CPuò essere eseguita una sola volta
  4. DRichiede sempre esattamente un secondo
2.Facile

Quale notazione descrive un limite superiore della crescita?

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

Che cos'è un algoritmo a forza bruta?

  1. AUn algoritmo che gira su molti processori
  2. BUn algoritmo che tira a indovinare una risposta a caso
  3. CUn algoritmo che prova tutte le possibili soluzioni candidate
  4. DUn algoritmo che usa sempre la ricorsione
4.Media

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

  1. AIl greedy usa 3 monete; l'ottimo è 2
  2. BIl greedy usa 2 monete; l'ottimo è 2
  3. CIl greedy usa 3 monete; l'ottimo è 3
  4. DIl greedy usa 4 monete; l'ottimo è 3
5.Media

Perché nell'O grande la base del logaritmo di solito si omette, come in O(log n)?

  1. ATutti i logaritmi in informatica hanno base 10, quindi è sottintesa
  2. BI logaritmi sono sempre arrotondati a interi
  3. CLogaritmi con basi diverse differiscono solo per un fattore costante
  4. DLa base conta solo per n piccolo
6.Media

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

  1. AΩ(n²)
  2. BΩ(n)
  3. CΩ(log n)
  4. DΩ(n log 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. BEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
  3. CControlla se qualche arco ha peso negativo
  4. DConta i cicli con una visita in profondità
8.Difficile

Quale tecnica garantisce al quicksort un tempo di esecuzione atteso O(n log n) su qualsiasi input?

  1. AUsare la ricorsione solo sul lato sinistro
  2. BScegliere il pivot in modo uniformemente casuale
  3. CScegliere sempre il primo elemento
  4. DOrdinare l'input prima di eseguire il quicksort

Soluzioni

  1. 1. B · Il suo tempo di esecuzione non cresce con la dimensione dell'input
  2. 2. B · O grande (Big O)
  3. 3. C · Un algoritmo che prova tutte le possibili soluzioni candidate
  4. 4. A · Il greedy usa 3 monete; l'ottimo è 2
  5. 5. C · Logaritmi con basi diverse differiscono solo per un fattore costante
  6. 6. D · Ω(n log n)
  7. 7. A · Dopo V − 1 turni controlla se qualche arco può ancora essere rilassato
  8. 8. B · Scegliere il pivot in modo uniformemente casuale

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