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 doet de bewerking peek (of top) op een stack?

  1. AVerwijdert alle elementen van de stack
  2. BVerwijdert het bovenste element en geeft het terug
  3. CGeeft het onderste element van de stack terug
  4. DGeeft het bovenste element terug zonder het te verwijderen
2.Makkelijk

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

  1. AKnoop, dan linkersubboom, dan rechtersubboom
  2. BLinkersubboom, dan knoop, dan rechtersubboom
  3. CRechtersubboom, dan knoop, dan linkersubboom
  4. DLinkersubboom, dan rechtersubboom, dan knoop
3.Makkelijk

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

  1. ABinaire boom
  2. BStapel (stack)
  3. CWachtrij (queue)
  4. DHeap
4.Gemiddeld

Hoe werkt extract-min in een binaire min-heap?

  1. AVerwijder de wortel en schuif alle elementen één plaats naar links
  2. BVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  3. CVerwijder het laatste element van de array
  4. DZoek in alle bladeren naar het nieuwe minimum
5.Gemiddeld

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

  1. ADe bestaande sleutels worden ter plaatse gesorteerd
  2. BDe oudste sleutels worden verwijderd om ruimte te maken
  3. CAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
  4. DEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
6.Gemiddeld

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

  1. AEen FIFO-queue
  2. BEen set zonder ordening
  3. CEen min-prioriteitswachtrij
  4. DEen stack
7.Moeilijk

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

  1. AEen min-heap die voor elk venster opnieuw wordt opgebouwd
  2. BEen enkelvoudig gekoppelde lijst van de elementen in het venster
  3. CEen gesorteerde array die door verschuiven wordt bijgewerkt
  4. DEen deque met indices in afnemende volgorde van waarde
8.Moeilijk

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

  1. AOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt
  2. BOm het vergroten van de tabel overbodig te maken
  3. COm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
  4. DOm de hashtabel gesorteerd te maken

Antwoordenblad

  1. 1. D · Geeft het bovenste element terug zonder het te verwijderen
  2. 2. D · Linkersubboom, dan rechtersubboom, dan knoop
  3. 3. C · Wachtrij (queue)
  4. 4. B · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  5. 5. D · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  6. 6. C · Een min-prioriteitswachtrij
  7. 7. D · Een deque met indices in afnemende volgorde van waarde
  8. 8. C · Om het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen

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