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 wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

  1. AEen rij van V Booleaanse waarden
  2. BEen lijst van de buurknopen
  3. CHet kortste pad naar elke andere knoop
  4. DHet totale aantal kanten in de graaf
2.Makkelijk

De diepte van een knoop in een boom is:

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

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AEen knoop en zijn ouder
  2. BKnopen op dezelfde diepte in verschillende subbomen
  3. CKnopen die dezelfde ouder hebben
  4. DKnopen zonder kinderen
4.Gemiddeld

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

  1. AEen stack
  2. BEen min-prioriteitswachtrij
  3. CEen set zonder ordening
  4. DEen FIFO-queue
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(log n)
  2. BO(n²)
  3. CO(1)
  4. DO(n)
6.Gemiddeld

Wat geldt voor de adjacency matrix van een ongerichte graaf?

  1. AHaar hoofddiagonaal bevat altijd enen
  2. BElke rij heeft precies één 1
  3. CZe is symmetrisch ten opzichte van de hoofddiagonaal
  4. DZe is altijd bovendriehoeks
7.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 rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
  3. CEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  4. DEen enkele rechtsrotatie bij de knoop
8.Moeilijk

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

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

Antwoordenblad

  1. 1. B · Een lijst van de buurknopen
  2. 2. D · Het aantal kanten van de wortel tot die knoop
  3. 3. C · Knopen die dezelfde ouder hebben
  4. 4. B · Een min-prioriteitswachtrij
  5. 5. C · O(1)
  6. 6. C · Ze is symmetrisch ten opzichte van de hoofddiagonaal
  7. 7. C · Een linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  8. 8. A · 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.