Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è il caso base di una funzione ricorsiva?

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

Qual è la complessità temporale della ricerca binaria in un array ordinato?

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

Che cosa richiede la ricerca binaria al suo input?

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

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

1. AGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
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. DL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati

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

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

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

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

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

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

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