Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

Quanto vale log₂ 1024?

1. A10
2. B12
3. C32
4. D512

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(k n log n)
2. BO(n + k)
3. CO(nk)
4. DO(n log n + k log n)

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. ARestituisce automaticamente 0
2. BIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
3. CContinua a chiamare se stessa finché lo stack delle chiamate va in overflow
4. DViene eseguita in tempo O(1)

Un quicksort usa sempre il primo elemento come pivot. Su quale input mostra il comportamento del caso peggiore?

1. AUn array già ordinato
2. BUn array di lunghezza 2
3. CUn array in ordine casuale
4. DUn array con elementi tutti diversi

Quale definizione della classe NP è corretta?

1. AProblemi che non si possono risolvere in tempo polinomiale
2. BProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato
3. CProblemi che nessun algoritmo può risolvere
4. DProblemi che non sono polinomiali

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

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