Paniere algoritmi e strutture dati - risposte multiple

Domande sulle strutture dati

FIFO02. Quale delle seguenti affermazioni è vera?

Pile e code rappresentano esattamente la stessa struttura dati

In una pila, inserimenti e cancellazioni avvengono allo stesso estremo

nessuna di queste risposte affermazioni è vera

03. La struttura di dati "coda" (o "queue")

si può realizzare solo con una lista collegata

realizza una politica FIFO.

serve per gestire le chiamate non ricorsive.

nessuna di queste risposte

04. La struttura di dati "pila" (o "stack")

realizza una politica FIFO.

si può realizzare solo con una lista collegata

serve per gestire le chiamate non ricorsive.

può essere realizzata facilmente con un array.

05. che somiglianze ci sono tra una pila e una coda?

entrambe le strutture dati possono essere realizzati con lo stesso tipo di dato astratto

nessuna di queste risposte

entrambi i tipi di dato astratto possono essere realizzati con la

stessa struttura dati

06. In una coda (queue) gli elementi vengono estratti utilizzando una politica

• FIFO
• dipende dai casi
• LIFO

07. che differenze ci sono tra una pila e una coda?

• la differenza sta nella struttura dati utilizzata
• la pila realizza una politica FIFO, la coda una politica LIFO
• la pila realizza una politica LIFO, la coda una politica FIFO
• nessuna di queste risposte

© 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 17/132Set Domande: ALGORITMI E STRUTTURE DATI INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04) Docente: Vecchio Massimo

08. cosa è una pila (stack)?

• un sinonimo di array
• nessuna di queste risposte
• una struttura dati
• un tipo di dato astratto

09. cosa è una coda (queue)?

• nessuna di queste risposte
• un sinonimo di lista concatenata
• una struttura dati
• un tipo di dato astratto

10. cosa è una coda (queue)? E' un ADT ossia un tipo di dato astratto. Realizza una politica

posizionale? È un tipo di dato astratto che realizza un contenitore di puntatori/reference ad elementi esterni alla lista. Nessuna di queste risposte è una struttura dati implementata internamente come un array di interi. È un tipo di dato astratto che realizza un contenitore di posizioni, ciascuna delle quali memorizza una posizione.

Quale situazione rappresenta il caso migliore dell'operazione di ricerca in una lista? Lista ordinata.

È possibile utilizzare una struttura dati array per realizzare un tipo di dato astratto Lista? Come? Con l'array lo Si, Si può utilizzare sia una array che un array dinamico che abbia una strategia di crescita (incrementale o con raddoppio). Lo spazio occupato sarà O(n), l'indicizzazione costante (get e set) e l'aggiunta di un elemento o la rimozione O(n). Possiamo descrivere le operazioni set(i,e) add(i,e) remove(i).

Cosa è una lista posizionale? Una lista posizionale è un tipo di dato astratto che realizza un contenitore di posizioni, ciascuna delle quali memorizza un elemento.

di dato astratto che realizza un contenitore di posizioni, ciascuna delle quali memorizza una posizione.

Quale situazione rappresenta il caso peggiore dell'operazione di ricerca in una lista? Lista ordinata al contrario.

si definisca una lista come tipo di dato astratto. Una lista prevede size, isEmpty, get(i), set(i,e), add(i,e), remove(i). Si può pensare come ad una Pila o Coda dove tuttavia gli elementi si possono inserire e rimuovere da posizioni arbitrarie. Non è una struttura necessariamente ordinata.

© 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 19/132Set Domande: ALGORITMI E STRUTTURE DATI INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04) Docente: Vecchio Massimo Lezione 016

01. L'indirizzamento aperto (open addressing) è una tecnica di gestione della RAM indica che un indirizzo di memoria contiene un indirizzo è una tecnica di scansione delle liste è una tecnica di gestione delle tabelle hash

02.

1. nessuna di queste risposte
2. 0,02
3. 0,002
4. 0,0002

1. Si ha collisione quando a chiavi diverse corrispondono valori diversi della funzione hash
2. Si ha collisione quando alla stessa chiave possono corrispondere valori diversi della funzione hash
3. Si ha collisione quando il valore della chiave coincide con quello della funzione hash
4. Si ha collisione quando a chiavi diverse corrisponde lo stesso valore della funzione hash

1. I nodi hanno al più 2 figli.

2. Quante foglie possono esserci al più in un albero binario di n nodi? (n + 1)/2

3. Quante foglie possono esserci al più in un albero binario di n nodi? (n+1)/2

4. Si definisca il tipo di dato astratto Albero. È un ADT che memorizza gli elementi in maniera gerarchica. Si compone di nodi che hanno una relazione genitore e figlio con l'eccezione della Root o Radice che sta in cima e non ha genitori. Se un nodo non ha figli viene definito foglia (o esterno). Un albero in cui ogni foglia ha al più 2 figli viene definito binario. Se ha 0 o 2 figli viene definito binario proprio.

5. Cosa è un albero binario? Un albero in cui ogni foglia ha al più 2 figli viene definito binario. Se le foglie dell'albero binario hanno 0 o 2 figli si parla di albero binario proprio. In un albero binario il numero di foglie è al massimo (n+1)/2 dove n sono i nodi dell'albero.

6. Come realizzeresti un albero?

binario (a livello di struttura dati)? Lo realizzerei con delle liste concatenate dove ogni elemento fa riferimento ad un elemento padre, ad un elemento figlio sx ed un elemento figlio destro oltre ovviamente al dato stesso. Da qui ne definirei proprio l'implementazione della classe foglia e della classe albero che di fatto punta alla foglia root.

© 2016 Università Telematica eCampus - Data Stampa 20/04/2017 09:45:53 - 22/132Set Domande: ALGORITMI E STRUTTURE DATI INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE (D.M. 270/04) Docente: Vecchio Massimo

Lezione 018

1. cosa si intende per programma?

   1. un programma è un'istanza di un algoritmo in un qualche linguaggio di programmazione
   2. progamma e problema sono sinonimi
   3. algoritmo e programma sono sinonimi
   4. nessuna di queste risposte

2. cosa si intende per problema?

   1. un problema non ha bisogno di un programma per essere risolto
   2. un problema è una funzione matematica che mappa un certo input in un certo output
   3. un problema è una situazione che richiede una soluzione
   4. nessuna di queste risposte

1. Cosa si intende per algoritmo?

Un algoritmo è un metodo per spiegare un problema.

Un algoritmo è un metodo o un processo eseguito per risolvere un problema.

Un algoritmo è un programma scritto in un determinato linguaggio di programmazione per risolvere un problema.

Nessuna di queste risposte.

2. Definire il concetto di tipo di dato astratto. Esemplificare

Un tipo di dato astratto (ADT) è un modello di struttura dati che specifica le caratteristiche degli oggetti di quel tipo e le operazioni che possono essere eseguite su tali tipi. È astratto perché non specifica come verrà concretamente implementato questo tipo.

3. Chiarire la differenza tra tipo di dato astratto e struttura