Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

Che cos'è la ricorsione?

1. AUn ciclo che non termina mai
2. BUn tipo di struttura dati
3. CUn metodo di ordinamento
4. DUna funzione che chiama se stessa su input più piccoli

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che prova tutte le possibili soluzioni candidate
2. BUn algoritmo che usa sempre la ricorsione
3. CUn algoritmo che gira su molti processori
4. DUn algoritmo che tira a indovinare una risposta a caso

Che cosa misura l'analisi ammortizzata?

1. AIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
2. BIl costo medio per operazione su una sequenza di operazioni nel caso peggiore
3. CIl costo di un algoritmo sull'input migliore
4. DIl costo atteso su input casuali

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(n + k)
4. DO(k n log 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³)
4. DO(n² log n)

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. BScegliere sempre il primo elemento
3. CUsare la ricorsione solo sul lato sinistro
4. DOrdinare l'input prima di eseguire il quicksort

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

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