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 cykel in een graaf?

  1. AEen pad dat elke knoop bezoekt
  2. BEen kant met gewicht nul
  3. CEen knoop zonder kanten
  4. DEen pad dat begint en eindigt in dezelfde knoop
2.Makkelijk

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

  1. AHet eerste element lezen
  2. BHet kopelement verwijderen
  3. CHet element op index i benaderen
  4. DInvoegen aan de kop
3.Makkelijk

Wat is een blad in een boom?

  1. AEen knoop met precies één kind
  2. BEen knoop zonder kinderen
  3. CDe knoop met de grootste waarde
  4. DEen knoop zonder ouder
4.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

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

AVL-bomen en rood-zwartbomen garanderen:

  1. ADat geen enkele knoop twee kinderen heeft
  2. BEen hoogte van O(log n) door herbalancering
  3. CDat sleutels in invoegvolgorde worden opgeslagen
  4. DZoeken in constante tijd in elk geval
6.Gemiddeld

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

  1. AKwadratisch proberen (quadratic probing)
  2. BDubbel hashen (double hashing)
  3. CSeparate chaining (ketenen)
  4. DLineair proberen (linear probing)
7.Moeilijk

Een Bloom-filter kan de vraag "zit dit element in de verzameling?" beantwoorden met:

  1. AAlleen antwoorden voor getallen
  2. BMogelijke fout-negatieven maar geen fout-positieven
  3. CMogelijke fout-positieven maar geen fout-negatieven
  4. DAltijd exacte antwoorden
8.Moeilijk

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

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

Antwoordenblad

  1. 1. D · Een pad dat begint en eindigt in dezelfde knoop
  2. 2. C · Het element op index i benaderen
  3. 3. B · Een knoop zonder kinderen
  4. 4. D · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  5. 5. B · Een hoogte van O(log n) door herbalancering
  6. 6. C · Separate chaining (ketenen)
  7. 7. C · Mogelijke fout-positieven maar geen fout-negatieven
  8. 8. D · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen

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