Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Quale notazione descrive un limite inferiore alla crescita?

1. Ao (o piccolo)
2. BΘ (Theta grande)
3. CΩ (Omega grande)
4. DO (O grande)

Qual è la complessità temporale della visita in profondità (DFS) su un grafo memorizzato con liste di adiacenza?

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

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

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

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

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

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. AIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
2. BContinua a chiamare se stessa finché lo stack delle chiamate va in overflow
3. CRestituisce automaticamente 0
4. DViene eseguita in tempo O(1)

Quale definizione della classe P è corretta?

1. AProblemi che si possono risolvere in parallelo
2. BProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale
3. CProblemi che richiedono tempo esponenziale su ogni computer
4. DProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + n log n?

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