Scheda di esercizi di Strutture dati con soluzioni

Che cosa definisce un albero binario?

1. AOgni nodo ha al massimo due figli
2. BL'albero ha esattamente due livelli
3. COgni nodo ha esattamente due figli
4. DOgni nodo memorizza un numero binario

Che cos'è una deque (coda a doppia estremità)?

1. ADue code separate che condividono un array
2. BUna coda ordinata per priorità
3. CUna struttura che permette inserimenti e rimozioni a entrambe le estremità
4. DUna coda che permette rimozioni solo in fondo

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna lista dei suoi vertici adiacenti
2. BIl numero totale di archi del grafo
3. CIl cammino minimo verso ogni altro vertice
4. DUna riga di V valori booleani

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

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

Qual è il valore dell'espressione postfissa 3 4 + 2 * ?

1. A11
2. B10
3. C14
4. D24

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

1. AO(log n)
2. BO(1)
3. CO(n log n)
4. DO(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 max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
2. BUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli
3. CUn array ordinato di tutti gli n valori
4. DUna coda FIFO degli ultimi k valori

Un array dinamico raddoppia quando è pieno. Perché molte implementazioni lo riducono solo quando è pieno per un quarto, e non per metà?

1. APer mantenere l'array ordinato
2. BPerché dimezzare a metà farebbe perdere elementi
3. CPerché l'allocatore di memoria può liberare memoria solo a quarti di blocco
4. DPer evitare ridimensionamenti ripetuti quando push e pop si alternano vicino alla soglia