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 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
2.Makkelijk

Wat is een botsing (collision) in een hashtabel?

  1. ATwee verschillende sleutels worden op dezelfde index afgebeeld
  2. BEen sleutel kan helemaal niet worden gehasht
  3. CDe tabel heeft geen geheugen meer
  4. DTwee gelijke sleutels worden twee keer opgeslagen
3.Makkelijk

Wat is de wortel van een boom?

  1. AEen willekeurige knoop in het midden
  2. BEen knoop zonder kinderen
  3. CDe bovenste knoop zonder ouder
  4. DDe knoop met de grootste waarde
4.Gemiddeld

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

  1. ADubbel hashen (double hashing)
  2. BSeparate chaining (ketenen)
  3. CKwadratisch proberen (quadratic probing)
  4. DLineair proberen (linear probing)
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 3
  2. BIndex 6
  3. CIndex 0
  4. DIndex 4
6.Gemiddeld

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

  1. AArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  2. BEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
  3. CGekoppelde lijsten slaan elementen altijd op schijf op
  4. DArrays gebruiken minder instructies om waarden te vergelijken
7.Moeilijk

Aan welke eigenschap moet een rood-zwartboom voldoen?

  1. AElke knoop moet rood zijn
  2. BElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  3. CDe wortel moet rood zijn
  4. DRode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
8.Moeilijk

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

  1. AHij slaat sleutels ongeordend op
  2. BVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  3. CHij gebruikt geen extra geheugen
  4. DGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart

Antwoordenblad

  1. 1. B · Sleutel-waardeparen die via een hashfunctie worden gevonden
  2. 2. A · Twee verschillende sleutels worden op dezelfde index afgebeeld
  3. 3. C · De bovenste knoop zonder ouder
  4. 4. B · Separate chaining (ketenen)
  5. 5. D · Index 4
  6. 6. A · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  7. 7. B · Elk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  8. 8. B · Verwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers

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