Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cosa sono i nodi fratelli?

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

La profondità di un nodo in un albero è:

1. AIl numero di figli di quel nodo
2. BIl numero di nodi del suo sottoalbero
3. CIl numero di archi da quel nodo alla foglia più profonda
4. DIl numero di archi dalla radice a quel nodo

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. ALeggere il primo elemento
2. BInserire in testa
3. CRimuovere l'elemento in testa
4. DAccedere all'elemento di indice i

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

1. ATrovare cammini minimi
2. BOrdinare numeri
3. CMemorizzare matrici
4. DRicerche per prefisso, come il completamento automatico

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

1. ALe liste concatenate memorizzano sempre gli elementi su disco
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. DGli elementi dell'array sono contigui, quindi sfruttano bene la cache della CPU

In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

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

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

Un oggetto è memorizzato come chiave in una hash map, e poi viene modificato un campo usato dalla sua funzione hash. Qual è il risultato probabile?

1. ALa mappa solleva un errore nel momento in cui il campo cambia
2. BNon cambia nulla, perché l'hash di una chiave si calcola una sola volta all'avvio del programma
3. CLa mappa sposta automaticamente la chiave nel nuovo bucket
4. DLa ricerca dell'oggetto può fallire perché si trova nel bucket corrispondente al vecchio hash