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 classe di complessità cresce più rapidamente per n grande?

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

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

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

Quale strategia di progettazione usa il merge sort?

  1. ADivide et impera
  2. BForza bruta
  3. CScelta greedy (golosa)
  4. DProgrammazione dinamica
4.Media

Un quicksort usa sempre il primo elemento come pivot. Su quale input mostra il comportamento del caso peggiore?

  1. AUn array già ordinato
  2. BUn array in ordine casuale
  3. CUn array di lunghezza 2
  4. DUn array con elementi tutti diversi
5.Media

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

  1. ALineare
  2. BCostante
  3. CEsponenziale
  4. DLogaritmica
6.Media

Qual è la complessità temporale di: for i = 1 to n: for j = 1 to i: lavoro O(1)?

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

Che cosa ha stabilito il teorema di Cook–Levin?

  1. AOgni problema NP si può risolvere in tempo esponenziale
  2. BIl problema della fermata è indecidibile
  3. CP è diverso da NP
  4. DIl problema della soddisfacibilità booleana (SAT) è NP-completo
8.Difficile

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

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

Soluzioni

  1. 1. A · O(2ⁿ)
  2. 2. D · O(log n)
  3. 3. A · Divide et impera
  4. 4. A · Un array già ordinato
  5. 5. C · Esponenziale
  6. 6. A · O(n²)
  7. 7. D · Il problema della soddisfacibilità booleana (SAT) è NP-completo
  8. 8. D · Raggiungere l'elemento centrale richiede O(n) passi, perché non c'è accesso diretto tramite indice

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