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 is een deque (double-ended queue)?

  1. ATwee aparte queues die één array delen
  2. BEen queue die alleen verwijderen achteraan toestaat
  3. CEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
  4. DEen queue gesorteerd op prioriteit
2.Makkelijk

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AEen knoop en zijn ouder
  2. BKnopen op dezelfde diepte in verschillende subbomen
  3. CKnopen zonder kinderen
  4. DKnopen die dezelfde ouder hebben
3.Makkelijk

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

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

Wat geldt voor de adjacency matrix van een ongerichte graaf?

  1. AZe is symmetrisch ten opzichte van de hoofddiagonaal
  2. BZe is altijd bovendriehoeks
  3. CHaar hoofddiagonaal bevat altijd enen
  4. DElke rij heeft precies één 1
5.Gemiddeld

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

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

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

  1. AZoeken op prefix, zoals automatisch aanvullen
  2. BMatrices opslaan
  3. CKortste paden vinden
  4. DGetallen sorteren
7.Moeilijk

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

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

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

  1. AEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  2. BHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  3. CDe map geeft een fout op het moment dat het veld verandert
  4. DDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket

Antwoordenblad

  1. 1. C · Een structuur die invoegen en verwijderen aan beide uiteinden toestaat
  2. 2. D · Knopen die dezelfde ouder hebben
  3. 3. C · Een lijst van de buurknopen
  4. 4. A · Ze is symmetrisch ten opzichte van de hoofddiagonaal
  5. 5. B · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  6. 6. A · Zoeken op prefix, zoals automatisch aanvullen
  7. 7. B · Een queue (of een willekeurige verzameling) van knopen met ingraad 0
  8. 8. B · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat

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