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 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
2.Facile

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

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

Quale classe di complessità cresce più rapidamente per n grande?

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

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

  1. ALa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
  2. BIl merge sort non ha una struttura ricorsiva
  3. CI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
  4. DIl merge sort è già O(n)
6.Media

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

  1. AScegliere l'attività che termina prima, poi ripetere con quelle compatibili
  2. BScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili
  3. CScegliere l'attività che inizia prima
  4. DScegliere per prima l'attività più breve
7.Difficile

Quale definizione della classe NP è corretta?

  1. AProblemi che non sono polinomiali
  2. BProblemi che non si possono risolvere in tempo polinomiale
  3. CProblemi che nessun algoritmo può risolvere
  4. DProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato
8.Difficile

I cammini semplici minimi si possono trovare in tempo polinomiale. Che cosa si sa del trovare il cammino semplice più lungo tra due vertici in un grafo generico?

  1. ASi può risolvere con l'algoritmo di Dijkstra con pesi cambiati di segno
  2. BÈ sempre risolvibile in O(V + E)
  3. CÈ NP-difficile
  4. DÈ indecidibile

Soluzioni

  1. 1. C · Un algoritmo che prova tutte le possibili soluzioni candidate
  2. 2. A · O(log n)
  3. 3. C · O(2ⁿ)
  4. 4. B · O(V × E)
  5. 5. C · I suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
  6. 6. A · Scegliere l'attività che termina prima, poi ripetere con quelle compatibili
  7. 7. D · Problemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato
  8. 8. C · È NP-difficile

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