Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanto vale log₂ 1024?

1. A512
2. B10
3. C32
4. D12

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

1. ARichiede sempre esattamente un secondo
2. BPuò essere eseguita una sola volta
3. CIl suo tempo di esecuzione non cresce con la dimensione dell'input
4. DElabora esattamente un elemento per ogni secondo di tempo di esecuzione

Un algoritmo O(n²) impiega 1 secondo per n = 1000. Circa quanto impiega per n = 2000?

1. A8 secondi
2. B2 secondi
3. C1 secondo
4. D4 secondi

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

1. ACostante
2. BLineare
3. CLogaritmica
4. DEsponenziale

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

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

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

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

Il problema della fermata dimostra che:

1. ANessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma
2. BAlcuni programmi girano più velocemente su computer più veloci, quindi la terminazione dipende dall'hardware
3. COgni programma prima o poi si ferma
4. DI cicli andrebbero evitati