Scheda di esercizi di Strutture dati con soluzioni

La profondità di un nodo in un albero è:

1. AIl numero di archi dalla radice a quel nodo
2. BIl numero di archi da quel nodo alla foglia più profonda
3. CIl numero di nodi del suo sottoalbero
4. DIl numero di figli di quel nodo

In un grafo, che cos'è un ciclo?

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

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

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

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. AUn albero binario di ricerca di frame
2. BLa coda della memoria heap
3. CLo stack delle chiamate
4. DUna tabella hash di funzioni

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

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 pila
2. BUna tabella hash
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. AMantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata
2. BSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto
3. CRendere la dimensione del buffer una potenza di due
4. DMemorizzare front e rear nella stessa variabile

Senza unione per rango né compressione dei cammini, qual è il costo nel caso peggiore di una singola find in una struttura union-find con n elementi?

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