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 kant met gewicht nul
  2. BEen pad dat begint en eindigt in dezelfde knoop
  3. CEen pad dat elke knoop bezoekt
  4. DEen knoop zonder kanten
2.Makkelijk

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

  1. ALinkersubboom, dan knoop, dan rechtersubboom
  2. BKnoop, dan linkersubboom, dan rechtersubboom
  3. CLinkersubboom, dan rechtersubboom, dan knoop
  4. DRechtersubboom, dan knoop, dan linkersubboom
3.Makkelijk

De diepte van een knoop in een boom is:

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

Hoe werkt extract-min in een binaire min-heap?

  1. AZoek in alle bladeren naar het nieuwe minimum
  2. BVerwijder het laatste element van de array
  3. CVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  4. DVerwijder de wortel en schuif alle elementen één plaats naar links
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. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
  2. BArrays gebruiken minder instructies om waarden te vergelijken
  3. CGekoppelde lijsten slaan elementen altijd op schijf op
  4. DArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
6.Gemiddeld

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

  1. A2h + 1
  2. B2h
  3. C2h+1 − 1
  4. Dh2
7.Moeilijk

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

  1. AO(n log n) tijd en O(1) extra geheugen
  2. BO(n) tijd en O(1) extra geheugen
  3. CO(1) tijd en O(1) extra geheugen
  4. DO(n) tijd en O(n) extra geheugen
8.Moeilijk

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

  1. AEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  2. BEen FIFO-queue van de laatste k waarden
  3. CEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  4. DEen gesorteerde array van alle n waarden

Antwoordenblad

  1. 1. B · Een pad dat begint en eindigt in dezelfde knoop
  2. 2. C · Linkersubboom, dan rechtersubboom, dan knoop
  3. 3. A · Het aantal kanten van de wortel tot die knoop
  4. 4. C · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  5. 5. D · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  6. 6. C · 2h+1 − 1
  7. 7. B · O(n) tijd en O(1) extra geheugen
  8. 8. C · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

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