Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Come si chiama una crescita O(2ⁿ)?

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

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

1. ACirca n / 2
2. BCirca n²
3. CCirca log₂ n
4. DCirca n

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)

La programmazione dinamica è utile quando un problema presenta:

1. ASolo input casuali
2. BUn unico ciclo
3. CNessun sottoproblema, quindi si risolve in un solo passo
4. DSottoproblemi sovrapposti e sottostruttura ottima

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. AGli array hanno accesso O(n)
2. BMolte chiavi possono collidere nello stesso bucket
3. CLe chiavi devono prima essere ordinate
4. DLe funzioni hash sono lente

Quale affermazione su P e NP è corretta?

1. ALe soluzioni dei problemi NP non possono essere verificate rapidamente
2. BNP significa «non polinomiale»
3. CÈ stato dimostrato che P ≠ NP
4. DOgni problema in P appartiene anche a NP