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 cos'è un grafo orientato?

  1. AUn grafo in cui ogni coppia di vertici distinti è collegata da un arco
  2. BUn grafo privo di cicli
  3. CUn grafo i cui archi hanno una direzione da un vertice a un altro
  4. DUn grafo i cui archi hanno tutti un peso
2.Facile

In una lista concatenata semplice, ogni nodo contiene:

  1. ADati e riferimenti a tutti gli altri nodi
  2. BDati e un riferimento al nodo successivo
  3. CSolo dati
  4. DDati e un indice
3.Facile

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

  1. ADue copie dei dati e un solo puntatore
  2. BDati, un puntatore al nodo successivo e un puntatore al nodo precedente
  3. CDati e soltanto un puntatore al nodo successivo
  4. DDati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo
4.Media

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

  1. AUno stack
  2. BUna coda
  3. CSolo una tabella hash
  4. DUn heap
5.Media

Quanta memoria utilizza una matrice di adiacenza per un grafo con V vertici?

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

Come si inserisce un nuovo elemento in un heap binario?

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

Un nodo AVL è sbilanciato perché il sottoalbero destro del suo figlio sinistro è diventato troppo alto (caso sinistra-destra). Quale correzione si applica?

  1. AUna singola rotazione a sinistra sul nodo
  2. BUna rotazione a destra sul figlio sinistro, poi una rotazione a sinistra sul nodo
  3. CUna rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo
  4. DUna singola rotazione a destra sul nodo

Soluzioni

  1. 1. C · Un grafo i cui archi hanno una direzione da un vertice a un altro
  2. 2. B · Dati e un riferimento al nodo successivo
  3. 3. B · Dati, un puntatore al nodo successivo e un puntatore al nodo precedente
  4. 4. A · Uno stack
  5. 5. A · O(V²)
  6. 6. A · Lo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
  7. 7. A · Ordina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
  8. 8. C · Una rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo

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