Scheda di esercizi di Strutture dati con soluzioni

Quale struttura dati si usa per eseguire una visita per livelli di un albero?

1. APila
2. BCoda
3. CCoda con priorità
4. DTabella hash

Qual è la differenza principale tra un array statico e un array dinamico?

1. AUn array statico può memorizzare solo numeri
2. BUn array statico permette un accesso per indice più lento
3. CUn array dinamico può crescere spostandosi in un blocco di memoria più grande
4. DUn array dinamico memorizza gli elementi in nodi collegati così può crescere un elemento alla volta

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. AEnqueue
2. BDequeue
3. CInsert
4. DPush

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(log n)
2. BO(1)
3. CO(n²)
4. DO(n)

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. A2^h
2. Bh²
3. C2^h+1 − 1
4. D2h + 1

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice 2i + 1
2. BAll'indice ⌊i / 2⌋ + 1
3. CAll'indice ⌊(i − 1) / 2⌋
4. DAll'indice i − 1

Un albero di Fenwick (binary indexed tree) su un array di n numeri supporta quali operazioni in O(log n)?

1. AOrdinamento dell'array e ricerca binaria
2. BInserimento di elementi in qualsiasi posizione
3. CRicerca della mediana in O(1)
4. DInterrogazioni di somme prefisse e aggiornamenti di singoli elementi

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. A60
2. B80
3. C70
4. D40