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

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

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

Wat doet de bewerking peek (of top) op een stack?

  1. AGeeft het onderste element van de stack terug
  2. BGeeft het bovenste element terug zonder het te verwijderen
  3. CVerwijdert alle elementen van de stack
  4. DVerwijdert het bovenste element en geeft het terug
3.Makkelijk

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

  1. AEen stack
  2. BEen ongeordende enkelvoudig gekoppelde lijst
  3. CEen heap
  4. DEen string
4.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 preorder-doorloop?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C1 2 3 4 5
  4. D1 2 4 5 3
5.Gemiddeld

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

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

AVL-bomen en rood-zwartbomen garanderen:

  1. ADat geen enkele knoop twee kinderen heeft
  2. BZoeken in constante tijd in elk geval
  3. CDat sleutels in invoegvolgorde worden opgeslagen
  4. DEen hoogte van O(log n) door herbalancering
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 gesorteerde array van alle n waarden
  4. DEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
8.Moeilijk

Waarom wordt verwijderen in een hashtabel met open adressering vaak gedaan met een "tombstone"-markering?

  1. AHet leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken
  2. BVerwijderde sleutels moeten om veiligheidsredenen voor altijd bewaard blijven, dus plekken kunnen nooit hergebruikt worden
  3. CTombstones versnellen het hashen
  4. DHet maakt de tabel gesorteerd

Antwoordenblad

  1. 1. C · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  2. 2. B · Geeft het bovenste element terug zonder het te verwijderen
  3. 3. C · Een heap
  4. 4. D · 1 2 4 5 3
  5. 5. C · O(V²)
  6. 6. D · Een hoogte van O(log n) door herbalancering
  7. 7. B · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  8. 8. A · Het leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken

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