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

  1. AEen graaf die op schijf is opgeslagen
  2. BEen graaf met meer kanten dan knopen
  3. CEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
  4. DEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
2.Makkelijk

Een hashtabel slaat data op als:

  1. AUitsluitend een gesorteerde lijst
  2. BSleutel-waardeparen die via een hashfunctie worden gevonden
  3. CEen string met vaste lengte
  4. DEen boom met geordende sleutels
3.Makkelijk

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

  1. ARechtersubboom, dan knoop, dan linkersubboom
  2. BLinkersubboom, dan knoop, dan rechtersubboom
  3. CLinkersubboom, dan rechtersubboom, dan knoop
  4. DKnoop, dan linkersubboom, dan rechtersubboom
4.Gemiddeld

Een circulaire buffer (ring buffer) wordt vaak gebruikt om het volgende te implementeren:

  1. AEen graafdoorloop
  2. BEen binaire zoekboom
  3. CEen wachtrij met vaste grootte
  4. DEen hashfunctie
5.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. ABouw de hele heap opnieuw op
  2. BPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  3. CVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
  4. DPlaats het in de wortel en laat het omlaag zakken (sift down)
6.Gemiddeld

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

  1. AO(n)
  2. BO(n log n)
  3. CO(log n)
  4. DO(1)
7.Moeilijk

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)
8.Moeilijk

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

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

Antwoordenblad

  1. 1. D · Een graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  2. 2. B · Sleutel-waardeparen die via een hashfunctie worden gevonden
  3. 3. C · Linkersubboom, dan rechtersubboom, dan knoop
  4. 4. C · Een wachtrij met vaste grootte
  5. 5. B · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  6. 6. C · O(log n)
  7. 7. C · O(log n)
  8. 8. D · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken

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