Scheda di esercizi di Strutture dati con soluzioni

Quale operazione è lenta in un array ma veloce in testa a una lista concatenata?

1. AOttenere la lunghezza di un array di dimensione fissa
2. BAccedere al 5° elemento
3. CInserire all'inizio
4. DLeggere l'ultimo elemento tramite indice

In un albero, che cosa sono i nodi fratelli?

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

Quanti archi ha un albero con n nodi?

1. An − 1
2. Bn + 1
3. Cn
4. D2n

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. A√n
2. Blog₂ n
3. Cn (diventa una lista concatenata)
4. D1

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(1), perché l'indice è noto
2. BO(n), perché gli elementi successivi devono essere spostati
3. CO(n²), perché ogni elemento si sposta n volte
4. DO(log n), per via della ricerca binaria

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUna lista concatenata non ordinata
2. BUn albero binario di ricerca bilanciato
3. CUna pila
4. DUna tabella hash

Come si può rilevare se una lista concatenata semplice contiene un ciclo usando O(1) memoria aggiuntiva?

1. ASi ordina la lista e si cercano i duplicati
2. BSi memorizza ogni nodo visitato in un hash set
3. CSi contano i nodi finché il conteggio supera il campo lunghezza della lista
4. DSi muove un puntatore di un passo e un altro di due passi e si verifica se si incontrano

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

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