Scheda di esercizi di Strutture dati con soluzioni

Qual è la caratteristica distintiva di un insieme (set) come tipo di dato astratto?

1. AMemorizza elementi senza duplicati
2. BPermette l'accesso solo a un'estremità
3. CMemorizza coppie chiave–valore
4. DMemorizza elementi in ordine

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANella foglia più a sinistra
2. BIn una foglia qualsiasi, da cercare
3. CNella radice
4. DNell'ultima posizione dell'array

Che cosa definisce un albero binario?

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

Quale struttura dati si usa per verificare se le parentesi in "{[()]}" sono bilanciate?

1. AUna pila
2. BUn albero binario di ricerca
3. CUna coda
4. DUna tabella hash

A che cosa serve un nodo sentinella (fittizio) in una lista concatenata?

1. AA rendere la lista ordinata
2. BA memorizzare il numero di elementi
3. CA impedire che la lista cresca oltre un numero massimo fisso di nodi
4. DA semplificare il codice eliminando i casi particolari in testa o in coda

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(n), dove n è il numero di parole
2. BO(log n), dove n è il numero di parole
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(L × n)

Quale affermazione sull'heapsort è corretta?

1. ARichiede tempo O(n) su qualsiasi input
2. BRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
3. COrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
4. DÈ stabile e richiede O(n) memoria aggiuntiva

Perché una tabella hash funzioni correttamente, quale regola devono rispettare hash e uguaglianza?

1. AValori hash uguali implicano chiavi uguali
2. BChiavi uguali devono avere valori hash uguali
3. CChiavi diverse devono avere valori hash diversi
4. DI valori hash devono essere numeri primi