Scheda di esercizi di Strutture dati con soluzioni

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e un indice
2. BSolo dati
3. CDati e un riferimento al nodo successivo
4. DDati e riferimenti a tutti gli altri nodi

Che cos'è un grafo orientato?

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

Un grafo è composto da:

1. ASolo chiavi e hash
2. BRighe e colonne
3. CSolo una radice e delle foglie
4. DVertici (nodi) collegati da archi

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

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

Quale tipo di dato astratto usa l'algoritmo di Dijkstra per scegliere il prossimo vertice da elaborare?

1. AUna coda con priorità di minimo
2. BUna pila
3. CUna coda FIFO
4. DUn insieme senza ordinamento

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(n²), perché ogni elemento si sposta n volte
2. BO(1), perché l'indice è noto
3. CO(log n), per via della ricerca binaria
4. DO(n), perché gli elementi successivi devono essere spostati

Perché i database usano spesso B+-alberi anziché semplici B-alberi per gli indici?

1. AI B+-alberi non devono essere bilanciati
2. BI B+-alberi memorizzano i dati solo nella radice
3. CTutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
4. DI B+-alberi usano nodi interni binari, il che riduce le letture da disco

Perché i B-alberi (B-tree) sono usati nei database e nei file system?

1. AUsano meno memoria di qualsiasi array, quindi l'intero indice sta sempre nella memoria centrale
2. BNon richiedono ribilanciamento
3. CIl loro elevato fattore di ramificazione mantiene l'albero poco profondo, riducendo le lente letture da disco
4. DMemorizzano i dati in modo non ordinato