Scheda di esercizi di Strutture dati con soluzioni

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BIl numero di archi a esso collegati
3. CLa lunghezza del cammino più lungo che parte da esso
4. DIl numero di vertici del grafo

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

1. AUna riga di V valori booleani
2. BUna lista dei suoi vertici adiacenti
3. CIl numero totale di archi del grafo
4. DIl cammino minimo verso ogni altro vertice

Che cosa definisce un albero binario?

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

Come si inserisce un nuovo elemento in un heap binario?

1. ALo si pone nella radice e lo si fa scendere
2. BSi ricostruisce da zero l'intero heap
3. CLo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
4. DLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi

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 + E)
4. DO(V²)

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel suo figlio destro, sempre
2. BNel nodo più a sinistra del suo sottoalbero destro
3. CNel suo genitore, sempre
4. DNel nodo più a destra del suo sottoalbero sinistro

Quanto tempo serve per cercare una chiave arbitraria in un min-heap binario di n elementi?

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

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

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