Scheda di esercizi di Strutture dati con soluzioni

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

1. AIl cammino minimo verso ogni altro vertice
2. BUna riga di V valori booleani
3. CUna lista dei suoi vertici adiacenti
4. DIl numero totale di archi del grafo

Che cos'è la radice di un albero?

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

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

1. AAlbero binario
2. BPila (stack)
3. CHeap
4. DCoda (queue)

Perché in pratica percorrere un array è spesso molto più veloce che percorrere una lista concatenata della stessa lunghezza?

1. AGli elementi dell'array sono contigui, quindi sfruttano bene la cache della CPU
2. BLa visita di un array è O(1) in totale, mentre quella di una lista concatenata è O(n)
3. CGli array usano meno istruzioni per confrontare i valori
4. DLe liste concatenate memorizzano sempre gli elementi su disco

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

Un trie (albero dei prefissi) è particolarmente efficiente per:

1. ARicerche per prefisso, come il completamento automatico
2. BMemorizzare matrici
3. COrdinare numeri
4. DTrovare cammini minimi

Che cosa fa uno splay tree dopo ogni accesso?

1. ARicostruisce l'intero albero in forma bilanciata
2. BPorta con rotazioni il nodo acceduto fino alla radice
3. CSposta il nodo acceduto in una foglia
4. DRicolora i nodi lungo il cammino di ricerca

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

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