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

Quanto vale log₂ 1024?

  1. A32
  2. B12
  3. C512
  4. D10
2.Facile

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

  1. ALeggi, calcola, scrivi
  2. BIndovina, verifica, ripeti
  3. CDividi, risolvi (impera), combina
  4. DOrdina, cerca, restituisci
3.Facile

Qual è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

Come costruisce l'algoritmo di Prim un albero ricoprente minimo?

  1. AEsegue una visita in ampiezza e conserva l'albero BFS
  2. BOrdina tutti gli archi per peso e aggiunge ciascuno di essi a meno che non formi un ciclo nella foresta
  3. CFa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero
  4. DRimuove l'arco più costoso finché non restano cicli
5.Media

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

  1. AO(n²)
  2. BO(dn log k)
  3. CO(d(n + k))
  4. DO(n log n)
6.Media

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

  1. AΩ(n)
  2. BΩ(n log n)
  3. CΩ(n²)
  4. DΩ(log n)
7.Difficile

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

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

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

  1. AAl massimo il doppio della dimensione di una copertura dei vertici minima
  2. BDi qualità ignota rispetto all'ottimo
  3. CAl massimo log n volte il minimo
  4. DSempre una copertura dei vertici minima

Soluzioni

  1. 1. D · 10
  2. 2. C · Dividi, risolvi (impera), combina
  3. 3. B · O(n + k)
  4. 4. C · Fa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero
  5. 5. C · O(d(n + k))
  6. 6. B · Ω(n log n)
  7. 7. A · W è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
  8. 8. A · Al massimo il doppio della dimensione di una copertura dei vertici minima

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