Scheda di esercizi di Strutture dati con soluzioni

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

1. APush
2. BDequeue
3. CInsert
4. DEnqueue

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ASottoalbero destro, poi nodo, poi sottoalbero sinistro
2. BSottoalbero sinistro, poi nodo, poi sottoalbero destro
3. CNodo, poi sottoalbero sinistro, poi sottoalbero destro
4. DSottoalbero sinistro, poi sottoalbero destro, poi nodo

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

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

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. C4 5 2 3 1
4. D5 4 3 2 1

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(n), dove n è il numero di parole
2. BO(L × n)
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(log n), dove n è il numero di parole

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(n²)
4. DO(1)

Quale proprietà deve soddisfare un albero rosso-nero?

1. AOgni nodo rosso deve avere figli rossi, quindi i nodi rossi formano sempre catene ininterrotte fino alle foglie
2. BLa radice deve essere rossa
3. COgni cammino da un nodo alle sue foglie discendenti contiene lo stesso numero di nodi neri
4. DOgni nodo deve essere rosso

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

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