Scheda di esercizi di Strutture dati con soluzioni

Qual è la differenza principale tra un array statico e un array dinamico?

1. AUn array dinamico può crescere spostandosi in un blocco di memoria più grande
2. BUn array statico permette un accesso per indice più lento
3. CUn array dinamico memorizza gli elementi in nodi collegati così può crescere un elemento alla volta
4. DUn array statico può memorizzare solo numeri

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

1. AUn heap
2. BUna lista concatenata semplice non ordinata
3. CUna stringa
4. DUno stack

Che cos'è la radice di un albero?

1. AIl nodo più in alto, privo di genitore
2. BUn qualsiasi nodo intermedio
3. CUn nodo senza figli
4. DIl nodo con il valore più grande

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. A4 2 5 1 3
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D5 4 3 2 1

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

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. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D1 2 3 4 5

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

Quale struttura dati permette una cache LRU (least recently used) con get e put in O(1)?

1. ASolo un albero binario di ricerca
2. BSolo uno stack
3. CUna hash map combinata con una lista doppiamente concatenata
4. DUn singolo array ordinato