Quiz: Strutture Dati e Algoritmi

Gli stack sono i più adatti ai modelli di accesso LIFO. Le code sono i più adatti ai modelli di accesso FIFO (First In, First Out).

O(1) rappresenta la complessità temporale costante. Significa che l’algoritmo impiega sempre la stessa quantità di tempo per l’esecuzione, indipendentemente dalla dimensione dell’input.

Per calcolare la lunghezza di una lista collegata singola, devi attraversare ogni nodo dalla testa alla coda, risultando in una complessità temporale O(n).

In un BST bilanciato, la complessità temporale media per la ricerca è O(log n) perché ogni livello dimezza lo spazio di ricerca.

Merge Sort opera sempre con una complessità nel caso peggiore di O(n log n) poiché divide ripetutamente l’array a metà e unisce i sottoarray ordinati.

BFS utilizza una Coda per esplorare i nodi livello per livello, elaborando i nodi in ordine di ampiezza (per “riga”).

La ricerca in profondità (DFS) è tipicamente usata per rilevare cicli in un grafo mantenendo uno stack di ricorsione per tenere traccia dei nodi visitati.

Heap Sort mantiene una complessità temporale nel caso peggiore di O(n log n), poiché costruisce un heap ed estrae ripetutamente l’elemento massimo.

Le tabelle hash hanno una complessità temporale media di O(1) per l’accesso agli elementi, assumendo una buona funzione hash che minimizza le collisioni.

Le operazioni principali di uno stack sono Push (aggiungi elemento), Pop (rimuovi elemento) e Peek (visualizza l’elemento in cima senza rimuoverlo).

L’Algoritmo di Dijkstra è spesso usato per trovare il percorso più breve nei grafi con pesi degli archi non negativi. Utilizza una coda di priorità per determinare la distanza minima in modo efficiente.

Gli alberi AVL e gli alberi Rosso-Nero sono tipi di alberi autobilancianti, che garantiscono che l’albero rimanga bilanciato dopo ogni inserimento o cancellazione.

Un caso base è necessario in una funzione ricorsiva per fermare le chiamate ricorsive quando viene soddisfatta una condizione specifica, evitando la ricorsione infinita.

Le due operazioni principali in una coda sono Enqueue (aggiungi un elemento alla fine) e Dequeue (rimuovi un elemento dall’inizio).

L’ordinamento topologico può essere eseguito su un grafo se è orientato e aciclico (DAG). Questo tipo di ordinamento è utile nei problemi di pianificazione delle attività.

L’implementazione ricorsiva ingenua della serie di Fibonacci ha una complessità temporale di O(2^n) a causa dei numerosi calcoli ripetuti per ogni numero di Fibonacci.

Una coda prioritaria è più spesso implementata usando un heap perché permette un’estrazione efficiente dell’elemento con priorità più alta o più bassa.

In-order, Pre-order e Post-order sono i tre ordini di attraversamento depth‑first più comuni per gli alberi binari, ognuno con un ordine diverso di visita dei nodi. Anche l’attraversamento breadth‑first è comune, ma appartiene a una categoria di attraversamento diversa.

In un min-heap, la radice è sempre l’elemento più piccolo e l’altezza dell’albero è O(log n), rendendo l’inserimento e l’estrazione efficienti.

Con il confronto stretto indicato, gli elementi con chiavi uguali non si superano mai, quindi Bubble Sort è stabile. Un’implementazione che scambia anche chiavi uguali può perdere questa proprietà.