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

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

  1. AKnoop, dan linkersubboom, dan rechtersubboom
  2. BNiveau voor niveau vanaf de bovenkant
  3. CLinkersubboom, dan knoop, dan rechtersubboom
  4. DLinkersubboom, dan rechtersubboom, dan knoop
2.Makkelijk

Wat is de bezettingsgraad (load factor) van een hashtabel?

  1. AHet aantal opgeslagen elementen gedeeld door het aantal buckets
  2. BDe tijd die nodig is om de tabel van schijf te laden
  3. CHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
  4. DHet aantal botsingen tot nu toe
3.Makkelijk

Een hashtabel slaat data op als:

  1. ASleutel-waardeparen die via een hashfunctie worden gevonden
  2. BEen boom met geordende sleutels
  3. CEen string met vaste lengte
  4. DUitsluitend een gesorteerde lijst
4.Gemiddeld

Een trie (prefixboom) is bijzonder efficiënt voor:

  1. AMatrices opslaan
  2. BZoeken op prefix, zoals automatisch aanvullen
  3. CGetallen sorteren
  4. DKortste paden vinden
5.Gemiddeld

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

  1. ASeparate chaining (ketenen)
  2. BKwadratisch proberen (quadratic probing)
  3. CDubbel hashen (double hashing)
  4. DLineair proberen (linear probing)
6.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. A70
  2. B20
  3. C40
  4. D50
7.Moeilijk

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

  1. APrefixsomquery's en updates van één element
  2. BDe mediaan vinden in O(1)
  3. CDe array sorteren en binair zoeken
  4. DElementen op elke positie invoegen
8.Moeilijk

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

  1. AEen gesorteerde array van alle n waarden
  2. BEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  3. CEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
  4. DEen FIFO-queue van de laatste k waarden

Antwoordenblad

  1. 1. A · Knoop, dan linkersubboom, dan rechtersubboom
  2. 2. A · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  3. 3. A · Sleutel-waardeparen die via een hashfunctie worden gevonden
  4. 4. B · Zoeken op prefix, zoals automatisch aanvullen
  5. 5. A · Separate chaining (ketenen)
  6. 6. B · 20
  7. 7. A · Prefixsomquery's en updates van één element
  8. 8. C · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

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