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 doet de bewerking peek (of top) op een stack?

  1. AVerwijdert het bovenste element en geeft het terug
  2. BGeeft het onderste element van de stack terug
  3. CVerwijdert alle elementen van de stack
  4. DGeeft het bovenste element terug zonder het te verwijderen
2.Makkelijk

Wat is een gerichte graaf?

  1. AEen graaf waarvan alle kanten een gewicht hebben
  2. BEen graaf waarin elk paar verschillende knopen door een kant verbonden is
  3. CEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  4. DEen graaf zonder cykels
3.Makkelijk

De diepte van een knoop in een boom is:

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

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

  1. AO(V²)
  2. BO(V + E)
  3. CO(E²)
  4. DO(V × E)
5.Gemiddeld

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

  1. A(i − 1) mod n
  2. Bi + 1
  3. C(i + 1) mod n
  4. D2i + 1
6.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. APlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  2. BPlaats het in de wortel en laat het omlaag zakken (sift down)
  3. CBouw de hele heap opnieuw op
  4. DVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
7.Moeilijk

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

  1. AHij gebruikt geen extra geheugen
  2. BVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  3. CGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart
  4. DHij slaat sleutels ongeordend op
8.Moeilijk

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

  1. AO(n²)
  2. BO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
  3. CPrecies O(log n)
  4. DO(n)

Antwoordenblad

  1. 1. D · Geeft het bovenste element terug zonder het te verwijderen
  2. 2. C · Een graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  3. 3. A · Het aantal kanten van de wortel tot die knoop
  4. 4. B · O(V + E)
  5. 5. C · (i + 1) mod n
  6. 6. A · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  7. 7. B · Verwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  8. 8. B · O(α(n)), de inverse Ackermann-functie, die in de praktijk constant is

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