Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo?

1. AUna struttura dati che memorizza numeri
2. BUna sequenza finita di passi ben definiti che risolve un problema
3. CUn linguaggio di programmazione progettato per scrivere formule matematiche
4. DQualsiasi programma con un'interfaccia grafica

Qual è il caso base di una funzione ricorsiva?

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

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

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. BL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
3. CL'insertion sort è O(n log n) nel caso peggiore
4. DGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi

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

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

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

1. AO(V × E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V + E)

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

1. A2-SAT, in cui ogni clausola ha al massimo due letterali
2. B3-SAT, in cui ogni clausola ha esattamente tre letterali
3. CSAT generale su formule in forma normale congiuntiva
4. DLa soddisfacibilità dei circuiti

Qual è il costo ammortizzato dell'incremento di un contatore binario, dato che un incremento può invertire molti bit?

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