Scheda di esercizi di Strutture dati con soluzioni

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AIl cammino minimo verso ogni altro vertice
2. BUna riga di V valori booleani
3. CUna lista dei suoi vertici adiacenti
4. DIl numero totale di archi del grafo

In un albero, che cos'è una foglia?

1. AIl nodo con il valore più grande
2. BUn nodo senza genitore
3. CUn nodo con esattamente un figlio
4. DUn nodo senza figli

Una tabella hash memorizza i dati come:

1. ASolo una lista ordinata
2. BUn albero con chiavi ordinate
3. CUna stringa di lunghezza fissa
4. DCoppie chiave–valore individuate da una funzione hash

Perché un heap binario si può memorizzare in un array senza puntatori?

1. AGli array mantengono automaticamente le chiavi in ordine, quindi non servono puntatori
2. BÈ un albero binario completo, quindi le posizioni seguono semplici formule sugli indici
3. CTutte le chiavi di un heap sono uguali
4. DGli heap non contengono mai più di 100 elementi

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

Hai un riferimento a un nodo a metà di una lista. In quale lista puoi rimuoverlo in O(1)?

1. AUn array dinamico
2. BUna lista doppiamente concatenata
3. CUna lista concatenata semplice
4. DUn array ordinato

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

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

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