Scheda di esercizi di Strutture dati con soluzioni

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

1. ADati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo
2. BDati e soltanto un puntatore al nodo successivo
3. CDati, un puntatore al nodo successivo e un puntatore al nodo precedente
4. DDue copie dei dati e un solo puntatore

Qual è la differenza principale tra un array statico e un array dinamico?

1. AUn array dinamico può crescere spostandosi in un blocco di memoria più grande
2. BUn array statico può memorizzare solo numeri
3. CUn array statico permette un accesso per indice più lento
4. DUn array dinamico memorizza gli elementi in nodi collegati così può crescere un elemento alla volta

Che cosa definisce un albero binario?

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

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. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 2 5 1 3
4. D4 5 2 3 1

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

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

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

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

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

Un albero di Fenwick (binary indexed tree) su un array di n numeri supporta quali operazioni in O(log n)?

1. AOrdinamento dell'array e ricerca binaria
2. BInterrogazioni di somme prefisse e aggiornamenti di singoli elementi
3. CInserimento di elementi in qualsiasi posizione
4. DRicerca della mediana in O(1)