Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è il caso base di una funzione ricorsiva?

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

Quali sono i tre passi di un algoritmo divide et impera?

1. AIndovina, verifica, ripeti
2. BLeggi, calcola, scrivi
3. CDividi, risolvi (impera), combina
4. DOrdina, cerca, restituisci

Come si chiama una crescita O(2ⁿ)?

1. AEsponenziale
2. BLogaritmica
3. CLineare
4. DPolinomiale

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

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

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

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

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

1. AScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili
2. BScegliere l'attività che termina prima, poi ripetere con quelle compatibili
3. CScegliere l'attività che inizia prima
4. DScegliere per prima l'attività più breve

Quale tecnica garantisce al quicksort un tempo di esecuzione atteso O(n log n) su qualsiasi input?

1. AScegliere il pivot in modo uniformemente casuale
2. BUsare la ricorsione solo sul lato sinistro
3. CScegliere sempre il primo elemento
4. DOrdinare l'input prima di eseguire il quicksort

Quali due cose bisogna dimostrare per provare che un problema decisionale X è NP-completo?

1. AX non ha un algoritmo polinomiale, e X è decidibile
2. BX è in P, e X si riduce a SAT
3. CX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
4. DX si riduce a un problema in P, e X è in NP