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

Hoe heet de stackbewerking die een element bovenaan toevoegt?

  1. APop
  2. BPeek
  3. CPush
  4. DEnqueue
2.Makkelijk

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

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

Wat slaat een map (dictionary) op?

  1. AParen van gelijke sleutels
  2. BSleutel-waardeparen met unieke sleutels
  3. CAlleen waarden in volgorde van invoegen
  4. DWaarden gesorteerd op grootte
4.Gemiddeld

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

  1. AEen dubbel gekoppelde lijst
  2. BEen enkelvoudig gekoppelde lijst
  3. CEen dynamische array
  4. DEen gesorteerde array
5.Gemiddeld

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

  1. AIndex 6
  2. BIndex 3
  3. CIndex 4
  4. DIndex 0
6.Gemiddeld

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

  1. AEen min-prioriteitswachtrij
  2. BEen FIFO-queue
  3. CEen set zonder ordening
  4. DEen stack
7.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 FIFO-queue van de laatste k waarden
  2. BEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  3. CEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  4. DEen gesorteerde array van alle n waarden
8.Moeilijk

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

  1. AEen deque met indices in afnemende volgorde van waarde
  2. BEen min-heap die voor elk venster opnieuw wordt opgebouwd
  3. CEen gesorteerde array die door verschuiven wordt bijgewerkt
  4. DEen enkelvoudig gekoppelde lijst van de elementen in het venster

Antwoordenblad

  1. 1. C · Push
  2. 2. A · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  3. 3. B · Sleutel-waardeparen met unieke sleutels
  4. 4. A · Een dubbel gekoppelde lijst
  5. 5. C · Index 4
  6. 6. A · Een min-prioriteitswachtrij
  7. 7. B · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  8. 8. A · Een deque met indices in afnemende volgorde van waarde

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