Scheda di esercizi di Strutture dati con soluzioni

Quanti archi ha un albero con n nodi?

1. A2n
2. Bn − 1
3. Cn + 1
4. Dn

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

1. ALista concatenata
2. BPila (stack)
3. CCoda (queue)
4. DTabella hash

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BValori ordinati per grandezza
3. CCoppie di chiavi uguali
4. DCoppie chiave–valore con chiavi univoche

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine per livelli
2. BOrdine crescente
3. COrdine sempre decrescente
4. DOrdine di inserimento

Che cosa è vero per la matrice di adiacenza di un grafo non orientato?

1. AÈ simmetrica rispetto alla diagonale principale
2. BOgni riga contiene esattamente un 1
3. CLa sua diagonale principale contiene sempre degli uno
4. DÈ sempre triangolare superiore

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. ALista di adiacenza
2. BUn heap binario di archi
3. CMatrice di adiacenza
4. DUn unico array ordinato di vertici

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

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

1. AUn array ordinato di tutti gli n valori
2. BUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
3. CUna coda FIFO degli ultimi k valori
4. DUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli