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 in een ongerichte graaf de graad van een knoop?

  1. AHet aantal knopen in de graaf
  2. BHet aantal kanten dat ermee verbonden is
  3. CDe lengte van het langste pad vanaf die knoop
  4. DDe positie in de adjacency list
2.Makkelijk

Wat is een gewogen graaf?

  1. AEen graaf met meer kanten dan knopen
  2. BEen graaf die op schijf is opgeslagen
  3. CEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
  4. DEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
3.Makkelijk

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

  1. AEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
  2. BEen statische array geeft tragere toegang via de index
  3. CEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  4. DEen statische array kan alleen getallen opslaan
4.Gemiddeld

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

  1. AO(n)
  2. BO(log n)
  3. CO(n log n)
  4. DO(1)
5.Gemiddeld

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

  1. AO(n)
  2. BO(1)
  3. CO(n²)
  4. DO(log n)
6.Gemiddeld

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

  1. Ai + 1
  2. B(i − 1) mod n
  3. C(i + 1) mod n
  4. D2i + 1
7.Moeilijk

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

  1. AO(log n)
  2. BO(1 + α), waarbij α = n / m
  3. CO(m)
  4. DO(n)
8.Moeilijk

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

  1. ABits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
  2. BDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  3. CVerwijderen zou het percentage fout-positieven naar 100% verhogen
  4. DBloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn

Antwoordenblad

  1. 1. B · Het aantal kanten dat ermee verbonden is
  2. 2. D · Een graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  3. 3. C · Een dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  4. 4. B · O(log n)
  5. 5. B · O(1)
  6. 6. C · (i + 1) mod n
  7. 7. B · O(1 + α), waarbij α = n / m
  8. 8. B · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken

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