Scheda di esercizi di Strutture dati con soluzioni

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

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

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUna stringa
2. BUna lista concatenata semplice non ordinata
3. CUn heap
4. DUno stack

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

1. ARimuovere l'elemento in testa
2. BAccedere all'elemento di indice i
3. CLeggere il primo elemento
4. DInserire in testa

Una coda è implementata con due pile: push su una pila «in» e pop da una pila «out», che viene riempita da «in» quando è vuota. Qual è il costo ammortizzato per operazione?

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

Come funziona extract-min in un min-heap binario?

1. ASi cercano in tutte le foglie il nuovo minimo
2. BSi sposta l'ultimo elemento nella radice e lo si fa scendere
3. CSi rimuove l'ultimo elemento dell'array
4. DSi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra

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

1. An (diventa una lista concatenata)
2. B1
3. Clog₂ n
4. D√n

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

1. AMemorizza le chiavi senza ordine
2. BNon usa memoria aggiuntiva
3. CRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti
4. DRicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi

Nel BST con radice 50, sottoalbero sinistro 30 (figli 20, 40) e sottoalbero destro 70 (figli 60, 80), la radice viene eliminata usando il successore in ordine. Quale chiave diventa la nuova radice?

1. A70
2. B80
3. C40
4. D60