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 deque (double-ended queue)?

  1. AEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
  2. BEen queue gesorteerd op prioriteit
  3. CTwee aparte queues die één array delen
  4. DEen queue die alleen verwijderen achteraan toestaat
2.Makkelijk

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

  1. AHet aantal bladeren in de boom
  2. BHet aantal kanten op het langste pad van de wortel naar een blad
  3. CHet aantal kinderen van de wortel
  4. DHet totale aantal knopen in de boom, inclusief de wortel en elk blad
3.Makkelijk

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

  1. AHet element op index i benaderen
  2. BInvoegen aan de kop
  3. CHet kopelement verwijderen
  4. DHet eerste element lezen
4.Gemiddeld

Een trie (prefixboom) is bijzonder efficiënt voor:

  1. AZoeken op prefix, zoals automatisch aanvullen
  2. BMatrices opslaan
  3. CGetallen sorteren
  4. DKortste paden vinden
5.Gemiddeld

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

  1. AVerwijder het laatste element van de array
  2. BVerwijder de wortel en schuif alle elementen één plaats naar links
  3. CVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  4. DZoek in alle bladeren naar het nieuwe minimum
6.Gemiddeld

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

  1. Ai + 1
  2. B2i + 1
  3. C(i − 1) mod n
  4. D(i + 1) mod n
7.Moeilijk

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

  1. AOm de array gesorteerd te houden
  2. BOmdat halveren bij de helft elementen zou kwijtraken
  3. COm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  4. DOmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
8.Moeilijk

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

  1. ADe hoogte is hoogstens n / 2
  2. BDe hoogte is precies log2 n
  3. CDe hoogte is hoogstens 2 log2(n + 1)
  4. DDe hoogte is hoogstens log2 n + 1

Antwoordenblad

  1. 1. A · Een structuur die invoegen en verwijderen aan beide uiteinden toestaat
  2. 2. B · Het aantal kanten op het langste pad van de wortel naar een blad
  3. 3. A · Het element op index i benaderen
  4. 4. A · Zoeken op prefix, zoals automatisch aanvullen
  5. 5. C · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  6. 6. D · (i + 1) mod n
  7. 7. C · Om herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  8. 8. C · De hoogte is hoogstens 2 log2(n + 1)

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