Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AQuicksort
2. BMerge sort
3. CBubble sort
4. DInsertion sort

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(n)
4. DO(1)

Quale strategia di progettazione usa il merge sort?

1. AForza bruta
2. BProgrammazione dinamica
3. CDivide et impera
4. DScelta greedy (golosa)

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

1. AO(log n)
2. BO(n log n)
3. CO(n)
4. DO(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 visita in ampiezza (BFS) su un grafo non pesato trova:

1. AI cammini minimi in numero di archi dal nodo di partenza
2. BI cammini minimi in grafi che contengono archi con peso negativo
3. CUn ordinamento topologico in tutti i grafi
4. DL'albero ricoprente minimo

Qual è la differenza tra un problema indecidibile e uno intrattabile?

1. AI problemi indecidibili sono in NP, mentre quelli intrattabili sono in P
2. BPer un problema indecidibile non esiste alcun algoritmo valido per tutti gli input; uno intrattabile ne ha uno, ma è troppo lento
3. CEntrambi significano che il problema non ha alcun algoritmo
4. DI problemi intrattabili non si possono risolvere con alcun algoritmo, mentre quelli indecidibili richiedono solo tempo esponenziale

Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?

1. AIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
2. BIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot
3. CLa selezione richiede sempre Ω(n log n) perché richiede un ordinamento
4. DLa selezione è possibile solo in O(n²)