Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

La complessità spaziale misura:

1. ALe dimensioni fisiche del computer
2. BIl numero di righe di codice
3. CLo spazio su disco del file del programma una volta compilato
4. DLa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input

Quale strategia di progettazione usa il merge sort?

1. AScelta greedy (golosa)
2. BProgrammazione dinamica
3. CDivide et impera
4. DForza bruta

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
2. BGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
3. CL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
4. DL'insertion sort è O(n log n) nel caso peggiore

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 log n + k log n)
2. BO(nk)
3. CO(k n log n)
4. DO(n + k)

Un algoritmo greedy (goloso):

1. AFornisce sempre la soluzione ottima
2. BUsa solo la ricorsione
3. CProva ogni soluzione possibile
4. DCompie la scelta localmente migliore a ogni passo

2²ⁿ è in O(2ⁿ)?

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

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

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