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

Een hashtabel slaat data op als:

  1. AEen string met vaste lengte
  2. BUitsluitend een gesorteerde lijst
  3. CSleutel-waardeparen die via een hashfunctie worden gevonden
  4. DEen boom met geordende sleutels
2.Makkelijk

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

  1. AWachtrij (queue)
  2. BHashtabel
  3. CGekoppelde lijst
  4. DStapel (stack)
3.Makkelijk

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

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

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

  1. ASeparate chaining (ketenen)
  2. BLineair proberen (linear probing)
  3. CDubbel hashen (double hashing)
  4. DKwadratisch proberen (quadratic probing)
5.Gemiddeld

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

  1. A2i + 1 en 2i + 2
  2. Bi/2 en i/2 + 1
  3. Ci + 1 en i + 2
  4. D2i en 2i + 1
6.Gemiddeld

AVL-bomen en rood-zwartbomen garanderen:

  1. AEen hoogte van O(log n) door herbalancering
  2. BDat geen enkele knoop twee kinderen heeft
  3. CZoeken in constante tijd in elk geval
  4. DDat sleutels in invoegvolgorde worden opgeslagen
7.Moeilijk

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

  1. AO(n) tijd en O(1) extra geheugen
  2. BO(n log n) tijd en O(1) extra geheugen
  3. CO(1) tijd en O(1) extra geheugen
  4. DO(n) tijd en O(n) extra geheugen
8.Moeilijk

In de BST met wortel 50, linkersubboom 30 (kinderen 20, 40) en rechtersubboom 70 (kinderen 60, 80) wordt de wortel verwijderd met behulp van de inorder-opvolger. Welke sleutel wordt de nieuwe wortel?

  1. A60
  2. B40
  3. C80
  4. D70

Antwoordenblad

  1. 1. C · Sleutel-waardeparen die via een hashfunctie worden gevonden
  2. 2. D · Stapel (stack)
  3. 3. D · Een lijst van de buurknopen
  4. 4. A · Separate chaining (ketenen)
  5. 5. A · 2i + 1 en 2i + 2
  6. 6. A · Een hoogte van O(log n) door herbalancering
  7. 7. A · O(n) tijd en O(1) extra geheugen
  8. 8. A · 60

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