Scheda di esercizi di Strutture dati con soluzioni

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AUguali al valore del nodo
2. BIn ordine casuale
3. CMinori del valore del nodo
4. DMaggiori del valore del nodo

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANella radice
2. BNell'ultima posizione dell'array
3. CIn una foglia qualsiasi, da cercare
4. DNella foglia più a sinistra

Che cos'è la radice di un albero?

1. AUn nodo senza figli
2. BIl nodo più in alto, privo di genitore
3. CIl nodo con il valore più grande
4. DUn qualsiasi nodo intermedio

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. AUn unico array ordinato di vertici
2. BUn heap binario di archi
3. CLista di adiacenza
4. DMatrice di adiacenza

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUna funzione hash
2. BUn albero binario di ricerca
3. CUna coda di dimensione fissa
4. DUna visita di un grafo

Quanta memoria utilizza una matrice di adiacenza per un grafo con V vertici?

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

Nell'algoritmo di Kruskal per l'albero ricoprente minimo, a che cosa serve la struttura union-find?

1. AA memorizzare la distanza corrente di ogni vertice dalla sorgente durante la visita
2. BA ordinare gli archi per peso
3. CA verificare se i due estremi di un arco sono già collegati
4. DA scegliere il vertice di partenza

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

1. AO(α(n)), l'inversa della funzione di Ackermann, praticamente costante
2. BO(n²)
3. CEsattamente O(log n)
4. DO(n)