Scheda di esercizi di Strutture dati con soluzioni

Che cosa definisce un albero binario?

1. AL'albero ha esattamente due livelli
2. BOgni nodo ha esattamente due figli
3. COgni nodo memorizza un numero binario
4. DOgni nodo ha al massimo due figli

Che cos'è un grafo orientato?

1. AUn grafo in cui ogni coppia di vertici distinti è collegata da un arco
2. BUn grafo i cui archi hanno tutti un peso
3. CUn grafo privo di cicli
4. DUn grafo i cui archi hanno una direzione da un vertice a un altro

In un grafo, che cos'è un ciclo?

1. AUn vertice senza archi
2. BUn arco di peso zero
3. CUn cammino che inizia e finisce nello stesso vertice
4. DUn cammino che visita ogni vertice

Che cosa è vero per la matrice di adiacenza di un grafo non orientato?

1. AÈ sempre triangolare superiore
2. BOgni riga contiene esattamente un 1
3. CLa sua diagonale principale contiene sempre degli uno
4. DÈ simmetrica rispetto alla diagonale principale

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

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

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. ADoppio hashing (double hashing)
2. BScansione quadratica (quadratic probing)
3. CConcatenamento separato (separate chaining)
4. DScansione lineare (linear probing)

In una tabella hash con indirizzamento aperto, perché la cancellazione avviene spesso con un marcatore «lapide» (tombstone)?

1. ALe lapidi velocizzano l'hashing
2. BLe chiavi cancellate devono essere conservate per sempre per motivi di sicurezza, quindi le posizioni non si possono mai riutilizzare
3. CRende la tabella ordinata
4. DSvuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi

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. CInterrogazioni di somme prefisse e aggiornamenti di singoli elementi
4. DRicerca della mediana in O(1)