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

Quanti archi ha un albero con n nodi?

  1. An + 1
  2. B2n
  3. Cn
  4. Dn − 1
2.Facile

Che cosa definisce un albero binario?

  1. AL'albero ha esattamente due livelli
  2. BOgni nodo ha al massimo due figli
  3. COgni nodo ha esattamente due figli
  4. DOgni nodo memorizza un numero binario
3.Facile

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

  1. ASottoalbero sinistro, poi sottoalbero destro, poi nodo
  2. BLivello per livello a partire dall'alto
  3. CNodo, poi sottoalbero sinistro, poi sottoalbero destro
  4. DSottoalbero sinistro, poi nodo, poi sottoalbero destro
4.Media

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 impedire che la lista cresca oltre un numero massimo fisso di nodi
  3. CA memorizzare il numero di elementi
  4. DA rendere la lista ordinata
5.Media

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

  1. AUna lista doppiamente concatenata
  2. BUn array dinamico
  3. CUna lista concatenata semplice
  4. DUn array ordinato
6.Media

Come funziona extract-min in un min-heap binario?

  1. ASi cercano in tutte le foglie il nuovo minimo
  2. BSi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra
  3. CSi sposta l'ultimo elemento nella radice e lo si fa scendere
  4. DSi rimuove l'ultimo elemento dell'array
7.Difficile

Quale affermazione sull'heapsort è corretta?

  1. AOrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
  2. BRichiede tempo O(n) su qualsiasi input
  3. CRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
  4. DÈ stabile e richiede O(n) memoria aggiuntiva
8.Difficile

Quale problema della scansione lineare viene ridotto principalmente dal doppio hashing?

  1. ALa necessità di una funzione hash
  2. BIl costo O(n) della lettura del valore di una chiave
  3. CL'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate
  4. DLa necessità di memorizzare le chiavi nella tabella

Soluzioni

  1. 1. D · n − 1
  2. 2. B · Ogni nodo ha al massimo due figli
  3. 3. C · Nodo, poi sottoalbero sinistro, poi sottoalbero destro
  4. 4. A · A semplificare il codice eliminando i casi particolari in testa o in coda
  5. 5. A · Una lista doppiamente concatenata
  6. 6. C · Si sposta l'ultimo elemento nella radice e lo si fa scendere
  7. 7. A · Ordina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
  8. 8. C · L'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate

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