Scheda di esercizi di Strutture dati con soluzioni

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BIl numero di vertici del grafo
3. CLa lunghezza del cammino più lungo che parte da esso
4. DIl numero di archi a esso collegati

Quale struttura dati funziona secondo il principio «ultimo a entrare, primo a uscire» (LIFO)?

1. APila (stack)
2. BLista concatenata
3. CTabella hash
4. DCoda (queue)

Qual è la differenza principale tra un array statico e un array dinamico?

1. AUn array statico può memorizzare solo numeri
2. BUn array dinamico può crescere spostandosi in un blocco di memoria più grande
3. CUn array dinamico memorizza gli elementi in nodi collegati così può crescere un elemento alla volta
4. DUn array statico permette un accesso per indice più lento

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

A che cosa serve un nodo sentinella (fittizio) in una lista concatenata?

1. AA semplificare il codice eliminando i casi particolari in testa o in coda
2. BA rendere la lista ordinata
3. CA impedire che la lista cresca oltre un numero massimo fisso di nodi
4. DA memorizzare il numero di elementi

In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?

1. A2i + 1
2. B(i + 1) mod n
3. C(i − 1) mod n
4. Di + 1

Qual è il tempo di esecuzione della visita in ampiezza (BFS) su un grafo con V vertici memorizzato come matrice di adiacenza?

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

L'algoritmo di Kahn per l'ordinamento topologico rimuove ripetutamente i vertici con grado entrante 0. Quale struttura contiene questi vertici?

1. AUna coda (o una collezione qualsiasi) dei vertici con grado entrante 0
2. BUn max-heap ordinato per grado uscente
3. CUna pila di tutti gli archi visitati
4. DUna matrice di adiacenza che registra quali vertici sono già stati rimossi