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. ABubble sort
2. BMerge sort
3. CInsertion sort
4. DQuicksort

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

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

Qual è il caso base di una funzione ricorsiva?

1. AUn caso a cui si risponde direttamente senza un'altra chiamata ricorsiva
2. BLa chiamata che usa più memoria
3. CLa prima riga della funzione
4. DIl caso con l'input più grande, che viene gestito prima di qualsiasi chiamata ricorsiva

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

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

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

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

Quale affermazione su P e NP è corretta?

1. AÈ stato dimostrato che P ≠ NP
2. BLe soluzioni dei problemi NP non possono essere verificate rapidamente
3. COgni problema in P appartiene anche a NP
4. DNP significa «non polinomiale»

Quale algoritmo trova un albero ricoprente minimo aggiungendo ripetutamente l'arco più economico che non forma un ciclo?

1. AAlgoritmo di Prim a partire da un nodo
2. BAlgoritmo di Kruskal
3. CFloyd-Warshall
4. DAlgoritmo di Dijkstra