Scheda di esercizi di Algoritmi e complessità con soluzioni

Come funziona il selection sort?

1. AInserisce ogni elemento in una parte ordinata crescente spostando gli altri
2. BScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
3. CDivide l'array a metà e le fonde
4. DTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa

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

1. AElabora esattamente un elemento per ogni secondo di tempo di esecuzione
2. BIl suo tempo di esecuzione non cresce con la dimensione dell'input
3. CRichiede sempre esattamente un secondo
4. DPuò essere eseguita una sola volta

Che cos'è la memoizzazione?

1. AConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate
2. BLiberare la memoria dopo il ritorno di una funzione
3. CMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
4. DScrivere commenti accanto a ogni riga di codice

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

1. AIl greedy usa 2 monete; l'ottimo è 2
2. BIl greedy usa 4 monete; l'ottimo è 3
3. CIl greedy usa 3 monete; l'ottimo è 2
4. DIl greedy usa 3 monete; l'ottimo è 3

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 Dijkstra
3. CFloyd-Warshall
4. DAlgoritmo di Kruskal

2²ⁿ è in O(2ⁿ)?

1. ANo, perché 2²ⁿ cresce più lentamente di 2ⁿ
2. BSì, perché sono entrambi esponenziali
3. CSì, perché i fattori costanti nell'esponente si ignorano sempre nell'O grande
4. DNo, perché 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite