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

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Wat is een cykel in een graaf?

  1. AEen pad dat elke knoop bezoekt
  2. BEen kant met gewicht nul
  3. CEen knoop zonder kanten
  4. DEen pad dat begint en eindigt in dezelfde knoop
3.Makkelijk

Hoe heet de stackbewerking die een element bovenaan toevoegt?

  1. APop
  2. BEnqueue
  3. CPeek
  4. DPush
4.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

  1. AElke knoop is rood of zwart gekleurd
  2. BDe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  3. CBeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
  4. DAlle bladeren liggen op precies dezelfde diepte
5.Gemiddeld

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

  1. AO(n)
  2. BO(n²)
  3. CO(log n)
  4. DO(1)
6.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. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  3. CArrays gebruiken minder instructies om waarden te vergelijken
  4. DGekoppelde lijsten slaan elementen altijd op schijf op
7.Moeilijk

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

  1. AEen stack te implementeren
  2. BStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
  3. CDe kanten van een graaf op te slaan
  4. DBereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
8.Moeilijk

Een AVL-knoop is ongebalanceerd omdat de rechtersubboom van zijn linkerkind te hoog werd (left-right-geval). Welke correctie wordt toegepast?

  1. AEen enkele linksrotatie bij de knoop
  2. BEen enkele rechtsrotatie bij de knoop
  3. CEen rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
  4. DEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop

Antwoordenblad

  1. 1. C · Het aantal kanten op het langste pad van de wortel naar een blad
  2. 2. D · Een pad dat begint en eindigt in dezelfde knoop
  3. 3. D · Push
  4. 4. B · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  5. 5. D · O(1)
  6. 6. B · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  7. 7. D · Bereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
  8. 8. D · Een linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop

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