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

Come funziona il selection sort?

  1. AScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
  2. BDivide l'array a metà e le fonde
  3. CTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
  4. DInserisce ogni elemento in una parte ordinata crescente spostando gli altri
2.Facile

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

  1. A6 secondi
  2. B12 secondi
  3. C3 secondi
  4. D9 secondi
3.Facile

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

  1. AIndovina, verifica, ripeti
  2. BDividi, risolvi (impera), combina
  3. CLeggi, calcola, scrivi
  4. DOrdina, cerca, restituisci
4.Media

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(n)?

  1. AO(n log n)
  2. BO(n²)
  3. CO(n)
  4. DO(2ⁿ)
5.Media

Un algoritmo greedy (goloso):

  1. AFornisce sempre la soluzione ottima
  2. BCompie la scelta localmente migliore a ogni passo
  3. CUsa solo la ricorsione
  4. DProva ogni soluzione possibile
6.Media

Che cosa significa che un problema ha una sottostruttura ottima?

  1. AUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
  2. BIl problema si può risolvere in tempo costante
  3. COgni sottoproblema ha la stessa dimensione
  4. DIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
7.Difficile

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + n log n?

  1. AΘ(n²)
  2. BΘ(n)
  3. CΘ(n log² n)
  4. DΘ(n log n)
8.Difficile

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

  1. APerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
  2. BPerché funziona solo per W = 0
  3. CW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
  4. DPerché n è sempre piccolo

Soluzioni

  1. 1. C · Trova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
  2. 2. A · 6 secondi
  3. 3. B · Dividi, risolvi (impera), combina
  4. 4. B · O(n²)
  5. 5. B · Compie la scelta localmente migliore a ogni passo
  6. 6. A · Una soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
  7. 7. C · Θ(n log² n)
  8. 8. C · W è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W

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