Scheda di esercizi di Strutture dati con soluzioni

Scheda di esercizi di Strutture dati gratuita e stampabile: 8 esercizi dal livello facile a quello d’esame, con le soluzioni. Stampala o salvala come PDF.

Nuova schedaEsercitati online con i suggerimenti

Per i docenti: gratuita da stampare, copiare e usare in classe. Ogni nuova scheda ha nuovi valori e le sue soluzioni. Un link a ExamProblems nella pagina del corso è molto apprezzato.

Nome: ____________________   Data: ____________

1.Facile

Qual è la caratteristica distintiva di un insieme (set) come tipo di dato astratto?

  1. APermette l'accesso solo a un'estremità
  2. BMemorizza elementi in ordine
  3. CMemorizza elementi senza duplicati
  4. DMemorizza coppie chiave–valore
2.Facile

In quale ordine una visita in preordine (preorder) di un albero binario visita i nodi?

  1. ALivello per livello a partire dall'alto
  2. BNodo, poi sottoalbero sinistro, poi sottoalbero destro
  3. CSottoalbero sinistro, poi sottoalbero destro, poi nodo
  4. DSottoalbero sinistro, poi nodo, poi sottoalbero destro
3.Facile

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

  1. AUguali al valore del nodo
  2. BIn ordine casuale
  3. CMinori del valore del nodo
  4. DMaggiori del valore del nodo
4.Media

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 postordine?

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
5.Media

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

  1. A(i + 1) mod n
  2. B2i + 1
  3. C(i − 1) mod n
  4. Di + 1
6.Media

Come si inserisce un nuovo elemento in un heap binario?

  1. ALo si pone nella radice e lo si fa scendere
  2. BSi ricostruisce da zero l'intero heap
  3. CLo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
  4. DLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi
7.Difficile

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

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

Nell'ipotesi di hashing uniforme semplice, qual è il tempo atteso di una ricerca in una tabella hash con concatenamento, n chiavi e m bucket?

  1. AO(1 + α), dove α = n / m
  2. BO(n)
  3. CO(log n)
  4. DO(m)

Soluzioni

  1. 1. C · Memorizza elementi senza duplicati
  2. 2. B · Nodo, poi sottoalbero sinistro, poi sottoalbero destro
  3. 3. C · Minori del valore del nodo
  4. 4. D · 4 5 2 3 1
  5. 5. A · (i + 1) mod n
  6. 6. C · Lo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
  7. 7. A · Tutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
  8. 8. A · O(1 + α), dove α = n / m

Soluzioni complete passo passo: esercitati su questo argomento su examproblems.com.