Che cos’è una struttura dati e perché non basta dire che è un contenitore di valori?

Una struttura dati è un’organizzazione dei dati che determina anche il modo in cui li posso accedere e modificare. Non è solo un contenitore, perché la sua forma impone costi diversi alle operazioni fondamentali e quindi influenza l’efficienza dell’algoritmo. In pratica, scegliere una struttura significa scegliere un compromesso tra tempo, spazio e tipo di operazioni.

Qual è la differenza tra array e lista concatenata?

L’array memorizza gli elementi in posizioni contigue e consente accesso diretto per indice, quindi la lettura di un elemento è molto efficiente. La lista concatenata, invece, collega i nodi con puntatori e non offre accesso casuale: per raggiungere una posizione bisogna scorrere la lista. In compenso, inserimenti e cancellazioni possono essere più convenienti se si ha già il riferimento al punto giusto.

Che differenza c’è tra una pila e una coda?

La pila segue la politica LIFO, cioè l’ultimo elemento inserito è il primo a essere rimosso. La coda segue la politica FIFO, cioè il primo elemento inserito è il primo a uscire. Sono strutture astratte che si descrivono tramite operazioni come push e pop per la pila, enqueue e dequeue per la coda.

Come si implementano pila e coda con array o con liste concatenate?

Una pila si implementa bene sia con array sia con lista concatenata, perché servono operazioni di inserimento e rimozione a un estremo solo. Per una coda, con una lista concatenata conviene mantenere riferimenti a testa e coda per rendere efficienti sia inserimento sia rimozione. Con un array, invece, bisogna gestire attentamente gli indici o una struttura circolare per evitare spostamenti inutili.

Che cos’è un albero binario e quali sono le sue proprietà fondamentali?

Un albero binario è una struttura gerarchica in cui ogni nodo ha al massimo due figli, distinti in sinistro e destro. È definito in modo ricorsivo: un albero binario è vuoto oppure è formato da una radice e da due sottoalberi binari. Questa definizione ricorsiva è importante perché permette di descrivere facilmente visite e algoritmi sugli alberi.

Che cos’è un albero binario di ricerca e quale invariante lo caratterizza?

In un albero binario di ricerca, per ogni nodo, tutte le chiavi nel sottoalbero sinistro sono minori della chiave del nodo e tutte quelle nel sottoalbero destro sono maggiori. Questo invariante rende efficiente la ricerca, perché a ogni confronto si elimina metà del sottoalbero possibile. Se l’albero è bilanciato, le operazioni principali hanno costo logarithmico; se invece si degenera, il costo può peggiorare molto.

Perché gli alberi di ricerca possono degradare e perché questo è importante?

Un albero di ricerca può degradare quando gli inserimenti avvengono in un ordine sfavorevole, ad esempio quasi ordinato, e la struttura si avvicina a una lista. In quel caso l’altezza cresce molto e le operazioni perdono la loro efficienza attesa. Questo mostra che non basta conoscere la struttura astratta: bisogna anche considerare la sua forma concreta.

Che cos’è una tabella hash e qual è l’idea alla base dell’hashing?

Una tabella hash è una struttura che associa a una chiave una posizione tramite una funzione hash. L’idea è ottenere accesso medio molto rapido, perché la chiave viene trasformata direttamente in un indice dell’array sottostante. Il punto critico è che due chiavi diverse possono produrre lo stesso indice, quindi bisogna gestire le collisioni.

Che cosa sono le collisioni e come si possono gestire?

Una collisione si ha quando due chiavi diverse vengono mappate nella stessa posizione dalla funzione hash. Si possono gestire con indirizzamento aperto, cercando altre celle secondo una sequenza di probe, oppure con concatenamento, memorizzando nella stessa posizione una lista di elementi. La qualità della funzione hash e il fattore di carico sono decisivi per mantenere buone prestazioni.

Come rappresenti un grafo e quando scegli lista di adiacenza o matrice di adiacenza?

Un grafo si può rappresentare con una lista di adiacenza, dove per ogni vertice si elencano i vertici adiacenti, oppure con una matrice di adiacenza, dove una cella indica se esiste un arco tra due vertici. La lista di adiacenza è più adatta ai grafi sparsi, perché usa meno spazio; la matrice è comoda quando il grafo è denso o quando serve verificare rapidamente la presenza di un arco. La scelta dipende quindi sia dalla densità sia dalle operazioni richieste.

Come scegli la struttura dati giusta in base alle operazioni che devi fare?

La scelta dipende dal compromesso tra accesso, ricerca, inserimento, cancellazione e uso di memoria. Se ti serve accesso per indice, l’array è naturale; se ti servono inserimenti locali frequenti, una lista concatenata può essere più adatta; se vuoi ricerca ordinata, un albero di ricerca è utile; se vuoi accesso medio rapido per chiave, usi una tabella hash. Il punto d’esame è saper motivare la scelta, non elencare strutture a memoria.

Collega tabelle hash e alberi di ricerca: quando preferisci l’una o l’altro?

Le tabelle hash sono preferibili quando ti interessa soprattutto il recupero per chiave e non ti serve l’ordinamento. Gli alberi di ricerca, invece, sono migliori quando vuoi mantenere i dati ordinati o fare visite in ordine. Quindi la scelta dipende dal fatto che conti di più l’accesso medio molto rapido oppure la struttura ordinata dei dati.

Collega alberi e grafi: in che senso un albero è un caso particolare di grafo?

Un albero è un grafo connesso e aciclico, quindi è una struttura più vincolata rispetto a un grafo generale. Questa visione aiuta perché molte operazioni sugli alberi sono specializzazioni di algoritmi sui grafi, ma semplificate dai vincoli di gerarchia. Per questo gli alberi sono usati quando la relazione tra elementi è naturalmente gerarchica.

Da dove conviene partire se ho poco tempo?

Parti da array, liste, pila e coda, poi passa ad alberi binari di ricerca e tabelle hash. Se resta tempo, ripassa le rappresentazioni dei grafi e il criterio di scelta in base alle operazioni.

Cosa devo sapere bene per non sbagliare all’orale?

Devi sapere confrontare le strutture su accesso, inserimento, cancellazione, ricerca e memoria. Inoltre devi distinguere sempre tra struttura astratta e implementazione concreta.

Come posso collegare bene questo argomento ad altri temi del corso?

Collegalo alla complessità degli algoritmi, ai puntatori e alla gestione dinamica della memoria, e agli indici nelle basi di dati. Sono collegamenti naturali perché tutte queste scelte servono a rendere efficienti le operazioni sui dati.

Guida aggiornata: settembre 2026 · a cura di Skooly · tutte le guide · altre domande di programmazione

Domande d'esame sulle strutture dati: le 13 che escono davvero, con le risposte

Su le strutture dati il docente di solito ti chiede non solo di definirle, ma di spiegare perché una struttura è più adatta di un’altra rispetto alle operazioni richieste. Devi saper confrontare rappresentazioni, costi e invarianti, non fermarti alla semplice lista di tipi noti. Conta molto anche saper motivare la scelta in base a inserimento, cancellazione, ricerca e visita.

In due minuti: Una struttura dati è un modo organizzato di memorizzare i dati per rendere efficienti certe operazioni. Le più classiche sono array e liste concatenate, che differiscono per accesso diretto e costo degli inserimenti; poi ci sono pila e coda, che impongono politiche precise di accesso. Gli alberi, in particolare gli alberi binari di ricerca, sono utili per mantenere i dati ordinati, mentre le tabelle hash puntano su accesso medio rapido al prezzo della gestione delle collisioni. I grafi servono quando le relazioni non sono gerarchiche, e la scelta tra liste di adiacenza e matrice di adiacenza dipende da densità e operazioni da fare. In generale, non esiste la struttura migliore in assoluto: esiste quella più adatta al problema.

I termini che il prof si aspetta: array · lista concatenata · pila · coda · albero binario · albero binario di ricerca · tabella hash · collisione · grafo · lista di adiacenza · matrice di adiacenza · invariante.

Le domande che escono all'esame

Che cos’è una struttura dati e perché non basta dire che è un contenitore di valori?

Una struttura dati è un’organizzazione dei dati che determina anche il modo in cui li posso accedere e modificare. Non è solo un contenitore, perché la sua forma impone costi diversi alle operazioni fondamentali e quindi influenza l’efficienza dell’algoritmo. In pratica, scegliere una struttura significa scegliere un compromesso tra tempo, spazio e tipo di operazioni.

Cosa vuole sentire: Vuole la definizione corretta e l’idea che la struttura condiziona le operazioni e i costi. Errore tipico: Dire solo che è un insieme di dati memorizzati, senza legarla alle operazioni e all’efficienza.
Qual è la differenza tra array e lista concatenata?

L’array memorizza gli elementi in posizioni contigue e consente accesso diretto per indice, quindi la lettura di un elemento è molto efficiente. La lista concatenata, invece, collega i nodi con puntatori e non offre accesso casuale: per raggiungere una posizione bisogna scorrere la lista. In compenso, inserimenti e cancellazioni possono essere più convenienti se si ha già il riferimento al punto giusto.

Cosa vuole sentire: Vuole il confronto su accesso, memoria e costo delle modifiche. Errore tipico: Confondere l’accesso per indice con lo scorrimento sequenziale o dire che la lista è sempre più veloce dell’array.
Che differenza c’è tra una pila e una coda?

La pila segue la politica LIFO, cioè l’ultimo elemento inserito è il primo a essere rimosso. La coda segue la politica FIFO, cioè il primo elemento inserito è il primo a uscire. Sono strutture astratte che si descrivono tramite operazioni come push e pop per la pila, enqueue e dequeue per la coda.

Cosa vuole sentire: Vuole riconoscere le politiche di accesso e i nomi delle operazioni. Errore tipico: Scambiare LIFO e FIFO oppure parlare solo di implementazione senza dire la semantica.
Come si implementano pila e coda con array o con liste concatenate?

Una pila si implementa bene sia con array sia con lista concatenata, perché servono operazioni di inserimento e rimozione a un estremo solo. Per una coda, con una lista concatenata conviene mantenere riferimenti a testa e coda per rendere efficienti sia inserimento sia rimozione. Con un array, invece, bisogna gestire attentamente gli indici o una struttura circolare per evitare spostamenti inutili.

Cosa vuole sentire: Vuole il collegamento tra struttura astratta e implementazione concreta. Errore tipico: Dire che basta un array normale per una coda senza considerare il problema degli spostamenti.
Che cos’è un albero binario e quali sono le sue proprietà fondamentali?

Un albero binario è una struttura gerarchica in cui ogni nodo ha al massimo due figli, distinti in sinistro e destro. È definito in modo ricorsivo: un albero binario è vuoto oppure è formato da una radice e da due sottoalberi binari. Questa definizione ricorsiva è importante perché permette di descrivere facilmente visite e algoritmi sugli alberi.

Cosa vuole sentire: Vuole la definizione rigorosa e la visione ricorsiva. Errore tipico: Dire soltanto che è un albero con due rami, senza precisare la struttura ricorsiva e i sottoalberi.
Che cos’è un albero binario di ricerca e quale invariante lo caratterizza?

In un albero binario di ricerca, per ogni nodo, tutte le chiavi nel sottoalbero sinistro sono minori della chiave del nodo e tutte quelle nel sottoalbero destro sono maggiori. Questo invariante rende efficiente la ricerca, perché a ogni confronto si elimina metà del sottoalbero possibile. Se l’albero è bilanciato, le operazioni principali hanno costo logarithmico; se invece si degenera, il costo può peggiorare molto.

Cosa vuole sentire: Vuole l’invariante ordinante e il collegamento con l’efficienza. Errore tipico: Dimenticare che la proprietà deve valere per ogni nodo, non solo per la radice.
Perché gli alberi di ricerca possono degradare e perché questo è importante?

Un albero di ricerca può degradare quando gli inserimenti avvengono in un ordine sfavorevole, ad esempio quasi ordinato, e la struttura si avvicina a una lista. In quel caso l’altezza cresce molto e le operazioni perdono la loro efficienza attesa. Questo mostra che non basta conoscere la struttura astratta: bisogna anche considerare la sua forma concreta.

Cosa vuole sentire: Vuole capire la differenza tra caso medio e caso pessimo e il ruolo dell’altezza. Errore tipico: Pensare che un albero di ricerca garantisca sempre costi logarithmici.
Che cos’è una tabella hash e qual è l’idea alla base dell’hashing?

Una tabella hash è una struttura che associa a una chiave una posizione tramite una funzione hash. L’idea è ottenere accesso medio molto rapido, perché la chiave viene trasformata direttamente in un indice dell’array sottostante. Il punto critico è che due chiavi diverse possono produrre lo stesso indice, quindi bisogna gestire le collisioni.

Cosa vuole sentire: Vuole la definizione e l’idea di accesso tramite funzione hash. Errore tipico: Descrivere la tabella hash come una ricerca sempre immediata e senza problemi.
Che cosa sono le collisioni e come si possono gestire?

Una collisione si ha quando due chiavi diverse vengono mappate nella stessa posizione dalla funzione hash. Si possono gestire con indirizzamento aperto, cercando altre celle secondo una sequenza di probe, oppure con concatenamento, memorizzando nella stessa posizione una lista di elementi. La qualità della funzione hash e il fattore di carico sono decisivi per mantenere buone prestazioni.

Cosa vuole sentire: Vuole la definizione di collisione e almeno due tecniche di gestione. Errore tipico: Pensare che una collisione sia un errore raro da ignorare o confondere le tecniche di gestione.
Come rappresenti un grafo e quando scegli lista di adiacenza o matrice di adiacenza?

Un grafo si può rappresentare con una lista di adiacenza, dove per ogni vertice si elencano i vertici adiacenti, oppure con una matrice di adiacenza, dove una cella indica se esiste un arco tra due vertici. La lista di adiacenza è più adatta ai grafi sparsi, perché usa meno spazio; la matrice è comoda quando il grafo è denso o quando serve verificare rapidamente la presenza di un arco. La scelta dipende quindi sia dalla densità sia dalle operazioni richieste.

Cosa vuole sentire: Vuole confronto tra rappresentazioni e criterio di scelta. Errore tipico: Dire che una rappresentazione è sempre migliore dell’altra senza riferirsi alla densità del grafo.
Come scegli la struttura dati giusta in base alle operazioni che devi fare?

La scelta dipende dal compromesso tra accesso, ricerca, inserimento, cancellazione e uso di memoria. Se ti serve accesso per indice, l’array è naturale; se ti servono inserimenti locali frequenti, una lista concatenata può essere più adatta; se vuoi ricerca ordinata, un albero di ricerca è utile; se vuoi accesso medio rapido per chiave, usi una tabella hash. Il punto d’esame è saper motivare la scelta, non elencare strutture a memoria.

Cosa vuole sentire: Vuole il ragionamento comparativo e motivato. Errore tipico: Rispondere con una lista di strutture senza collegarle alle operazioni richieste.
Collega tabelle hash e alberi di ricerca: quando preferisci l’una o l’altro?

Le tabelle hash sono preferibili quando ti interessa soprattutto il recupero per chiave e non ti serve l’ordinamento. Gli alberi di ricerca, invece, sono migliori quando vuoi mantenere i dati ordinati o fare visite in ordine. Quindi la scelta dipende dal fatto che conti di più l’accesso medio molto rapido oppure la struttura ordinata dei dati.

Cosa vuole sentire: Vuole un confronto concettuale tra accesso per chiave e ordinamento. Errore tipico: Dire che hash e alberi fanno la stessa cosa, ignorando il problema dell’ordine.
Collega alberi e grafi: in che senso un albero è un caso particolare di grafo?

Un albero è un grafo connesso e aciclico, quindi è una struttura più vincolata rispetto a un grafo generale. Questa visione aiuta perché molte operazioni sugli alberi sono specializzazioni di algoritmi sui grafi, ma semplificate dai vincoli di gerarchia. Per questo gli alberi sono usati quando la relazione tra elementi è naturalmente gerarchica.

Cosa vuole sentire: Vuole il collegamento teorico tra strutture gerarchiche e grafi. Errore tipico: Considerare l’albero come una struttura del tutto separata dai grafi.

Fatti interrogare sulle strutture dati, come all'esame. Carica le tue dispense, le slide o le sbobine, scegli il livello università e Skoo ti fa queste domande a voce, con il rigore di un esame: ti incalza se sei vago e alla fine ti dà una pagella sui quattro criteri, con le frasi che hai detto. I primi 30 minuti sono gratis, senza carta. Simula l'esame sulle strutture dati

Le risposte vaghe che non passano

«L’array è veloce, la lista è lenta, la pila e la coda servono per gestire i dati, mentre gli alberi e gli hash sono strutture avanzate.»: Meglio: L’array offre accesso diretto per indice, mentre la lista concatenata è più flessibile negli inserimenti ma richiede attraversamento sequenziale. Pila e coda sono strutture astratte definite dalla politica di accesso, gli alberi organizzano i dati gerarchicamente e le tabelle hash puntano su accesso medio rapido tramite funzione hash e gestione delle collisioni.
«Un albero binario di ricerca è un albero che contiene i dati ordinati.»: Meglio: In un albero binario di ricerca, per ogni nodo, le chiavi del sottoalbero sinistro sono minori e quelle del destro sono maggiori. Questa proprietà di ordinamento vale ricorsivamente per tutti i nodi ed è ciò che rende efficienti ricerca, inserimento e cancellazione in un albero bilanciato.
«Per i grafi si usa la rappresentazione più comoda.»: Meglio: La scelta tra lista di adiacenza e matrice di adiacenza dipende dalla densità del grafo e dalle operazioni richieste. La lista è più adatta ai grafi sparsi, la matrice è utile quando serve verificare rapidamente l’esistenza di un arco o quando il grafo è denso.

I collegamenti che fanno salire il voto

Algoritmi e complessità — analisi dei costi asintotici. Le strutture dati si valutano soprattutto in base al costo delle operazioni fondamentali, quindi il legame con la complessità è diretto.
Programmazione — puntatori e gestione dinamica della memoria. Le liste concatenate, gli alberi e molte rappresentazioni di grafi richiedono familiarità con allocazione dinamica e riferimenti tra nodi.
Basi di dati — indici e organizzazione dell’accesso ai dati. La scelta tra ricerca lineare, hashing e strutture ordinate richiama il problema dell’accesso efficiente ai dati, centrale anche negli indici.

Come ti valuta la pagella sulle strutture dati

Un'interrogazione si valuta su quattro criteri. Ecco cosa fa la differenza in questo argomento:

Criterio	Cosa fa la differenza qui
Conoscenza dei contenuti	Fa la differenza saper definire ogni struttura con i suoi vincoli e i costi tipici, non solo riconoscerne il nome.
Correttezza espositiva e lessico specifico	Premia molto parlare per confronto: operazioni, vantaggi, limiti e casi d’uso, con terminologia precisa e senza confondere struttura astratta e implementazione.
Capacità di analisi e collegamenti	Conta saper motivare la scelta della struttura in funzione delle operazioni richieste e del caso medio o pessimo.
Autonomia nell'argomentare	Il voto sale se sai spiegare perché una struttura degenera, come cambia la scelta al variare della densità o del tipo di accesso, e se sai collegare argomenti diversi senza frasi memorizzate.

Criterio

Cosa fa la differenza qui

Conoscenza dei contenuti

Fa la differenza saper definire ogni struttura con i suoi vincoli e i costi tipici, non solo riconoscerne il nome.

Correttezza espositiva e lessico specifico

Premia molto parlare per confronto: operazioni, vantaggi, limiti e casi d’uso, con terminologia precisa e senza confondere struttura astratta e implementazione.

Capacità di analisi e collegamenti

Conta saper motivare la scelta della struttura in funzione delle operazioni richieste e del caso medio o pessimo.

Autonomia nell'argomentare

Il voto sale se sai spiegare perché una struttura degenera, come cambia la scelta al variare della densità o del tipo di accesso, e se sai collegare argomenti diversi senza frasi memorizzate.

Domande frequenti

Da dove conviene partire se ho poco tempo?: Parti da array, liste, pila e coda, poi passa ad alberi binari di ricerca e tabelle hash. Se resta tempo, ripassa le rappresentazioni dei grafi e il criterio di scelta in base alle operazioni.
Cosa devo sapere bene per non sbagliare all’orale?: Devi sapere confrontare le strutture su accesso, inserimento, cancellazione, ricerca e memoria. Inoltre devi distinguere sempre tra struttura astratta e implementazione concreta.
Come posso collegare bene questo argomento ad altri temi del corso?: Collegalo alla complessità degli algoritmi, ai puntatori e alla gestione dinamica della memoria, e agli indici nelle basi di dati. Sono collegamenti naturali perché tutte queste scelte servono a rendere efficienti le operazioni sui dati.

Altre domande d'esame di programmazione

La complessità degli algoritmi · La programmazione a oggetti · La ricorsione · Le basi di dati e SQL · Variabili, tipi e controllo del flusso · tutti gli argomenti di programmazione

Come si prepara un orale universitario: simulare l'esame orale · Skooly per l'università.

Le domande e le risposte modello di questa pagina sono generate con l'intelligenza artificiale a partire dal programma scolastico, passate da una verifica automatica dei fatti e riviste a campione dalla redazione di Skooly (AI Act, Art. 50). Hai trovato un errore? Scrivi a supporto@skooly.it e lo correggiamo.