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 gerichte graaf?

  1. AEen graaf waarin elk paar verschillende knopen door een kant verbonden is
  2. BEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  3. CEen graaf waarvan alle kanten een gewicht hebben
  4. DEen graaf zonder cykels
2.Makkelijk

Een hashtabel slaat data op als:

  1. AUitsluitend een gesorteerde lijst
  2. BEen boom met geordende sleutels
  3. CEen string met vaste lengte
  4. DSleutel-waardeparen die via een hashfunctie worden gevonden
3.Makkelijk

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

  1. AZe slaat elementen gesorteerd op
  2. BZe slaat sleutel-waardeparen op
  3. CZe slaat elementen op zonder duplicaten
  4. DZe staat alleen toegang aan één uiteinde toe
4.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. C2i + 1
  4. D(i + 1) mod n
5.Gemiddeld

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

  1. AGekoppelde lijsten slaan elementen altijd op schijf op
  2. BEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
  3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  4. DArrays gebruiken minder instructies om waarden te vergelijken
6.Gemiddeld

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

  1. AO(E)
  2. BO(log V)
  3. CO(1)
  4. DO(V)
7.Moeilijk

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

  1. AHet opnieuw kleuren van de knoop en zijn kind
  2. BEen enkele rechtsrotatie bij de ongebalanceerde knoop
  3. CEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
  4. DEen enkele linksrotatie bij de ongebalanceerde knoop
8.Moeilijk

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

  1. APrecies O(log n)
  2. BO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
  3. CO(n²)
  4. DO(n)

Antwoordenblad

  1. 1. B · Een graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  2. 2. D · Sleutel-waardeparen die via een hashfunctie worden gevonden
  3. 3. C · Ze slaat elementen op zonder duplicaten
  4. 4. D · (i + 1) mod n
  5. 5. C · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  6. 6. C · O(1)
  7. 7. B · Een enkele rechtsrotatie bij de ongebalanceerde knoop
  8. 8. B · O(α(n)), de inverse Ackermann-functie, die in de praktijk constant is

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