Scheda di esercizi di Strutture dati con soluzioni

Come sono memorizzati in memoria gli elementi di un array?

1. AIn un unico blocco contiguo, uno dopo l'altro
2. BIn posizioni casuali scelte da un hash
3. CSparsi, collegati da puntatori
4. DIn un albero di pagine di memoria

La profondità di un nodo in un albero è:

1. AIl numero di figli di quel nodo
2. BIl numero di archi da quel nodo alla foglia più profonda
3. CIl numero di nodi del suo sottoalbero
4. DIl numero di archi dalla radice a quel nodo

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUno stack
2. BUna stringa
3. CUna lista concatenata semplice non ordinata
4. DUn heap

Quanto tempo serve per verificare se l'arco (u, v) esiste usando una matrice di adiacenza?

1. AO(E)
2. BO(V)
3. CO(1)
4. DO(log V)

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. ANon c'è un massimo
2. B0,5
3. C2
4. D1

Un trie (albero dei prefissi) è particolarmente efficiente per:

1. AOrdinare numeri
2. BTrovare cammini minimi
3. CMemorizzare matrici
4. DRicerche per prefisso, come il completamento automatico

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

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

Perché in un filtro di Bloom standard non si possono semplicemente eliminare gli elementi azzerandone i bit?

1. AL'eliminazione porterebbe il tasso di falsi positivi al 100%
2. BI bit di un filtro di Bloom non si possono modificare dopo la creazione
3. CI filtri di Bloom memorizzano gli elementi completi, che una volta sottoposti a hash non si possono più ritrovare
4. DQuei bit possono appartenere anche ad altri elementi, il che causerebbe falsi negativi