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

Een graaf bestaat uit:

  1. AAlleen sleutels en hashes
  2. BRijen en kolommen
  3. CKnopen (vertices) verbonden door kanten
  4. DAlleen een wortel en bladeren
2.Makkelijk

De diepte van een knoop in een boom is:

  1. AHet aantal kanten van de wortel tot die knoop
  2. BHet aantal kanten van die knoop tot het diepste blad
  3. CHet aantal knopen in zijn subboom
  4. DHet aantal kinderen van die knoop
3.Makkelijk

Wat bevat elke knoop in een dubbel gekoppelde lijst?

  1. AData en alleen een pointer naar de volgende knoop
  2. BData, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  3. CTwee kopieën van de data en één pointer
  4. DData en twee pointers, één naar de volgende knoop en één naar de knoop daarna
4.Gemiddeld

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

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

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

  1. AEen stack
  2. BEen ongesorteerde gekoppelde lijst
  3. CEen hashtabel
  4. DEen gebalanceerde binaire zoekboom
6.Gemiddeld

Wat kost het invoegen van een element in het midden van een array met n elementen?

  1. AO(n), omdat latere elementen moeten opschuiven
  2. BO(1), omdat de index bekend is
  3. CO(n²), omdat elk element n keer verschuift
  4. DO(log n), vanwege binair zoeken
7.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. ADe map geeft een fout op het moment dat het veld verandert
  2. BEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  3. CDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
  4. DHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
8.Moeilijk

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

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

Antwoordenblad

  1. 1. C · Knopen (vertices) verbonden door kanten
  2. 2. A · Het aantal kanten van de wortel tot die knoop
  3. 3. B · Data, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  4. 4. D · O(V²)
  5. 5. D · Een gebalanceerde binaire zoekboom
  6. 6. A · O(n), omdat latere elementen moeten opschuiven
  7. 7. D · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  8. 8. A · 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.