Scheda di esercizi di Strutture dati con soluzioni

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AIl cammino minimo verso ogni altro vertice
2. BIl numero totale di archi del grafo
3. CUna lista dei suoi vertici adiacenti
4. DUna riga di V valori booleani

Quale struttura dati funziona secondo il principio «primo a entrare, primo a uscire» (FIFO)?

1. ACoda (queue)
2. BPila (stack)
3. CHeap
4. DAlbero binario

La profondità di un nodo in un albero è:

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

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

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

Una coda è implementata con due pile: push su una pila «in» e pop da una pila «out», che viene riempita da «in» quando è vuota. Qual è il costo ammortizzato per operazione?

1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

Perché i database usano spesso B+-alberi anziché semplici B-alberi per gli indici?

1. AI B+-alberi usano nodi interni binari, il che riduce le letture da disco
2. BI B+-alberi memorizzano i dati solo nella radice
3. CTutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
4. DI B+-alberi non devono essere bilanciati

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

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