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 è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

Qual è l'O grande di 3n² + 5n + 2?

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

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

  1. ABubble sort
  2. BQuicksort
  3. CMerge sort
  4. DHeap sort
4.Media

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

  1. AI cammini minimi in grafi che contengono archi con peso negativo
  2. BUn ordinamento topologico in tutti i grafi
  3. CL'albero ricoprente minimo
  4. DI cammini minimi in numero di archi dal nodo di partenza
5.Media

Un algoritmo greedy (goloso):

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

Perché nell'O grande la base del logaritmo di solito si omette, come in O(log n)?

  1. AI logaritmi sono sempre arrotondati a interi
  2. BLogaritmi con basi diverse differiscono solo per un fattore costante
  3. CLa base conta solo per n piccolo
  4. DTutti i logaritmi in informatica hanno base 10, quindi è sottintesa
7.Difficile

Qual è il tempo di esecuzione dell'algoritmo di Dijkstra con uno heap binario su un grafo con V vertici ed E archi?

  1. AO(V + E)
  2. BO(V × E)
  3. CO(V³)
  4. DO((V + E) log V)
8.Difficile

Che cosa ha stabilito il teorema di Cook–Levin?

  1. AIl problema della fermata è indecidibile
  2. BOgni problema NP si può risolvere in tempo esponenziale
  3. CIl problema della soddisfacibilità booleana (SAT) è NP-completo
  4. DP è diverso da NP

Soluzioni

  1. 1. C · O(n + k)
  2. 2. A · O(n²)
  3. 3. A · Bubble sort
  4. 4. D · I cammini minimi in numero di archi dal nodo di partenza
  5. 5. B · Compie la scelta localmente migliore a ogni passo
  6. 6. B · Logaritmi con basi diverse differiscono solo per un fattore costante
  7. 7. D · O((V + E) log V)
  8. 8. C · Il problema della soddisfacibilità booleana (SAT) è NP-completo

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