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. AUna lista dei suoi vertici adiacenti
2. BIl numero totale di archi del grafo
3. CIl cammino minimo verso ogni altro vertice
4. DUna riga di V valori booleani

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

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

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. AEnqueue
2. BDequeue
3. CInsert
4. DPush

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

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

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

1. AAll'indice 6
2. BAll'indice 0
3. CAll'indice 4
4. DAll'indice 3

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in preordine?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D1 2 3 4 5

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

1. AMemorizza le chiavi senza ordine
2. BNon usa memoria aggiuntiva
3. CRicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi
4. DRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti

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

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