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 definieert een binaire boom?

  1. AElke knoop heeft precies twee kinderen
  2. BElke knoop heeft hoogstens twee kinderen
  3. CDe boom heeft precies twee niveaus
  4. DElke knoop slaat een binair getal op
2.Makkelijk

Wat is een deque (double-ended queue)?

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

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

  1. APrioriteitswachtrij
  2. BQueue
  3. CHashtabel
  4. DStack
4.Gemiddeld

AVL-bomen en rood-zwartbomen garanderen:

  1. AZoeken in constante tijd in elk geval
  2. BDat sleutels in invoegvolgorde worden opgeslagen
  3. CEen hoogte van O(log n) door herbalancering
  4. DDat geen enkele knoop twee kinderen heeft
5.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. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
  2. BGekoppelde lijsten slaan elementen altijd op schijf op
  3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  4. DArrays gebruiken minder instructies om waarden te vergelijken
6.Gemiddeld

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

  1. AOp index i − 1
  2. BOp index ⌊(i − 1) / 2⌋
  3. COp index 2i + 1
  4. DOp index ⌊i / 2⌋ + 1
7.Moeilijk

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

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

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

  1. AEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  2. BDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
  3. CHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  4. DDe map geeft een fout op het moment dat het veld verandert

Antwoordenblad

  1. 1. B · Elke knoop heeft hoogstens twee kinderen
  2. 2. C · Een structuur die invoegen en verwijderen aan beide uiteinden toestaat
  3. 3. B · Queue
  4. 4. C · Een hoogte van O(log n) door herbalancering
  5. 5. C · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  6. 6. B · Op index ⌊(i − 1) / 2⌋
  7. 7. A · Verwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  8. 8. C · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat

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