# 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à. - **Canonical URL:** https://flashcards.world/flashcards/sets/f976bb34-9bbe-4e1c-acea-0c6d4acd15b9/ - **Markdown URL:** https://flashcards.world/flashcards/sets/f976bb34-9bbe-4e1c-acea-0c6d4acd15b9.md - **Level:** basic - **Languages:** it → it - **Total Cards:** 32 ## Flashcards (32 Cards) | # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options | | :--- | :--- | :--- | :--- | :--- | | 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). | | | --- Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/f976bb34-9bbe-4e1c-acea-0c6d4acd15b9/).