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 een botsing (collision) in een hashtabel?

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

In welke volgorde bezoekt een preorder-doorloop van een binaire boom de knopen?

  1. ALinkersubboom, dan knoop, dan rechtersubboom
  2. BLinkersubboom, dan rechtersubboom, dan knoop
  3. CKnoop, dan linkersubboom, dan rechtersubboom
  4. DNiveau voor niveau vanaf de bovenkant
3.Makkelijk

Waar vind je het kleinste element van een binaire min-heap?

  1. AOp de laatste positie in de array
  2. BIn het meest linkse blad
  3. CIn de wortel
  4. DIn een willekeurig blad, dat moet worden gezocht
4.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 4
  4. DIndex 0
5.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. AArrays gebruiken minder instructies om waarden te vergelijken
  2. BGekoppelde lijsten slaan elementen altijd op schijf op
  3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  4. DEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
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. B1 2 4 5 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
7.Moeilijk

Aan welke eigenschap moet een rood-zwartboom voldoen?

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

Welke uitspraak over heapsort is juist?

  1. AHet draait op elke invoer in O(n) tijd
  2. BHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
  3. CHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
  4. DHet is stabiel en heeft O(n) extra geheugen nodig

Antwoordenblad

  1. 1. A · Twee verschillende sleutels worden op dezelfde index afgebeeld
  2. 2. C · Knoop, dan linkersubboom, dan rechtersubboom
  3. 3. C · In de wortel
  4. 4. C · Index 4
  5. 5. C · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  6. 6. D · 4 5 2 3 1
  7. 7. B · Elk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  8. 8. B · Het sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel

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