Scheda di esercizi di Strutture dati con soluzioni

Che cos'è una deque (coda a doppia estremità)?

1. ADue code separate che condividono un array
2. BUna struttura che permette inserimenti e rimozioni a entrambe le estremità
3. CUna coda che permette rimozioni solo in fondo
4. DUna coda ordinata per priorità

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di collisioni avvenute finora
2. BIl numero di elementi memorizzati diviso per il numero di bucket
3. CIl tempo necessario per caricare la tabella dal disco
4. DIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate

Una tabella hash memorizza i dati come:

1. AUna stringa di lunghezza fissa
2. BUn albero con chiavi ordinate
3. CSolo una lista ordinata
4. DCoppie chiave–valore individuate da una funzione hash

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(1), perché l'indice è noto
2. BO(log n), per via della ricerca binaria
3. CO(n), perché gli elementi successivi devono essere spostati
4. DO(n²), perché ogni elemento si sposta n volte

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L × n)
2. BO(n), dove n è il numero di parole
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(log n), dove n è il numero di parole

Quale tipo di dato astratto usa l'algoritmo di Dijkstra per scegliere il prossimo vertice da elaborare?

1. AUn insieme senza ordinamento
2. BUna coda con priorità di minimo
3. CUna coda FIFO
4. DUna pila

Un segment tree (albero dei segmenti) è tipicamente usato per:

1. ARispondere a interrogazioni su intervalli (come somme su intervalli) e aggiornamenti in O(log n)
2. BMemorizzare gli archi di un grafo
3. CImplementare uno stack
4. DOrdinare stringhe alfabeticamente memorizzando ogni prefisso in un nodo separato dell'albero

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

1. AL'altezza è esattamente log₂ n
2. BL'altezza è al massimo log₂ n + 1
3. CL'altezza è al massimo 2 log₂(n + 1)
4. DL'altezza è al massimo n / 2