Scheda di esercizi di Strutture dati con soluzioni

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

1. AUn heap
2. BUna lista concatenata semplice non ordinata
3. CUno stack
4. DUna stringa

In un albero, che cosa sono i nodi fratelli?

1. AUn nodo e il suo genitore
2. BNodi che hanno lo stesso genitore
3. CNodi alla stessa profondità in sottoalberi diversi
4. DNodi privi di figli

Che cosa fa l'operazione peek (o top) su una pila?

1. ARestituisce l'elemento in fondo alla pila
2. BRimuove tutti gli elementi dalla pila
3. CRimuove l'elemento in cima e lo restituisce
4. DRestituisce l'elemento in cima senza rimuoverlo

Come funziona extract-min in un min-heap binario?

1. ASi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra
2. BSi rimuove l'ultimo elemento dell'array
3. CSi cercano in tutte le foglie il nuovo minimo
4. DSi sposta l'ultimo elemento nella radice e lo si fa scendere

A che cosa serve un nodo sentinella (fittizio) in una lista concatenata?

1. AA memorizzare il numero di elementi
2. BA impedire che la lista cresca oltre un numero massimo fisso di nodi
3. CA semplificare il codice eliminando i casi particolari in testa o in coda
4. DA rendere la lista ordinata

Quanta memoria usa una lista di adiacenza per un grafo con V vertici ed E archi?

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

Perché i database usano spesso B+-alberi anziché semplici B-alberi per gli indici?

1. AI B+-alberi memorizzano i dati solo nella radice
2. BTutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
3. CI B+-alberi usano nodi interni binari, il che riduce le letture da disco
4. DI B+-alberi non devono essere bilanciati

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

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