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. BUna lista dei suoi vertici adiacenti
3. CIl numero totale di archi del grafo
4. DUna riga di V valori booleani

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

1. AAlbero binario
2. BHeap
3. CCoda (queue)
4. DPila (stack)

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. AInsert
2. BDequeue
3. CPush
4. DEnqueue

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

Come si trova la chiave minima in un albero binario di ricerca?

1. ASi visitano tutte le foglie e le si confronta
2. BSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
3. CSi guarda solo la radice
4. DSi seguono i figli destri dalla radice finché non c'è più un figlio destro

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. AUn heap
2. BSolo una tabella hash
3. CUna coda
4. DUno stack

Quali sono i costi in tempo e in spazio aggiuntivo dell'inversione sul posto di una lista concatenata semplice?

1. ATempo O(n) e spazio aggiuntivo O(n)
2. BTempo O(1) e spazio aggiuntivo O(1)
3. CTempo O(n log n) e spazio aggiuntivo O(1)
4. DTempo O(n) e spazio aggiuntivo O(1)

Quale coppia di visite determina sempre un unico albero binario con chiavi distinte?

1. AIl solo preordine
2. BPreordine e postordine
3. CLa sola visita per livelli
4. DPreordine e ordine simmetrico (inorder)