Informatica I - Esercizi teoria 2

QUESTIONARIO 4

n. 1

Domanda

Argomento: Algoritmi e complessità temporale

Domanda: La funzione f(n) = n + 8 + log(n) è, in migliore approssimazione:

Risposte:

1. O(log n)

2. O(n)

3. O(n log n)

4. Nessuna delle precedenti risposte è corretta

Domanda n. 2

Argomento: Ricorsione

Domanda: Quale, tra le seguenti affermazioni, è corretta?

Risposte:

1. In un programma ricorsivo esiste un metodo che viene eseguito più volte

2. In un programma ricorsivo esiste almeno un metodo che viene invocato mentre una precedente invocazione

allo stesso metodo è ancora attiva

3. In un programma ricorsivo più metodi diversi sono invocati contemporaneamente

Domanda n. 3

Argomento: Algoritmi e complessità temporale

Domanda: La funzione T(n) = 3n + 10log(log(n)) + nlog(n) + 8 è:

Risposte:

1. O(n)

2. O(log(log(n)))

3. O(nlog n)

Domanda n. 4

Argomento: Algoritmi e complessità temporale

Domanda: La funzione f(n) e' O(g(n)) se:

Risposte:

1. esistono due costanti positive c e n0 tali che f(n) < c g(n), per tutti gli n >= n0

2. esistono due costanti positive c e n0 tali che g(n) < c f(n), per tutti gli n >= n0

3. esiste una costante positiva c tale che f(n) < c g(n), per tutti gli n > 0

4. Nessuna delle precedenti risposte e' corretta

Domanda n. 5

Argomento: Algoritmi e complessità temporale

Domanda: La complessità temporale dell'algoritmo di ricerca lineare è:

Risposte:

1. O(n) in media

2. O(1) solo nel caso di ricerca con successo

3. O(1) sempre

4. O(n) solo nel caso di ricerca senza successo

Domanda n. 6

Argomento: Ricorsione

Domanda: Quando un metodo effettua una chiamata ricorsiva:

Risposte:

1. viene eseguito fino alla sua terminazione piu' volte

2. sospende l'esecuzione del metodo invocante fino a quando ha terminato l'esecuzione del metodo invocato,

infine riprende l'esecuzione del metodo invocante

3. sospende l'esecuzione del metodo invocante fino a quando il metodo invocato non lo richiama nuovamente

4. nessuna delle precedenti è esatta

Domanda n. 7

Argomento: Ricorsione

Domanda: Quando si può affermare che un metodo ricorsivo realizza un algoritmo?

Risposte:

1. quando ad ogni invocazione si risolve un problema più complesso

2. quando possiede un caso base

3. quando il suo albero di ricorsione contiene un numero finito di chiamate ricorsive per qualsiasi input

4. quando il suo albero di ricorsione contiene un numero infinito di chiamate ricorsive per qualsiasi input

Domanda n. 8

Argomento: Ricorsione

Domanda: Come può essere eliminata una ricorsione in coda?

Risposte:

1. non è possibile eliminare la ricorsione

2. con la ricorsione multipla

3. con l'uso di un ciclo

Domanda n. 9

Argomento: Algoritmi e complessità temporale

Domanda: Se si vuole ordinare in ordine crescente un array composto dai numeri interi {15, 8, 6, 7} mediante

l'algoritmo di ordinamento per selezione, quanti scambi occorre fare?

Risposte:

1. 2

2. 4

3. 3

4. nessuna delle precedenti è esatta