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 è l'O grande di 3n² + 5n + 2?

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

Che cos'è un algoritmo a forza bruta?

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

Quale di questi tempi di esecuzione è polinomiale?

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

La programmazione dinamica è utile quando un problema presenta:

  1. ANessun sottoproblema, quindi si risolve in un solo passo
  2. BSottoproblemi sovrapposti e sottostruttura ottima
  3. CSolo input casuali
  4. DUn unico ciclo
5.Media

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

  1. ABellman-Ford è necessario in tutti i casi
  2. BVisita in profondità (DFS)
  3. CAlgoritmo di Kruskal
  4. DAlgoritmo di Dijkstra
6.Media

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

Perché la ricerca binaria non dà tempo O(log n) su una lista concatenata semplice?

  1. AI confronti sui nodi di una lista concatenata sono più lenti
  2. BLa ricerca binaria richiede almeno il doppio della memoria
  3. CRaggiungere l'elemento centrale richiede O(n) passi, perché non c'è accesso diretto tramite indice
  4. DLe liste concatenate non si possono ordinare
8.Difficile

Quali due cose bisogna dimostrare per provare che un problema decisionale X è NP-completo?

  1. AX non ha un algoritmo polinomiale, e X è decidibile
  2. BX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
  3. CX è in P, e X si riduce a SAT
  4. DX si riduce a un problema in P, e X è in NP

Soluzioni

  1. 1. A · O(n²)
  2. 2. C · Un algoritmo che prova tutte le possibili soluzioni candidate
  3. 3. B · O(n³)
  4. 4. B · Sottoproblemi sovrapposti e sottostruttura ottima
  5. 5. D · Algoritmo di Dijkstra
  6. 6. C · O(n log n)
  7. 7. C · Raggiungere l'elemento centrale richiede O(n) passi, perché non c'è accesso diretto tramite indice
  8. 8. B · X è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale

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