Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cos'è una foglia?

1. AUn nodo con esattamente un figlio
2. BUn nodo senza figli
3. CIl nodo con il valore più grande
4. DUn nodo senza genitore

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

1. AIl numero di vertici del grafo
2. BLa sua posizione nella lista di adiacenza
3. CIl numero di archi a esso collegati
4. DLa lunghezza del cammino più lungo che parte da esso

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

1. ACoda (queue)
2. BTabella hash
3. CLista concatenata
4. DPila (stack)

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), indipendentemente da quante parole sono memorizzate
3. CO(log n), dove n è il numero di parole
4. DO(L × n)

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. A2^h
2. B2h + 1
3. Ch²
4. D2^h+1 − 1

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(1)
2. BO(log n)
3. CO(n)
4. DO(n²)

In che modo un radix tree (trie compresso) migliora un trie semplice?

1. AFonde le catene di nodi con un solo figlio in un unico arco etichettato con una stringa
2. BMemorizza ogni parola in una tabella hash alla radice invece che in nodi separati
3. CConserva solo la prima lettera di ogni parola
4. DOrdina i figli di ogni nodo per frequenza

L'algoritmo di Kahn per l'ordinamento topologico rimuove ripetutamente i vertici con grado entrante 0. Quale struttura contiene questi vertici?

1. AUn max-heap ordinato per grado uscente
2. BUna pila di tutti gli archi visitati
3. CUna coda (o una collezione qualsiasi) dei vertici con grado entrante 0
4. DUna matrice di adiacenza che registra quali vertici sono già stati rimossi