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 met meer kanten dan knopen
  2. BEen graaf die op schijf is opgeslagen
  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

Welke datastructuur wordt gebruikt voor een level-order-doorloop van een boom?

  1. AQueue
  2. BHashtabel
  3. CPrioriteitswachtrij
  4. DStack
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. CKnoop, dan linkersubboom, dan rechtersubboom
  4. DLinkersubboom, dan rechtersubboom, dan knoop
4.Gemiddeld

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

  1. Alog₂ n
  2. B1
  3. C√n
  4. Dn (hij wordt een gekoppelde lijst)
5.Gemiddeld

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de preorder-doorloop?

  1. A4 5 2 3 1
  2. B1 2 4 5 3
  3. C1 2 3 4 5
  4. D4 2 5 1 3
6.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. AArrays gebruiken minder instructies om waarden te vergelijken
  2. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  3. CEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
  4. DGekoppelde lijsten slaan elementen altijd op schijf op
7.Moeilijk

Aan welke eigenschap moet een rood-zwartboom voldoen?

  1. AElke knoop moet rood zijn
  2. BRode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
  3. CElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  4. DDe wortel moet rood zijn
8.Moeilijk

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

  1. AMaak de buffergrootte een macht van twee
  2. BHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt
  3. CSla front en rear op in dezelfde variabele
  4. DMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is

Antwoordenblad

  1. 1. D · Een graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  2. 2. A · Queue
  3. 3. D · Linkersubboom, dan rechtersubboom, dan knoop
  4. 4. D · n (hij wordt een gekoppelde lijst)
  5. 5. B · 1 2 4 5 3
  6. 6. B · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  7. 7. C · Elk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  8. 8. B · Houd een apart aantal elementen bij, of laat altijd één plaats ongebruikt

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