Scheda di esercizi di Strutture dati con soluzioni

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

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

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUno stack
2. BUn heap
3. CUna stringa
4. DUna lista concatenata semplice non ordinata

Che cos'è un grafo orientato?

1. AUn grafo i cui archi hanno tutti un peso
2. BUn grafo in cui ogni coppia di vertici distinti è collegata da un arco
3. CUn grafo i cui archi hanno una direzione da un vertice a un altro
4. DUn grafo privo di cicli

Qual è il valore dell'espressione postfissa 3 4 + 2 * ?

1. A10
2. B14
3. C11
4. D24

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUn albero binario di ricerca bilanciato
2. BUna lista concatenata non ordinata
3. CUna pila
4. DUna tabella hash

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

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

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. BConserva solo la prima lettera di ogni parola
3. CMemorizza ogni parola in una tabella hash alla radice invece che in nodi separati
4. DOrdina i figli di ogni nodo per frequenza

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

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