Strutture dati: domande di esercitazione con spiegazioni

1Che cos’è una struttura dati

Una struttura dati è un modo di organizzare i dati in memoria in modo che certe operazioni siano veloci: trovare un elemento, aggiungerne uno, rimuoverne uno.

Nessuna struttura è veloce in tutto. Sceglierne una significa scegliere quali operazioni devono costare poco. I loro costi si scrivono in notazione O grande, con n il numero di elementi.

I due mattoni fondamentali sono l’array e la lista concatenata.

Un array memorizza i suoi elementi in un unico blocco di memoria, uno dopo l’altro. Il computer può calcolare dove si trova l’elemento i, quindi leggere a[i] richiede O(1). Inserire all’inizio significa spostare ogni elemento: O(n).

Una lista concatenata memorizza ogni elemento in un nodo con un puntatore al nodo successivo. L’ultimo puntatore è null. Inserire in testa (h) cambia un solo puntatore: O(1). Ma per raggiungere l’elemento i bisogna seguire i puntatori: O(n).

Una lista doppiamente concatenata ha anche un puntatore al nodo precedente, quindi si può scorrere in entrambe le direzioni.

2Pile e code

Una pila (stack) è come una pila di piatti: si aggiunge e si toglie solo in cima. L’ultimo elemento entrato è il primo a uscire: LIFO.

• push mette un elemento in cima, pop rimuove l’elemento in cima, peek legge l’elemento in cima senza rimuoverlo. Tutte sono O(1).
• Usi: la funzione annulla di un editor, lo stack delle chiamate di un programma, il controllo del bilanciamento delle parentesi, la ricerca in profondità.

Una coda (queue) è come la fila a una cassa: ci si mette in fondo e si esce dalla testa. Il primo elemento entrato è il primo a uscire: FIFO.

• enqueue aggiunge in fondo, dequeue rimuove dalla testa. Entrambe sono O(1).
• Usi: lavori di stampa, messaggi in attesa di essere gestiti, ricerca in ampiezza.

Una deque (coda a doppia estremità) permette di aggiungere e rimuovere a entrambe le estremità. Una coda con priorità rimuove sempre per primo l’elemento con la priorità più alta; di solito è costruita come heap.

3Alberi, heap, tabelle hash e grafi

Un albero ha un nodo in alto, la radice. Ogni altro nodo ha esattamente un genitore. I nodi senza figli sono foglie. Un albero con n nodi ha n − 1 archi.

In un albero binario ogni nodo ha al massimo due figli. Un albero binario di ricerca (BST) aggiunge una regola: le chiavi nel sottoalbero sinistro sono minori del nodo, quelle nel sottoalbero destro sono maggiori.

Cercare in un BST segue un solo percorso verso il basso, quindi costa O(altezza). Un albero bilanciato (AVL, rosso-nero) mantiene l’altezza vicina a log₂ n. Chiavi inserite in ordine crescente formano una catena di altezza n.

Un heap è un albero binario in cui ogni genitore è minore dei suoi figli (min-heap) o maggiore (max-heap). Il minimo o il massimo è nella radice, e inserimento e rimozione costano O(log n).

Una tabella hash memorizza coppie chiave–valore. Una funzione hash trasforma la chiave in un indice, quindi inserimento e ricerca richiedono O(1) in media. Due chiavi con lo stesso indice sono una collisione, risolta con il concatenamento (una lista per ogni posizione) o con l’indirizzamento aperto (si prova un’altra posizione).

Un grafo ha vertici collegati da archi, che possono avere una direzione o un peso. Si memorizza come matrice di adiacenza, memoria O(V²), o come liste di adiacenza, O(V + E).

4Il metodo passo dopo passo

Le domande spesso descrivono un compito e chiedono quale struttura si adatta, oppure chiedono come appare una struttura dopo alcune operazioni.

1. Trova l’operazione che deve essere veloce: accesso per posizione, per chiave, l’elemento più recente, quello più vecchio, il più piccolo, o un intervallo.
2. Abbinala a una struttura: indice → array, chiave → tabella hash, più recente → pila, più vecchio → coda, più piccolo o più grande → heap, ordine o intervalli → albero di ricerca bilanciato.
3. Controlla il costo, in notazione O grande, delle altre operazioni di cui il compito ha bisogno.
4. Per una domanda di simulazione, esegui le operazioni una alla volta e annota lo stato dopo ciascuna.
5. Verifica lo stato finale rispetto alla regola della struttura: LIFO, FIFO, l’ordine del BST o l’ordine dell’heap.

5Un esempio svolto

Segui ogni passaggio. Prova a prevedere il successivo prima di aprirlo.

6Errori comuni

• Confondere LIFO e FIFO. Una pila restituisce l’elemento più recente, una coda il più vecchio.
• Pensare che una lista concatenata dia accesso rapido per indice. Deve scorrere dalla testa.
• Supporre che un BST sia sempre O(log n). Lo è solo un albero bilanciato; inserimenti ordinati danno O(n).
• Dimenticare le collisioni in una tabella hash. O(1) è il caso medio, non il caso peggiore.
• Confondere le visite. Preorder: prima il nodo. In-order: il nodo nel mezzo. Postorder: il nodo per ultimo.
• Usare una matrice di adiacenza per un grafo grande e sparso. Spreca memoria O(V²).

7Come sono fatte le domande d’esame

• Facile: termini e fatti chiave. LIFO e FIFO, che cos’è un nodo, una radice o una foglia, la regola del BST, che cosa fa una funzione hash.
• Medio: applicare i concetti. Quale struttura si adatta a un compito, il risultato di push e pop o di inserimenti in un BST, visite di alberi, una tabella hash con sondaggio lineare, costi in notazione O grande.
• Difficile: casi e analisi. Alberi bilanciati, heap negli array, B-tree, trie, union-find, filtri di Bloom e progetti come una cache LRU.

Per un heap memorizzato in un array a partire dall’indice 0, i figli dell’indice i si trovano in 2i + 1 e 2i + 2, e il suo genitore in ⌊(i − 1) / 2⌋.