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 gerichte graaf?

  1. AEen graaf waarin elk paar verschillende knopen door een kant verbonden is
  2. BEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  3. CEen graaf waarvan alle kanten een gewicht hebben
  4. DEen graaf zonder cykels
2.Makkelijk

Wat slaat een map (dictionary) op?

  1. AWaarden gesorteerd op grootte
  2. BParen van gelijke sleutels
  3. CSleutel-waardeparen met unieke sleutels
  4. DAlleen waarden in volgorde van invoegen
3.Makkelijk

De diepte van een knoop in een boom is:

  1. AHet aantal knopen in zijn subboom
  2. BHet aantal kanten van die knoop tot het diepste blad
  3. CHet aantal kanten van de wortel tot die knoop
  4. DHet aantal kinderen van die knoop
4.Gemiddeld

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

  1. AO(n²)
  2. BO(log n)
  3. CO(1)
  4. DO(n)
5.Gemiddeld

Hoe vind je de kleinste sleutel in een binaire zoekboom?

  1. AVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is
  2. BKijk alleen naar de wortel
  3. CVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
  4. DBezoek elk blad en vergelijk ze
6.Gemiddeld

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

  1. AAdjacency matrix
  2. BAdjacency list
  3. CEen binaire heap van kanten
  4. DEén gesorteerde array van knopen
7.Moeilijk

Een AVL-knoop is ongebalanceerd omdat de rechtersubboom van zijn linkerkind te hoog werd (left-right-geval). Welke correctie wordt toegepast?

  1. AEen enkele linksrotatie bij de knoop
  2. BEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  3. CEen enkele rechtsrotatie bij de knoop
  4. DEen rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
8.Moeilijk

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

  1. AOmdat halveren bij de helft elementen zou kwijtraken
  2. BOm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  3. COmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
  4. DOm de array gesorteerd te houden

Antwoordenblad

  1. 1. B · Een graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  2. 2. C · Sleutel-waardeparen met unieke sleutels
  3. 3. C · Het aantal kanten van de wortel tot die knoop
  4. 4. C · O(1)
  5. 5. C · Volg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
  6. 6. B · Adjacency list
  7. 7. B · Een linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  8. 8. B · Om herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen

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