Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

Qual è la complessità temporale nel caso peggiore dell'insertion sort?

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

Quale strategia di progettazione usa il merge sort?

1. AForza bruta
2. BProgrammazione dinamica
3. CScelta greedy (golosa)
4. DDivide et impera

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

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ALineare
2. BCostante
3. CEsponenziale
4. DLogaritmica

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

1. AI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
2. BLa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
3. CIl merge sort non ha una struttura ricorsiva
4. DIl merge sort è già O(n)

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

1. AEntrambe le varianti
2. BNessuna delle due varianti
3. CLo zaino 0/1, in cui gli oggetti si devono prendere sempre interi
4. DLo zaino frazionario, in cui gli oggetti si possono dividere

Quale definizione della classe NP è corretta?

1. AProblemi che non sono polinomiali
2. BProblemi che nessun algoritmo può risolvere
3. CProblemi che non si possono risolvere in tempo polinomiale
4. DProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato