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. ADivide l'array a metà e le fonde
  2. BInserisce ogni elemento in una parte ordinata crescente spostando gli altri
  3. CTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
  4. DScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
2.Facile

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

  1. ALineare
  2. BLogaritmica
  3. CQuadratica
  4. DCostante
3.Facile

Quale di queste cresce più lentamente quando n diventa grande?

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

Quale algoritmo di ordinamento è stabile?

  1. AQuicksort (tipica versione in loco)
  2. BMerge sort
  3. CSelection sort (versione tipica)
  4. DHeap sort
5.Media

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

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

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

  1. ACirca 1,000
  2. BCirca 20
  3. CCirca 100
  4. DCirca 500,000
7.Difficile

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

  1. AΘ(n3)
  2. BΘ(n log n)
  3. CΘ(nlog₂ 3), circa n1,585
  4. DΘ(n²)
8.Difficile

Quale definizione della classe NP è corretta?

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

Soluzioni

  1. 1. C · Trova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
  2. 2. A · Lineare
  3. 3. A · O(log n)
  4. 4. B · Merge sort
  5. 5. A · Algoritmo di Dijkstra
  6. 6. B · Circa 20
  7. 7. C · Θ(nlog₂ 3), circa n1,585
  8. 8. B · Problemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato

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