Scheda di esercizi di Strutture dati con soluzioni

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

1. AIl numero di nodi della lista
2. BL'indirizzo del primo nodo
3. CNull (nessun nodo)
4. DL'indirizzo del nodo precedente

Che cos'è la proprietà di max-heap?

1. ALa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro
2. BLa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli
3. CTutte le foglie contengono la chiave massima
4. DLe chiavi sono ordinate da sinistra a destra

In un albero, che cosa sono i nodi fratelli?

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

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice i − 1
2. BAll'indice 2i + 1
3. CAll'indice ⌊i / 2⌋ + 1
4. DAll'indice ⌊(i − 1) / 2⌋

Come si inserisce un nuovo elemento in un heap binario?

1. ALo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
2. BLo si pone nella radice e lo si fa scendere
3. CSi ricostruisce da zero l'intero heap
4. DLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi

Perché un heap binario si può memorizzare in un array senza puntatori?

1. AGli heap non contengono mai più di 100 elementi
2. BTutte le chiavi di un heap sono uguali
3. CGli array mantengono automaticamente le chiavi in ordine, quindi non servono puntatori
4. DÈ un albero binario completo, quindi le posizioni seguono semplici formule sugli indici

Quale coppia di visite determina sempre un unico albero binario con chiavi distinte?

1. APreordine e postordine
2. BPreordine e ordine simmetrico (inorder)
3. CIl solo preordine
4. DLa sola visita per livelli

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. AUna coda FIFO degli ultimi k valori
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. DUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo