Scheda di esercizi di Strutture dati con soluzioni

Che cosa fa l'operazione peek (o top) su una pila?

1. ARimuove tutti gli elementi dalla pila
2. BRestituisce l'elemento in cima senza rimuoverlo
3. CRestituisce l'elemento in fondo alla pila
4. DRimuove l'elemento in cima e lo restituisce

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BCoppie di chiavi uguali
3. CCoppie chiave–valore con chiavi univoche
4. DValori ordinati per grandezza

In un grafo, che cos'è un ciclo?

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

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

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

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L × n)
2. BO(L), indipendentemente da quante parole sono memorizzate
3. CO(log n), dove n è il numero di parole
4. DO(n), dove n è il numero di parole

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

1. AUn array ordinato
2. BUn array dinamico
3. CUna lista doppiamente concatenata
4. DUna lista concatenata semplice

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

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

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

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