Scheda di esercizi di Strutture dati con soluzioni

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

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

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi sottoalbero destro, poi nodo
2. BNodo, poi sottoalbero sinistro, poi sottoalbero destro
3. CSottoalbero sinistro, poi nodo, poi sottoalbero destro
4. DSottoalbero destro, poi nodo, poi sottoalbero sinistro

Come sono memorizzati in memoria gli elementi di un array?

1. AIn un albero di pagine di memoria
2. BIn un unico blocco contiguo, uno dopo l'altro
3. CIn posizioni casuali scelte da un hash
4. DSparsi, collegati da puntatori

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(1)

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine per livelli
2. BOrdine crescente
3. COrdine sempre decrescente
4. DOrdine di inserimento

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. ALo stack delle chiamate
2. BUn albero binario di ricerca di frame
3. CUna tabella hash di funzioni
4. DLa coda della memoria heap

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

1. AL'altezza è al massimo n / 2
2. BL'altezza è esattamente log₂ n
3. CL'altezza è al massimo 2 log₂(n + 1)
4. DL'altezza è al massimo log₂ n + 1

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 muove un puntatore di un passo e un altro di due passi e si verifica se si incontrano
3. CSi contano i nodi finché il conteggio supera il campo lunghezza della lista
4. DSi memorizza ogni nodo visitato in un hash set