Werkblad Datastructuren met antwoorden

Gratis printbaar werkblad Datastructuren: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Een graaf bestaat uit:

  1. ARijen en kolommen
  2. BAlleen sleutels en hashes
  3. CAlleen een wortel en bladeren
  4. DKnopen (vertices) verbonden door kanten
2.Makkelijk

Een hashtabel slaat data op als:

  1. AEen string met vaste lengte
  2. BSleutel-waardeparen die via een hashfunctie worden gevonden
  3. CUitsluitend een gesorteerde lijst
  4. DEen boom met geordende sleutels
3.Makkelijk

Wat is de bezettingsgraad (load factor) van een hashtabel?

  1. AHet aantal botsingen tot nu toe
  2. BDe tijd die nodig is om de tabel van schijf te laden
  3. CHet aantal opgeslagen elementen gedeeld door het aantal buckets
  4. DHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
4.Gemiddeld

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

  1. AO(E²)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V²)
5.Gemiddeld

Welke datastructuur gebruikt diepte-eerst zoeken (DFS) in de iteratieve versie?

  1. AEen queue
  2. BEen heap
  3. CEen stack
  4. DAlleen een hashtabel
6.Gemiddeld

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

  1. A4 2 5 1 3
  2. B5 4 3 2 1
  3. C1 2 4 5 3
  4. D4 5 2 3 1
7.Moeilijk

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

  1. ADe map geeft een fout op het moment dat het veld verandert
  2. BHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  3. CEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  4. DDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
8.Moeilijk

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

  1. AEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  2. BEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  3. CEen gesorteerde array van alle n waarden
  4. DEen FIFO-queue van de laatste k waarden

Antwoordenblad

  1. 1. D · Knopen (vertices) verbonden door kanten
  2. 2. B · Sleutel-waardeparen die via een hashfunctie worden gevonden
  3. 3. C · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  4. 4. C · O(V + E)
  5. 5. C · Een stack
  6. 6. D · 4 5 2 3 1
  7. 7. B · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  8. 8. A · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.