Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Che cosa significa che un'operazione ha tempo O(1)?

1. AIl suo tempo di esecuzione non cresce con la dimensione dell'input
2. BElabora esattamente un elemento per ogni secondo di tempo di esecuzione
3. CRichiede sempre esattamente un secondo
4. DPuò essere eseguita una sola volta

Qual è il caso base di una funzione ricorsiva?

1. ALa chiamata che usa più memoria
2. BIl caso con l'input più grande, che viene gestito prima di qualsiasi chiamata ricorsiva
3. CLa prima riga della funzione
4. DUn caso a cui si risponde direttamente senza un'altra chiamata ricorsiva

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ASì, ma solo se n è minore di 100
2. BNo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
3. CNo, perché per n grande n³ è minore di n²
4. DSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³

Che cosa significa che un problema ha una sottostruttura ottima?

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

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

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

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(n!)
2. BO(n² 2ⁿ)
3. CO(n³)
4. DO(2^n²)

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

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