Qual è il costo ammortizzato di union/find con compressione dei cammini e unione per rango?

O(α(n)) per operazione: α è l'inversa di Ackermann e n il numero di elementi. L'inizializzazione costa O(n); il limite riguarda una sequenza, non un costo costante nel caso peggiore di ogni chiamata.

Quali proprietà deve avere una funzione hash per la ricerca in tabella?

Deve essere deterministica e distribuire bene le chiavi attese. Calcolare l'hash di chiavi di dimensione fissa può costare O(1); quello di una nuova stringa di L caratteri costa in genere O(L).

Perché una lista doppiamente concatenata può eliminare un nodo dato in O(1)?

I collegamenti al precedente e al successivo permettono di ricollegare direttamente i vicini. Si aggiornano testa e coda se necessario, senza cercare il predecessore.

Come evita gli spostamenti una coda in un array circolare dopo un'estrazione?

Gli indici di testa e coda avanzano modulo la capacità. L'estrazione avanza la testa, consentendo di riutilizzare le celle libere senza spostare gli altri elementi.

Dove sono genitore e figli del nodo i in un array heap di lunghezza n indicizzato da zero?

Genitore: ⌊(i−1)/2⌋ per i>0. Figli: 2i+1 e 2i+2, solo se tali indici sono minori di n. L'indice 0 non ha genitore.

Che differenza c'è tra O, Ω e Θ?

Indicano rispettivamente un limite asintotico superiore, inferiore e stretto. Descrivono una specifica funzione di costo; O non significa di per sé «caso peggiore».

Quali sono l'ordine di accesso e i costi tipici delle operazioni di una coda?

FIFO: inserimento in fondo, estrazione dalla testa. Entrambi costano O(1) con collegamenti a testa e coda o un buffer circolare di capacità fissa; spostare un array rende l'estrazione O(n).

Come differiscono compressione dei cammini, unione per rango e unione per dimensione?

La compressione reindirizza alla radice i nodi visitati. Per rango, la radice di rango minore va sotto quella di rango maggiore; per dimensione, l'insieme più piccolo sotto il più grande. Il rango può differire dall'altezza corrente.

Cosa fanno find e union in una struttura di insiemi disgiunti?

find(x) restituisce il rappresentante dell'insieme di x. union(x,y) unisce i loro insiemi se sono diversi; se coincidono già, la partizione non cambia.

Come visita un albero binario la visita per livelli?

Una coda FIFO permette di visitare un livello di profondità alla volta. Accodare il figlio sinistro prima del destro dà l'ordine da sinistra a destra.

Quali sono gli ordini delle visite in preordine, inordine e postordine di un albero binario?

Preordine: nodo → sinistra → destra. Inordine: sinistra → nodo → destra. Postordine: sinistra → destra → nodo.

Raddoppiando la capacità, qual è il costo ammortizzato di un inserimento in fondo a un array dinamico?

O(1) per inserimento. Un ridimensionamento può costare O(n), ma n inserimenti in fondo a partire da un array vuoto costano complessivamente O(n).

Per funzioni non negative f e g, cosa significa f(n) ∈ O(g(n))?

Esistono costanti c > 0 e n₀ ≥ 0 tali che f(n) ≤ c·g(n) per ogni n ≥ n₀.

Quali risposte può dare un filtro di Bloom che consente solo inserimenti?

Un risultato negativo indica che l'elemento non è stato inserito; uno positivo che potrebbe esserlo stato. Gli hash impostano bit in un array: sono possibili falsi positivi, ma non falsi negativi se lo stato è intatto.

Come dipendono dall'altezza h ricerca, inserimento ed eliminazione in un BST?

Costano O(h). Un albero bilanciato ha h = O(log n), una catena h = O(n). Il costo atteso O(log n) richiede ipotesi come un ordine casuale di inserimento.

Quanto costa costruire un heap dal basso verso l'alto a partire da n elementi?

O(n). La maggioranza dei nodi è vicina alle foglie e richiede poche discese; sommando il lavoro per altezza del nodo si ottiene un totale lineare.

Ordina queste crescite dalla più lenta alla più rapida per n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

Asintoticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Perché l'accesso per indice in un array di dimensione fissa costa O(1)?

Le celle, di uguale dimensione, sono contigue: indirizzo(i) = base + i·dimensione_cella. Si assume che l'aritmetica degli indirizzi richieda tempo costante.

Qual è la condizione di bilanciamento AVL?

A ogni nodo, altezza(sinistra) − altezza(destra) ∈ {−1, 0, 1}. Vale anche l'invariante d'ordine del BST.

Confronta inserimento in testa e accesso per indice in una lista concatenata semplice e in un array dinamico.

Lista: inserimento in testa O(1), accesso per indice O(n). Array: inserimento in testa O(n), accesso per indice O(1); inserire in testa sposta gli elementi.

Come risolve le collisioni hash il concatenamento separato?

Ogni bucket contiene una raccolta di voci con quell'indice, spesso una lista concatenata. Chiavi diverse nello stesso bucket restano voci distinte.

Quali sono i costi attesi e nel caso peggiore di una tabella hash con concatenamento separato?

Con carico limitato, hash ben distribuiti e operazioni sulle chiavi a costo costante, ricerca ed eliminazione costano O(1) atteso. Con crescita geometrica, l'inserimento costa O(1) ammortizzato atteso. Una catena di n chiavi in collisione può causare O(n).

Come differiscono scansione lineare e quadratica nell'indirizzamento aperto?

Le voci restano nell'array. Con dimensione m e indice iniziale h, si provano rispettivamente (h+i) mod m e (h+c₁i+c₂i²) mod m. La scansione quadratica richiede parametri adatti.

Come si corregge uno sbilanciamento sinistra-destra dopo un inserimento AVL?

Prima si ruota il figlio sinistro verso sinistra, poi il nodo sbilanciato verso destra.

Quali regole sui colori mantengono bilanciato un BST rosso-nero?

I nodi sono rossi o neri; radice e foglie NIL sono nere. Un nodo rosso non ha figli rossi. Tutti i cammini da un nodo a una foglia NIL discendente contengono lo stesso numero di nodi neri. Ciò limita l'altezza a O(log n).

Cos'è il fattore di carico di una tabella hash e perché può essere ridimensionata?

α = n/m: n voci memorizzate e m bucket o celle. Superare la soglia dell'implementazione può causare un ampliamento e un nuovo hashing; 0,75 non è universale.

Come funziona una pila e quando le sue operazioni costano O(1)?

LIFO: l'ultimo elemento inserito viene estratto per primo. In testa a una lista concatenata, inserimento, estrazione e lettura della cima costano O(1); ridimensionare un array può rendere un inserimento O(n).

Quale invariante d'ordine definisce un albero binario di ricerca (BST) con chiavi distinte?

A ogni nodo, tutte le chiavi del sottoalbero sinistro sono minori e tutte quelle del destro maggiori. La regola vale ricorsivamente.

Quali due proprietà definiscono un min-heap binario?

È un albero binario completo e la chiave di ogni genitore non supera quelle dei figli. La radice contiene quindi un minimo.

Quanto costano inserimento, rimozione della radice e lettura della radice in un heap binario?

Rispettivamente O(log n), O(log n) e O(1), se non occorre ridimensionare l'array. Un ridimensionamento può costare O(n).

Cos'è un trie e quando costa O(L) cercare una chiave di L caratteri?

È un albero di prefissi che memorizza chiavi lungo cammini di caratteri, con marcatori di chiave completa. La ricerca costa O(L) se ogni transizione al carattere successivo costa O(1).

Cosa produce la visita inordine di un BST con chiavi distinte?

Tutte le chiavi in ordine strettamente crescente, visitando n nodi in O(n).

Strutture Dati, Analisi di Complessità (Big-O) e Algoritmi Fondamentali

Ripasso universitario che richiede basi di programmazione: 32 schede su array, liste, hashing, alberi, heap, trie, Union–Find, filtri di Bloom e complessità.

Level: basic
Languages: it → it
Cards: 32
Markdown: Strutture Dati, Analisi di Complessità (Big-O) e Algoritmi Fondamentali (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Qual è il costo ammortizzato di union/find con compressione dei cammini e unione per rango?	O(α(n)) per operazione: α è l'inversa di Ackermann e n il numero di elementi. L'inizializzazione costa O(n); il limite riguarda una sequenza, non un costo costante nel caso peggiore di ogni chiamata.
2	Quali proprietà deve avere una funzione hash per la ricerca in tabella?	Deve essere deterministica e distribuire bene le chiavi attese. Calcolare l'hash di chiavi di dimensione fissa può costare O(1); quello di una nuova stringa di L caratteri costa in genere O(L).
3	Perché una lista doppiamente concatenata può eliminare un nodo dato in O(1)?	I collegamenti al precedente e al successivo permettono di ricollegare direttamente i vicini. Si aggiornano testa e coda se necessario, senza cercare il predecessore.
4	Come evita gli spostamenti una coda in un array circolare dopo un'estrazione?	Gli indici di testa e coda avanzano modulo la capacità. L'estrazione avanza la testa, consentendo di riutilizzare le celle libere senza spostare gli altri elementi.
5	Dove sono genitore e figli del nodo i in un array heap di lunghezza n indicizzato da zero?	Genitore: ⌊(i−1)/2⌋ per i>0. Figli: 2i+1 e 2i+2, solo se tali indici sono minori di n. L'indice 0 non ha genitore.
6	Che differenza c'è tra O, Ω e Θ?	Indicano rispettivamente un limite asintotico superiore, inferiore e stretto. Descrivono una specifica funzione di costo; O non significa di per sé «caso peggiore».
7	Quali sono l'ordine di accesso e i costi tipici delle operazioni di una coda?	FIFO: inserimento in fondo, estrazione dalla testa. Entrambi costano O(1) con collegamenti a testa e coda o un buffer circolare di capacità fissa; spostare un array rende l'estrazione O(n).
8	Come differiscono compressione dei cammini, unione per rango e unione per dimensione?	La compressione reindirizza alla radice i nodi visitati. Per rango, la radice di rango minore va sotto quella di rango maggiore; per dimensione, l'insieme più piccolo sotto il più grande. Il rango può differire dall'altezza corrente.
9	Cosa fanno find e union in una struttura di insiemi disgiunti?	find(x) restituisce il rappresentante dell'insieme di x. union(x,y) unisce i loro insiemi se sono diversi; se coincidono già, la partizione non cambia.
10	Come visita un albero binario la visita per livelli?	Una coda FIFO permette di visitare un livello di profondità alla volta. Accodare il figlio sinistro prima del destro dà l'ordine da sinistra a destra.
11	Quali sono gli ordini delle visite in preordine, inordine e postordine di un albero binario?	Preordine: nodo → sinistra → destra. Inordine: sinistra → nodo → destra. Postordine: sinistra → destra → nodo.
12	Raddoppiando la capacità, qual è il costo ammortizzato di un inserimento in fondo a un array dinamico?	O(1) per inserimento. Un ridimensionamento può costare O(n), ma n inserimenti in fondo a partire da un array vuoto costano complessivamente O(n).
13	Per funzioni non negative f e g, cosa significa f(n) ∈ O(g(n))?	Esistono costanti c > 0 e n₀ ≥ 0 tali che f(n) ≤ c·g(n) per ogni n ≥ n₀.
14	Quali risposte può dare un filtro di Bloom che consente solo inserimenti?	Un risultato negativo indica che l'elemento non è stato inserito; uno positivo che potrebbe esserlo stato. Gli hash impostano bit in un array: sono possibili falsi positivi, ma non falsi negativi se lo stato è intatto.
15	Come dipendono dall'altezza h ricerca, inserimento ed eliminazione in un BST?	Costano O(h). Un albero bilanciato ha h = O(log n), una catena h = O(n). Il costo atteso O(log n) richiede ipotesi come un ordine casuale di inserimento.
16	Quanto costa costruire un heap dal basso verso l'alto a partire da n elementi?	O(n). La maggioranza dei nodi è vicina alle foglie e richiede poche discese; sommando il lavoro per altezza del nodo si ottiene un totale lineare.
17	Ordina queste crescite dalla più lenta alla più rapida per n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.	Asintoticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!.
18	Perché l'accesso per indice in un array di dimensione fissa costa O(1)?	Le celle, di uguale dimensione, sono contigue: indirizzo(i) = base + i·dimensione_cella. Si assume che l'aritmetica degli indirizzi richieda tempo costante.
19	Qual è la condizione di bilanciamento AVL?	A ogni nodo, altezza(sinistra) − altezza(destra) ∈ {−1, 0, 1}. Vale anche l'invariante d'ordine del BST.
20	Confronta inserimento in testa e accesso per indice in una lista concatenata semplice e in un array dinamico.	Lista: inserimento in testa O(1), accesso per indice O(n). Array: inserimento in testa O(n), accesso per indice O(1); inserire in testa sposta gli elementi.
21	Come risolve le collisioni hash il concatenamento separato?	Ogni bucket contiene una raccolta di voci con quell'indice, spesso una lista concatenata. Chiavi diverse nello stesso bucket restano voci distinte.
22	Quali sono i costi attesi e nel caso peggiore di una tabella hash con concatenamento separato?	Con carico limitato, hash ben distribuiti e operazioni sulle chiavi a costo costante, ricerca ed eliminazione costano O(1) atteso. Con crescita geometrica, l'inserimento costa O(1) ammortizzato atteso. Una catena di n chiavi in collisione può causare O(n).
23	Come differiscono scansione lineare e quadratica nell'indirizzamento aperto?	Le voci restano nell'array. Con dimensione m e indice iniziale h, si provano rispettivamente (h+i) mod m e (h+c₁i+c₂i²) mod m. La scansione quadratica richiede parametri adatti.
24	Come si corregge uno sbilanciamento sinistra-destra dopo un inserimento AVL?	Prima si ruota il figlio sinistro verso sinistra, poi il nodo sbilanciato verso destra.
25	Quali regole sui colori mantengono bilanciato un BST rosso-nero?	I nodi sono rossi o neri; radice e foglie NIL sono nere. Un nodo rosso non ha figli rossi. Tutti i cammini da un nodo a una foglia NIL discendente contengono lo stesso numero di nodi neri. Ciò limita l'altezza a O(log n).
26	Cos'è il fattore di carico di una tabella hash e perché può essere ridimensionata?	α = n/m: n voci memorizzate e m bucket o celle. Superare la soglia dell'implementazione può causare un ampliamento e un nuovo hashing; 0,75 non è universale.
27	Come funziona una pila e quando le sue operazioni costano O(1)?	LIFO: l'ultimo elemento inserito viene estratto per primo. In testa a una lista concatenata, inserimento, estrazione e lettura della cima costano O(1); ridimensionare un array può rendere un inserimento O(n).
28	Quale invariante d'ordine definisce un albero binario di ricerca (BST) con chiavi distinte?	A ogni nodo, tutte le chiavi del sottoalbero sinistro sono minori e tutte quelle del destro maggiori. La regola vale ricorsivamente.
29	Quali due proprietà definiscono un min-heap binario?	È un albero binario completo e la chiave di ogni genitore non supera quelle dei figli. La radice contiene quindi un minimo.
30	Quanto costano inserimento, rimozione della radice e lettura della radice in un heap binario?	Rispettivamente O(log n), O(log n) e O(1), se non occorre ridimensionare l'array. Un ridimensionamento può costare O(n).
31	Cos'è un trie e quando costa O(L) cercare una chiave di L caratteri?	È un albero di prefissi che memorizza chiavi lungo cammini di caratteri, con marcatori di chiave completa. La ricerca costa O(L) se ogni transizione al carattere successivo costa O(1).
32	Cosa produce la visita inordine di un BST con chiavi distinte?	Tutte le chiavi in ordine strettamente crescente, visitando n nodi in O(n).