Qual è la complessità temporale di un algoritmo che impiega sempre la stessa quantità di tempo per l’esecuzione, indipendentemente dalla dimensione dell’input?
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.
La quantità di lavoro cresce con il numero degli elementi?
Se una lista semplicemente concatenata non memorizza la propria lunghezza, qual è la complessità temporale per calcolarla attraversando i nodi?
Per calcolare la lunghezza di una lista collegata singola, devi attraversare ogni nodo dalla testa alla coda, risultando in una complessità temporale O(n).
Non c’è un contatore memorizzato: quanti nodi devi visitare?
Quale visita rileva un ciclo in un grafo orientato trovando un arco verso un vertice ancora presente nello stack di ricorsione?
La ricerca in profondità (DFS) è tipicamente usata per rilevare cicli in un grafo mantenendo uno stack di ricorsione per tenere traccia dei nodi visitati.
Quale visita mantiene attiva la catena di chiamate ricorsive?
Qual è la complessità temporale media per accedere a un elemento in una tabella hash?
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.
Quale algoritmo greedy per i cammini minimi da una singola sorgente seleziona ripetutamente il vertice non ancora definitivo con la distanza provvisoria minima, tipicamente usando una coda di priorità, e richiede pesi degli archi non negativi?
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.
Osserva la scelta greedy del vertice con distanza provvisoria minima.
Quale gruppo contiene esempi di alberi di ricerca binari autobilancianti?
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.
Quali alberi ristabiliscono il bilanciamento dopo le modifiche?
Cosa deve essere definito in una funzione ricorsiva per evitare la ricorsione infinita?
Un caso base è necessario in una funzione ricorsiva per fermare le chiamate ricorsive quando viene soddisfatta una condizione specifica, evitando la ricorsione infinita.
Quale condizione interrompe le chiamate ricorsive?
Quali sono le condizioni per eseguire l’ordinamento topologico su un grafo?
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à.
Un ciclo può rispettare un ordine in cui ogni predecessore viene prima?
Qual è la complessità temporale di un’implementazione ricorsiva ingenua della serie di Fibonacci?
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.
Le stesse sottosequenze vengono calcolate ripetutamente.
Quale struttura dati è comunemente usata per implementare una coda prioritaria?
Una coda prioritaria è più spesso implementata usando un heap perché permette un’estrazione efficiente dell’elemento con priorità più alta o più bassa.
Quale struttura rende economica l’estrazione dell’elemento prioritario?
Quale insieme elenca gli ordini di attraversamento depth‑first più comuni per un albero binario?
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.
Pensa a quando visiti la radice rispetto ai due sottoalberi.
Bubble Sort standard è stabile se scambia due elementi adiacenti solo quando la chiave a sinistra è strettamente maggiore di quella a destra?
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à.
Il confronto stretto può scambiare due chiavi uguali?
