Scheda di esercizi di Strutture dati con soluzioni

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

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

Che cosa definisce un albero binario?

1. AOgni nodo ha al massimo due figli
2. BOgni nodo ha esattamente due figli
3. CL'albero ha esattamente due livelli
4. DOgni nodo memorizza un numero binario

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e un indice
2. BDati e riferimenti a tutti gli altri nodi
3. CDati e un riferimento al nodo successivo
4. DSolo dati

Che cosa è vero per la matrice di adiacenza di un grafo non orientato?

1. ALa sua diagonale principale contiene sempre degli uno
2. BÈ simmetrica rispetto alla diagonale principale
3. COgni riga contiene esattamente un 1
4. DÈ sempre triangolare superiore

Quanta memoria usa una lista di adiacenza per un grafo con V vertici ed E archi?

1. AO(V × E)
2. BO(E²)
3. CO(V²)
4. DO(V + E)

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

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

Perché i B-alberi (B-tree) sono usati nei database e nei file system?

1. AMemorizzano i dati in modo non ordinato
2. BIl loro elevato fattore di ramificazione mantiene l'albero poco profondo, riducendo le lente letture da disco
3. CUsano meno memoria di qualsiasi array, quindi l'intero indice sta sempre nella memoria centrale
4. DNon richiedono ribilanciamento