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 blad in een boom?

  1. ADe knoop met de grootste waarde
  2. BEen knoop zonder kinderen
  3. CEen knoop met precies één kind
  4. DEen knoop zonder ouder
2.Makkelijk

Welke datastructuur werkt volgens het principe "first in, first out" (FIFO)?

  1. ABinaire boom
  2. BWachtrij (queue)
  3. CHeap
  4. DStapel (stack)
3.Makkelijk

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

  1. AGekoppelde lijst
  2. BStapel (stack)
  3. CHashtabel
  4. DWachtrij (queue)
4.Gemiddeld

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

  1. AO(log n)
  2. BO(n)
  3. CO(n log n)
  4. DO(1)
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(log n)
  2. BO(1)
  3. CO(n)
  4. DO(n²)
6.Gemiddeld

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

  1. Ai/2 en i/2 + 1
  2. B2i en 2i + 1
  3. C2i + 1 en 2i + 2
  4. Di + 1 en i + 2
7.Moeilijk

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

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

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

  1. AO(n)
  2. BO(m)
  3. CO(log n)
  4. DO(1 + α), waarbij α = n / m

Antwoordenblad

  1. 1. B · Een knoop zonder kinderen
  2. 2. B · Wachtrij (queue)
  3. 3. B · Stapel (stack)
  4. 4. A · O(log n)
  5. 5. B · O(1)
  6. 6. C · 2i + 1 en 2i + 2
  7. 7. A · O(n)
  8. 8. D · O(1 + α), waarbij α = n / m

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