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

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

  1. AIl numero di nodi della lista
  2. BL'indirizzo del nodo precedente
  3. CL'indirizzo del primo nodo
  4. DNull (nessun nodo)
2.Facile

In un albero, che cosa sono i nodi fratelli?

  1. ANodi alla stessa profondità in sottoalberi diversi
  2. BNodi privi di figli
  3. CNodi che hanno lo stesso genitore
  4. DUn nodo e il suo genitore
3.Facile

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

  1. AInsert
  2. BPush
  3. CEnqueue
  4. DDequeue
4.Media

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

  1. AO(log n), dove n è il numero di parole
  2. BO(n), dove n è il numero di parole
  3. CO(L), indipendentemente da quante parole sono memorizzate
  4. DO(L × n)
5.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
6.Media

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

  1. AUna lista concatenata non ordinata
  2. BUna pila
  3. CUna tabella hash
  4. DUn albero binario di ricerca bilanciato
7.Difficile

Nel BST con radice 50, sottoalbero sinistro 30 (figli 20, 40) e sottoalbero destro 70 (figli 60, 80), la radice viene eliminata usando il successore in ordine. Quale chiave diventa la nuova radice?

  1. A80
  2. B40
  3. C60
  4. D70
8.Difficile

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

  1. AUn array ordinato di tutti gli n valori
  2. BUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
  3. CUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli
  4. DUna coda FIFO degli ultimi k valori

Soluzioni

  1. 1. D · Null (nessun nodo)
  2. 2. C · Nodi che hanno lo stesso genitore
  3. 3. D · Dequeue
  4. 4. C · O(L), indipendentemente da quante parole sono memorizzate
  5. 5. A · A semplificare il codice eliminando i casi particolari in testa o in coda
  6. 6. D · Un albero binario di ricerca bilanciato
  7. 7. C · 60
  8. 8. B · Un max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo

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