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 bevat elke knoop in een dubbel gekoppelde lijst?

  1. AData en alleen een pointer naar de volgende knoop
  2. BTwee kopieën van de data en één pointer
  3. CData en twee pointers, één naar de volgende knoop en één naar de knoop daarna
  4. DData, een pointer naar de volgende knoop en een pointer naar de vorige knoop
2.Makkelijk

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

  1. AHashtabel
  2. BStapel (stack)
  3. CGekoppelde lijst
  4. DWachtrij (queue)
3.Makkelijk

In welke volgorde bezoekt een preorder-doorloop van een binaire boom de knopen?

  1. ANiveau voor niveau vanaf de bovenkant
  2. BLinkersubboom, dan rechtersubboom, dan knoop
  3. CKnoop, dan linkersubboom, dan rechtersubboom
  4. DLinkersubboom, dan knoop, dan rechtersubboom
4.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. AGekoppelde lijsten slaan elementen altijd op schijf op
  2. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  3. CArrays gebruiken minder instructies om waarden te vergelijken
  4. DEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
5.Gemiddeld

De sleutels 50, 30, 70, 20, 40 worden in deze volgorde in een lege binaire zoekboom ingevoegd. Wat is het linkerkind van 30?

  1. A50
  2. B40
  3. C70
  4. D20
6.Gemiddeld

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

  1. AEen stack
  2. BEen FIFO-queue
  3. CEen min-prioriteitswachtrij
  4. DEen set zonder ordening
7.Moeilijk

Waarom worden B-bomen gebruikt in databases en bestandssystemen?

  1. AZe hebben geen herbalancering nodig
  2. BZe slaan data ongesorteerd op
  3. CHun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
  4. DZe gebruiken minder geheugen dan welke array dan ook, dus de hele index past altijd in het werkgeheugen
8.Moeilijk

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

  1. ASla elke bezochte knoop op in een hash-set
  2. BVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
  3. CSorteer de lijst en zoek naar duplicaten
  4. DTel de knopen tot het aantal het lengteveld van de lijst overschrijdt

Antwoordenblad

  1. 1. D · Data, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  2. 2. B · Stapel (stack)
  3. 3. C · Knoop, dan linkersubboom, dan rechtersubboom
  4. 4. B · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  5. 5. D · 20
  6. 6. C · Een min-prioriteitswachtrij
  7. 7. C · Hun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
  8. 8. B · Verplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten

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