Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale classe di complessità cresce più rapidamente per n grande?

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

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

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

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

Un quicksort usa sempre il primo elemento come pivot. Su quale input mostra il comportamento del caso peggiore?

1. AUn array già ordinato
2. BUn array con elementi tutti diversi
3. CUn array in ordine casuale
4. DUn array di lunghezza 2

Che cosa significa che un problema ha una sottostruttura ottima?

1. AUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
2. BOgni sottoproblema ha la stessa dimensione
3. CIl problema si può risolvere in tempo costante
4. DIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. ASempre una copertura dei vertici minima
2. BDi qualità ignota rispetto all'ottimo
3. CAl massimo il doppio della dimensione di una copertura dei vertici minima
4. DAl massimo log n volte il minimo

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. ATutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
2. BIl problema della fermata diventerebbe decidibile
3. COgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
4. DSolo quel problema passerebbe in P