Informatica I - Esercizi teoria 6

Domanda n. 4

Argomento: Algoritmi e complessita` 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 complessita` temporale

Domanda: La complessita` temporale dell'algoritmo di ricerca lineare e`:

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 e` esatta

Domanda n. 7

Argomento: Ricorsione

Domanda: Quando si puo` affermare che un metodo ricorsivo realizza un

algoritmo? Risposte:

1. quando ad ogni invocazione si risolve un problema piu` 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 puo` essere eliminata una ricorsione in coda?

Risposte:

1. non e` possibile eliminare la ricorsione

2. con la ricorsione multipla

3. con l'uso di un ciclo

Domanda n. 9

Argomento: Algoritmi e complessita` 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:

5. 2

6. 4

7. 3

8. nessuna delle precedenti e` esatta

Domanda n. 10

Argomento: Algoritmi e complessita` temporale

Domanda: Quali assunzioni e semplificazioni si fanno nella stima delle prestazioni di un

algoritmo? Risposte:

1. si assume che l'algoritmo sia realizzato in un particolare linguaggio di programmazione, ad esempio

Java

2. si considera il caso peggiore e si assume che tutte le operazioni primitive impieghino lo stesso

tempo di esecuzione

3. si considera costante il numero di accessi in lettura e scrittura

4. si considera il caso migliore