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

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

  1. AEen heap
  2. BEen ongeordende enkelvoudig gekoppelde lijst
  3. CEen stack
  4. DEen string
2.Makkelijk

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

  1. AHet adres van de eerste knoop
  2. BNull (geen knoop)
  3. CHet adres van de vorige knoop
  4. DHet aantal knopen in de lijst
3.Makkelijk

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

  1. AGekoppelde lijst
  2. BStapel (stack)
  3. CHashtabel
  4. DWachtrij (queue)
4.Gemiddeld

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

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

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

  1. A0,5
  2. B1
  3. CEr is geen maximum
  4. D2
7.Moeilijk

Je wilt voor elk element van een array het volgende grotere element rechts ervan vinden, in totaal O(n) tijd. Welke structuur helpt?

  1. AEen stack die elementen bewaart die op hun antwoord wachten
  2. BEen queue die elk paar elementen bevat
  3. CEen hashtabel van alle elementen
  4. DEen binaire zoekboom die voor elk element opnieuw wordt opgebouwd
8.Moeilijk

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

  1. AHem te verwisselen met de wortel
  2. BDe hele subboom te verwijderen
  3. CDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
  4. DHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen

Antwoordenblad

  1. 1. A · Een heap
  2. 2. B · Null (geen knoop)
  3. 3. B · Stapel (stack)
  4. 4. A · O(1)
  5. 5. C · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  6. 6. B · 1
  7. 7. A · Een stack die elementen bewaart die op hun antwoord wachten
  8. 8. D · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen

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