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

Che cosa memorizza una mappa (dizionario)?

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

In un albero, che cos'è una foglia?

  1. AUn nodo senza genitore
  2. BUn nodo con esattamente un figlio
  3. CUn nodo senza figli
  4. DIl nodo con il valore più grande
3.Facile

Che cos'è una deque (coda a doppia estremità)?

  1. AUna struttura che permette inserimenti e rimozioni a entrambe le estremità
  2. BUna coda che permette rimozioni solo in fondo
  3. CUna coda ordinata per priorità
  4. DDue code separate che condividono un array
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. A5 4 3 2 1
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D4 2 5 1 3
5.Media

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

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

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

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

Quale affermazione sull'heapsort è corretta?

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

Quale proprietà deve soddisfare un albero rosso-nero?

  1. ALa radice deve essere rossa
  2. BOgni nodo deve essere rosso
  3. COgni cammino da un nodo alle sue foglie discendenti contiene lo stesso numero di nodi neri
  4. DOgni nodo rosso deve avere figli rossi, quindi i nodi rossi formano sempre catene ininterrotte fino alle foglie

Soluzioni

  1. 1. C · Coppie chiave–valore con chiavi univoche
  2. 2. C · Un nodo senza figli
  3. 3. A · Una struttura che permette inserimenti e rimozioni a entrambe le estremità
  4. 4. B · 4 5 2 3 1
  5. 5. A · O(L), indipendentemente da quante parole sono memorizzate
  6. 6. B · Si sposta l'ultimo elemento nella radice e lo si fa scendere
  7. 7. B · Ordina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
  8. 8. C · Ogni cammino da un nodo alle sue foglie discendenti contiene lo stesso numero di nodi neri

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