Scheda di esercizi di Algoritmi e complessità con soluzioni

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

Che cosa richiede la ricerca binaria al suo input?

1. AL'array deve contenere solo numeri positivi
2. BLa lunghezza dell'array deve essere una potenza di due
3. CL'array non deve avere più di 1000 elementi
4. DL'array deve essere ordinato

Quale di queste cresce più lentamente quando n diventa grande?

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

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

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

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

1. ABellman-Ford è necessario in tutti i casi
2. BAlgoritmo di Kruskal
3. CVisita in profondità (DFS)
4. DAlgoritmo di Dijkstra

La visita in ampiezza (BFS) su un grafo non pesato trova:

1. AL'albero ricoprente minimo
2. BUn ordinamento topologico in tutti i grafi
3. CI cammini minimi in grafi che contengono archi con peso negativo
4. DI cammini minimi in numero di archi dal nodo di partenza

L'insertion sort richiede O(n) su un input ordinato. Questo contraddice il limite inferiore Ω(n log n) per l'ordinamento per confronti?

1. ASì, ma solo per array più corti di 100
2. BNo, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
3. CSì, quindi il limite inferiore è sbagliato
4. DNo, perché l'insertion sort non è un ordinamento per confronti

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)