Paniere con risposte chiuse - Algoritmi e strutture dati (2023/2024)

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 020

01. La determinazione del massimo in un array di n elementi

richiede n - 1 confronti.

x richiede l'ordinamento della sequenza.

nessuna di queste risposte

richiede Theta(n^2) confronti.

02. cosa si intende per analisi asintotica?

nessuna di queste risposte

e' una tecnica per analizzare l'efficienza di un algoritmo, indipendentemente dalla macchina specifica, al crescere della dimensione dell'input

x e' una tecnica per analizzare l'efficienza di un algoritmo, su una macchina specifica presa come riferimento, al crescere della dimensione dell'input

e' una tecnica per analizzare l'efficienza di un algoritmo, su una macchina specifica presa come riferimento, su una determinata dimensione dell'input

03. In quanto tempo è possibile selezionare contemporaneamente il minimo, il mediano ed il massimo di una sequenza di n elementi?

O(n^2)

O(n)

x O(log n)

O(n log n)

04. Quanti confronti sono sufficienti nel caso peggiore per trovare l'elemento più piccolo in una sequenza di n elementi?

n+1

1

n-1

x log(n)

05. Qual è la complessità dell'algoritmo di ricerca binaria, in funzione del numero di elementi n?

O(log n) nel caso medio ed O(n) nel caso peggiore

O(log log n) nel caso medio

O(log n) nel caso peggiore

x O(n) nel caso peggiore

06. Qual è la complessità dell'algoritmo di ricerca sequenziale, in funzione del numero di elementi n?

O(log n) nel caso medio

O(log n) nel caso medio ed O(n) nel caso peggiore

O(n) nel caso peggiore

x O(log n) nel caso peggiore

07. si definisca formalmente la notazione O-grande (big Oh)

08. Perché la complessità di un problema e il costo computazionale di un algoritmo vengono misurate usando la notazione asintotica?

09. cosa si intende per analisi asintotica?

10. Quanti confronti sono sufficienti nel caso peggiore per trovare l'elemento più piccolo in una sequenza di n elementi?

11. In quanto tempo è possibile selezionare contemporaneamente il minimo, il mediano ed il massimo di una sequenza di n elementi?

12. si definisca formalmente la notazione Omega-grande © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 24/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

13. si definisca formalmente la notazione Theta-grande

14. Qual è la complessità dell'algoritmo di ricerca sequenziale, in funzione del numero di elementi n?

15. Qual è la complessità dell'algoritmo di ricerca binaria, in funzione del numero di elementi n? © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 25/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 021

01. Come misuriamo l'efficienza di un algoritmo?

In base al tempo necessario a scrivere un programma basato sull'algoritmo

In base alla quantità di risorse (tempo, spazio) richieste alla sua esecuzione

x In base al tempo necessario ad eseguire l'algoritmo su un'architettura di riferimento

In base al numero di linee di codice di un programma basato sull'algoritmo

02. Come si fa a stabilire se l'algoritmo A è effettivamente più veloce dell'algoritmo B?

è sufficiente analizzare il tempo di esecuzione asintotico dei due algoritmi

x Basta misurare le velocità di esecuzione dei due algoritmi scritti in linguaggio Assembler

Non si può stabilire in maniera generale: riusciremo solo a verificare su quali architetture e su quali istanze l'algoritmo A è più veloce dell'algoritmo B

Basta semplicemente calcolare il numero di linee di codice mandate in esecuzione dai due algoritmi

03. Perché è importante calcolare l'occupazione di memoria di un algoritmo?

E' utile quando non riusciamo a stimare il tempo di esecuzione di un algoritmo

Al giorno d'oggi, non è importante calcolare l'occupazione di memoria di un algoritmo perché la RAM di un calcolatore è sempre maggiore di quella necessaria

all'esecuzione dei nostri programmi

Se un algoritmo richiede troppo spazio di memoria potrebbe generare programmi che non producono alcun risultato

x L'occupazione di memoria dà un'idea del tempo richiesto per scrivere un programma basato sull'algoritmo

04. Perché è utile la notazione asintotica?

Per calcolare anche l'occupazione di memoria oltre che il tempo di esecuzione

Per ridurre il tempo di esecuzione dei nostri algoritmi

Perché le linee di codice di un programma non possono essere calcolate

Perché ci consente di stimare gli ordini di grandezza delle funzioni che vogliamo calcolare,

x

05. Quanti confronti esegue la ricerca sequenziale nel caso medio?

sempre n confronti, in ogni caso

3n/4 se l'elemento è presente nell'insieme, n se l'elemento non è presente nell'insieme

O(log n) se l'elemento è presente nell'insieme, n se l'elemento non è presente nell'insieme

(n + 1)/2 se l'elemento è presente nell'insieme, n se l'elemento non è presente nell'insieme

x

06. n(n-1)/100 è

O(n/100)

nessuna di queste risposte

O(n)

O(n^2)

x

07. Come misuriamo l'efficienza di un algoritmo?

08. Come si fa a stabilire se l'algoritmo A è effettivamente più veloce dell'algoritmo B?

09. Perché è utile la notazione asintotica?

10. Perché è importante calcolare l'occupazione di memoria di un algoritmo?

11. Quanti confronti esegue la ricerca sequenziale nel caso medio? © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 26/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 022

01. Quali sono gli algoritmi più efficienti, quelli ricorsivi o quelli iterativi?

Quelli iterativi

x Quelli ricorsivi

Nessuno dei due: sono gli algoritmi scritti in C ad essere i più efficienti

Non può essere stabilito in maniera generale

02. Le chiamate ricorsive di procedure

nessuna di queste risposte

x in generale possono essere eliminate usando uno stack

vanno evitate a ogni costo

non possono essere eliminate

03. Quali vantaggi introduce la ricorsione?

04. Quali svantaggi introduce la ricorsione?

05. Quali sono gli algoritmi più efficienti, quelli ricorsivi o quelli iterativi? © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 27/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 023

01. un algoritmo greedy ha il seguente costo computazionale

nessuna di queste risposte

sempre polinomiale

dipende dal problema

x sempre costante

02. Le tecniche greedy

servono a risolvere problemi ricorsivi.

�trovano sempre una soluzione, che però può non essere affatto ottima.

x consentono sempre di trovare una soluzione ottima.

come dice il nome, richiedono troppe risorse, in generale più della programmazione dinamica.

03. Un algoritmo goloso (greedy) è sempre in grado di trovare la soluzione ottima di un problema?

solo se il problema può essere risolto in tempo polinomiale

mai

qualche volta

x sempre

04. Quali svantaggi introduce l'approccio greedy?

05. Un algoritmo goloso (greedy) è sempre in grado di trovare la soluzione ottima di un problema?

06. Quali vantaggi introduce l'approccio greedy?

07. Definire un problema computazionale adatto ad essere risolto con un algoritmo greedy © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 28/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 024

01. La strategia algoritmica di forza bruta

è applicabile solo a problemi di complessità polinominale

è applicabile solo a problemi di complessità superiore alla polinominale

è sempre applicabile

nessuna di queste risposte

x

02. Il problema dell 8 regine

nessuna di queste risposte

x non è risolvibile utilizzando la strategia del backtracking

ha una complessità polinomiale

si risolve solo con la strategia di backtracking © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 29/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 025

01. Quanti confronti vengono eseguiti dalla ricerca binaria nel caso migliore?

O(n)

1

x O(log n)

O(log log n)

02. Quale dei seguenti algoritmi è basato sulla tecnica divide et impera?

insertionSort

selectionSort

bucketSort

mergeSort

x

03. Quali vantaggi introduce l'approccio divide et impera?

04. Quali svantaggi introduce l'approccio divide et impera?

05. Annoverare un esempio di algoritmo basato sulla tecnica del divide et impera

06. Quanti confronti vengono eseguiti dalla ricerca binaria nel caso migliore? © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 30/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 026

01. Le tecniche di programmazione dinamica

sono più efficienti delle tecniche greedy

x sono molto faticose per il programmatore

consentono, in generale, di risolvere problemi di ottimizzazione

si utilizzano quando non è possibile usare tecniche greedy

02. L'approccio della programamzione dinamica ha il seguente costo computazionale

sempre polinomiale

sempre esponenziale

dipende dal problema

x sempre lineare © 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 31/132

Set Domande: ALGORITMI E STRUTTURE DATI

INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04)

Docente: Vecchio Massimo

Lezione 027

01. la radice di un albero è quel nodo che

ha più fratelli di tutti gli altri nodi

non ha padre

x ha più figli di tutti gli altri nodi

non ha figli

02. l'altezza di un nodo n dell'albero (anche detta profondità del nodo) è data

x dalla distanza tra il nodo n è la radice dell'albero

dalla distanza massima tra il nodo n e una foglia dell'albero

nessuna di queste risposte

dal numero di figli del nodo n

03. la foglia di un albero è un nodo che

non h