Scheda di esercizi di Strutture dati con soluzioni

Quanti archi ha un albero con n nodi?

1. An − 1
2. B2n
3. Cn + 1
4. Dn

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

1. AHeap
2. BPila (stack)
3. CAlbero binario
4. DCoda (queue)

Che cosa memorizza una mappa (dizionario)?

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

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

1. A2i + 1 e 2i + 2
2. B2i e 2i + 1
3. Ci + 1 e i + 2
4. Di/2 e i/2 + 1

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

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

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L × n)
2. BO(L), indipendentemente da quante parole sono memorizzate
3. CO(log n), dove n è il numero di parole
4. DO(n), dove n è il numero di parole

Qual è il tempo di esecuzione della visita in ampiezza (BFS) su un grafo con V vertici memorizzato come matrice di adiacenza?

1. AO(V²)
2. BO(E log V)
3. CO(V)
4. DO(V + E)

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

1. ARicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi
2. BRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti
3. CMemorizza le chiavi senza ordine
4. DNon usa memoria aggiuntiva