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 zonder cykels
  3. CEen graaf waarvan alle kanten een gewicht hebben
  4. DEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
2.Makkelijk

Een graaf bestaat uit:

  1. AAlleen sleutels en hashes
  2. BAlleen een wortel en bladeren
  3. CKnopen (vertices) verbonden door kanten
  4. DRijen en kolommen
3.Makkelijk

Wat is een deque (double-ended queue)?

  1. AEen queue gesorteerd op prioriteit
  2. BEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
  3. CTwee aparte queues die één array delen
  4. DEen queue die alleen verwijderen achteraan toestaat
4.Gemiddeld

Welke datastructuur gebruikt diepte-eerst zoeken (DFS) in de iteratieve versie?

  1. AAlleen een hashtabel
  2. BEen stack
  3. CEen heap
  4. DEen queue
5.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(1)
  3. CO(log n)
  4. DO(n²)
6.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
7.Moeilijk

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

  1. ABloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
  2. BVerwijderen zou het percentage fout-positieven naar 100% verhogen
  3. CBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
  4. DDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
8.Moeilijk

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

  1. AHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
  2. BDe hele subboom te verwijderen
  3. CDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
  4. DHem te verwisselen met de wortel

Antwoordenblad

  1. 1. D · Een graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  2. 2. C · Knopen (vertices) verbonden door kanten
  3. 3. B · Een structuur die invoegen en verwijderen aan beide uiteinden toestaat
  4. 4. B · Een stack
  5. 5. B · O(1)
  6. 6. C · Volg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
  7. 7. D · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  8. 8. A · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen

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