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

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

  1. AGekoppelde lijst
  2. BHashtabel
  3. CStapel (stack)
  4. DWachtrij (queue)
2.Makkelijk

Wat bevat elke knoop in een dubbel gekoppelde lijst?

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

Wat doet de bewerking peek (of top) op een stack?

  1. AGeeft het onderste element van de stack terug
  2. BVerwijdert alle elementen van de stack
  3. CVerwijdert het bovenste element en geeft het terug
  4. DGeeft het bovenste element terug zonder het te verwijderen
4.Gemiddeld

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

  1. AZoeken op prefix, zoals automatisch aanvullen
  2. BMatrices opslaan
  3. CGetallen sorteren
  4. DKortste paden vinden
5.Gemiddeld

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

  1. A1
  2. B0,5
  3. C2
  4. DEr is geen maximum
6.Gemiddeld

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

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

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

  1. AO(n)
  2. BO(1)
  3. CO(log n)
  4. DO(α(n))
8.Moeilijk

Waarom wordt verwijderen in een hashtabel met open adressering vaak gedaan met een "tombstone"-markering?

  1. ATombstones versnellen het hashen
  2. BVerwijderde sleutels moeten om veiligheidsredenen voor altijd bewaard blijven, dus plekken kunnen nooit hergebruikt worden
  3. CHet leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken
  4. DHet maakt de tabel gesorteerd

Antwoordenblad

  1. 1. C · Stapel (stack)
  2. 2. B · Data, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  3. 3. D · Geeft het bovenste element terug zonder het te verwijderen
  4. 4. A · Zoeken op prefix, zoals automatisch aanvullen
  5. 5. A · 1
  6. 6. D · O(log n)
  7. 7. A · O(n)
  8. 8. C · Het leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken

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