Scheda di esercizi di Strutture dati con soluzioni

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AMaggiori del valore del nodo
2. BMinori del valore del nodo
3. CIn ordine casuale
4. DUguali al valore del nodo

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

1. ACoda
2. BTabella hash
3. CCoda con priorità
4. DPila

Quanti archi ha un albero con n nodi?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

1. A2i + 1 e 2i + 2
2. Bi + 1 e i + 2
3. Ci/2 e i/2 + 1
4. D2i e 2i + 1

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

1. AUna coda
2. BUna tabella hash
3. CUna pila
4. DUn albero binario di ricerca

Quanta memoria utilizza una matrice di adiacenza per un grafo con V vertici?

1. AO(V + E)
2. BO(log V)
3. CO(E)
4. DO(V²)

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

1. AInterrogazioni di somme prefisse e aggiornamenti di singoli elementi
2. BRicerca della mediana in O(1)
3. CInserimento di elementi in qualsiasi posizione
4. DOrdinamento dell'array e ricerca binaria

Senza unione per rango né compressione dei cammini, qual è il costo nel caso peggiore di una singola find in una struttura union-find con n elementi?

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