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

Qual è la complessità temporale del merge sort nel caso peggiore?

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

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

  1. ADividi, risolvi (impera), combina
  2. BOrdina, cerca, restituisci
  3. CIndovina, verifica, ripeti
  4. DLeggi, calcola, scrivi
4.Media

La visita in ampiezza (BFS) su un grafo non pesato trova:

  1. AL'albero ricoprente minimo
  2. BI cammini minimi in grafi che contengono archi con peso negativo
  3. CI cammini minimi in numero di archi dal nodo di partenza
  4. DUn ordinamento topologico in tutti i grafi
5.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 log n)
  3. CO(n³)
  4. DO(n)
6.Media

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

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

L'algoritmo di programmazione dinamica di Held–Karp risolve esattamente il problema del commesso viaggiatore. Qual è il suo tempo di esecuzione per n città?

  1. AO(2n²)
  2. BO(n!)
  3. CO(n² 2ⁿ)
  4. DO(n³)
8.Difficile

L'ordinamento topologico è possibile solo per:

  1. AGrafi con pesi negativi
  2. BGrafi completi
  3. CGrafi non orientati
  4. DGrafi orientati aciclici (DAG)

Soluzioni

  1. 1. A · O(log n)
  2. 2. C · O(n log n)
  3. 3. A · Dividi, risolvi (impera), combina
  4. 4. C · I cammini minimi in numero di archi dal nodo di partenza
  5. 5. A · O(n²)
  6. 6. B · Circa 20
  7. 7. C · O(n² 2ⁿ)
  8. 8. D · Grafi orientati aciclici (DAG)

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