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 de bezettingsgraad (load factor) van een hashtabel?

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

Wat doet een hashfunctie in een hashtabel?

  1. ATelt hoeveel sleutels er zijn opgeslagen
  2. BVersleutelt de waarden in de tabel
  3. CBeeldt een sleutel af op een index in de tabel
  4. DSorteert de sleutels in de tabel
3.Makkelijk

Wat is de max-heap-eigenschap?

  1. ADe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  2. BAlle bladeren bevatten de maximale sleutel
  3. CDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer
  4. DDe sleutels zijn van links naar rechts gesorteerd
4.Gemiddeld

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

  1. A√n
  2. B1
  3. Clog₂ n
  4. Dn (hij wordt een gekoppelde lijst)
5.Gemiddeld

Wat geldt voor de adjacency matrix van een ongerichte graaf?

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

Hoe vind je de kleinste sleutel in een binaire zoekboom?

  1. ABezoek elk blad en vergelijk ze
  2. BVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is
  3. CKijk alleen naar de wortel
  4. DVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
7.Moeilijk

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

  1. ADe kanten van een graaf op te slaan
  2. BStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
  3. CBereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
  4. DEen stack te implementeren
8.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(m)
  3. CO(n)
  4. DO(1 + α), waarbij α = n / m

Antwoordenblad

  1. 1. A · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  2. 2. C · Beeldt een sleutel af op een index in de tabel
  3. 3. A · De sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  4. 4. D · n (hij wordt een gekoppelde lijst)
  5. 5. B · Ze is symmetrisch ten opzichte van de hoofddiagonaal
  6. 6. D · Volg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
  7. 7. C · Bereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
  8. 8. D · O(1 + α), waarbij α = n / m

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