Scheda di esercizi di Strutture dati con soluzioni

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

1. ARimuovere l'elemento in testa
2. BInserire in testa
3. CAccedere all'elemento di indice i
4. DLeggere il primo elemento

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

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

Quale struttura dati è più adatta per la funzione «annulla» (undo) di un editor di testo?

1. AInsieme hash (hash set)
2. BPila (stack)
3. CGrafo
4. DCoda (queue)

Come si trova la chiave minima in un albero binario di ricerca?

1. ASi visitano tutte le foglie e le si confronta
2. BSi guarda solo la radice
3. CSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
4. DSi seguono i figli destri dalla radice finché non c'è più un figlio destro

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

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

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D5 4 3 2 1

Che cosa fa uno splay tree dopo ogni accesso?

1. APorta con rotazioni il nodo acceduto fino alla radice
2. BRicostruisce l'intero albero in forma bilanciata
3. CRicolora i nodi lungo il cammino di ricerca
4. DSposta il nodo acceduto in una foglia

Quanto tempo serve per cercare una chiave arbitraria in un min-heap binario di n elementi?

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