Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di questi tempi di esecuzione è polinomiale?

1. AO(2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(nⁿ)

Che cos'è la ricorsione?

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

Che cos'è un algoritmo?

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

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

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

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

Quale affermazione sulla notazione o piccolo è corretta?

1. An = o(n), perché ogni funzione è o piccolo di se stessa
2. Bn = o(n²), ma n non è o(n)
3. Cn² = o(n)
4. D2n = o(n), perché 2n cresce lentamente

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. ADi qualità ignota rispetto all'ottimo
2. BAl massimo il doppio della dimensione di una copertura dei vertici minima
3. CSempre una copertura dei vertici minima
4. DAl massimo log n volte il minimo