Scheda di esercizi di Strutture dati con soluzioni

Che cos'è la radice di un albero?

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

In un grafo, che cos'è un ciclo?

1. AUn vertice senza archi
2. BUn cammino che inizia e finisce nello stesso vertice
3. CUn cammino che visita ogni vertice
4. DUn arco di peso zero

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. AAccedere all'elemento di indice i
2. BInserire in testa
3. CRimuovere l'elemento in testa
4. DLeggere il primo elemento

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. AConcatenamento separato (separate chaining)
2. BScansione quadratica (quadratic probing)
3. CScansione lineare (linear probing)
4. DDoppio hashing (double hashing)

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 preordine?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 3 4 5

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. AUna tabella hash
2. BUna pila
3. CUna lista concatenata non ordinata
4. DUn albero binario di ricerca bilanciato

In un buffer circolare, front == rear può significare sia vuoto sia pieno. Qual è un modo comune per distinguere i due casi?

1. ARendere la dimensione del buffer una potenza di due
2. BSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto
3. CMemorizzare front e rear nella stessa variabile
4. DMantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata

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

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