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

Quali sono i tre passi di un algoritmo divide et impera?

  1. AOrdina, cerca, restituisci
  2. BDividi, risolvi (impera), combina
  3. CLeggi, calcola, scrivi
  4. DIndovina, verifica, ripeti
2.Facile

Quale di questi tempi di esecuzione è polinomiale?

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

Che cos'è la memoizzazione?

  1. AMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
  2. BConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate
  3. CScrivere commenti accanto a ogni riga di codice
  4. DLiberare la memoria dopo il ritorno di una funzione
4.Media

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

  1. ALogaritmica
  2. BLineare
  3. CEsponenziale
  4. DCostante
6.Media

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V³ × E)
7.Difficile

Quale definizione della classe P è corretta?

  1. AProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale
  2. BProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
  3. CProblemi che si possono risolvere in parallelo
  4. DProblemi che richiedono tempo esponenziale su ogni computer
8.Difficile

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

  1. AOgni confronto richiede un tempo logaritmico
  2. BOgni elemento deve essere confrontato almeno una volta
  3. CUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
  4. DLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti

Soluzioni

  1. 1. B · Dividi, risolvi (impera), combina
  2. 2. C · O(n³)
  3. 3. A · Memorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
  4. 4. A · O(d(n + k))
  5. 5. C · Esponenziale
  6. 6. B · O(V × E)
  7. 7. A · Problemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale
  8. 8. C · Un albero di decisione con n esiti possibili deve avere profondità almeno log₂ n

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