Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Qual è il caso base di una funzione ricorsiva?

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

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. ABubble sort
2. BQuicksort
3. CMerge sort
4. DInsertion sort

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

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

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

2²ⁿ è in O(2ⁿ)?

1. ASì, perché sono entrambi esponenziali
2. BNo, perché 2²ⁿ cresce più lentamente di 2ⁿ
3. CSì, perché i fattori costanti nell'esponente si ignorano sempre nell'O grande
4. DNo, perché 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite

Quale affermazione sulla notazione o piccolo è corretta?

1. A2n = o(n), perché 2n cresce lentamente
2. Bn = o(n), perché ogni funzione è o piccolo di se stessa
3. Cn = o(n²), ma n non è o(n)
4. Dn² = o(n)