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

Hoe heet de queuebewerking die het element vooraan verwijdert?

  1. ADequeue
  2. BInsert
  3. CPush
  4. DEnqueue
2.Makkelijk

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

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

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

  1. AHet laatste element via de index lezen
  2. BInvoegen aan het begin
  3. CDe lengte van een array met vaste grootte bepalen
  4. DHet 5e element benaderen
4.Gemiddeld

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

  1. AO(V²)
  2. BO(log V)
  3. CO(V + E)
  4. DO(E)
5.Gemiddeld

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

  1. AVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  2. BVerwijder het laatste element van de array
  3. CZoek in alle bladeren naar het nieuwe minimum
  4. DVerwijder de wortel en schuif alle elementen één plaats naar links
6.Gemiddeld

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

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

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

  1. AEen stack van alle bezochte kanten
  2. BEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
  3. CEen max-heap geordend op uitgraad
  4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0
8.Moeilijk

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

  1. ABereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
  2. BEen stack te implementeren
  3. CDe kanten van een graaf op te slaan
  4. DStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan

Antwoordenblad

  1. 1. A · Dequeue
  2. 2. B · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  3. 3. B · Invoegen aan het begin
  4. 4. A · O(V²)
  5. 5. A · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  6. 6. C · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  7. 7. D · Een queue (of een willekeurige verzameling) van knopen met ingraad 0
  8. 8. A · Bereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden

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