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

Een graaf bestaat uit:

  1. AAlleen een wortel en bladeren
  2. BKnopen (vertices) verbonden door kanten
  3. CRijen en kolommen
  4. DAlleen sleutels en hashes
2.Makkelijk

Hoeveel kanten heeft een boom met n knopen?

  1. An + 1
  2. Bn
  3. C2n
  4. Dn − 1
3.Makkelijk

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

  1. AStack
  2. BQueue
  3. CPrioriteitswachtrij
  4. DHashtabel
4.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 postorder-doorloop?

  1. A5 4 3 2 1
  2. B1 2 4 5 3
  3. C4 5 2 3 1
  4. D4 2 5 1 3
5.Gemiddeld

Wat kost het invoegen van een element in het midden van een array met n elementen?

  1. AO(1), omdat de index bekend is
  2. BO(n²), omdat elk element n keer verschuift
  3. CO(log n), vanwege binair zoeken
  4. DO(n), omdat latere elementen moeten opschuiven
6.Gemiddeld

Welke datastructuur wordt gebruikt om te controleren of de haakjes in "{[()]}" in balans zijn?

  1. AEen hashtabel
  2. BEen binaire zoekboom
  3. CEen stack
  4. DEen queue
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(log n)
  3. CO(n)
  4. DO(1)
8.Moeilijk

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

  1. AAlleen een stack
  2. BEen hashmap gecombineerd met een dubbel gekoppelde lijst
  3. CAlleen een binaire zoekboom
  4. DEén gesorteerde array

Antwoordenblad

  1. 1. B · Knopen (vertices) verbonden door kanten
  2. 2. D · n − 1
  3. 3. B · Queue
  4. 4. C · 4 5 2 3 1
  5. 5. D · O(n), omdat latere elementen moeten opschuiven
  6. 6. C · Een stack
  7. 7. C · O(n)
  8. 8. B · Een hashmap gecombineerd met een dubbel gekoppelde lijst

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