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 zijn broer- of zusknopen (siblings) in een boom?

  1. AKnopen op dezelfde diepte in verschillende subbomen
  2. BKnopen die dezelfde ouder hebben
  3. CEen knoop en zijn ouder
  4. DKnopen zonder kinderen
2.Makkelijk

Wat doet een hashfunctie in een hashtabel?

  1. AVersleutelt de waarden in de tabel
  2. BSorteert de sleutels in de tabel
  3. CBeeldt een sleutel af op een index in de tabel
  4. DTelt hoeveel sleutels er zijn opgeslagen
3.Makkelijk

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

  1. AHashtabel
  2. BGekoppelde lijst
  3. CStapel (stack)
  4. DWachtrij (queue)
4.Gemiddeld

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de preorder-doorloop?

  1. A1 2 4 5 3
  2. B4 5 2 3 1
  3. C1 2 3 4 5
  4. D4 2 5 1 3
5.Gemiddeld

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

  1. AOp index 2i + 1
  2. BOp index ⌊i / 2⌋ + 1
  3. COp index ⌊(i − 1) / 2⌋
  4. DOp index i − 1
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(n²), omdat elk element n keer verschuift
  3. CO(1), omdat de index bekend is
  4. DO(log n), vanwege binair zoeken
7.Moeilijk

Waarom worden B-bomen gebruikt in databases en bestandssystemen?

  1. AZe hebben geen herbalancering nodig
  2. BHun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
  3. CZe slaan data ongesorteerd op
  4. DZe gebruiken minder geheugen dan welke array dan ook, dus de hele index past altijd in het werkgeheugen
8.Moeilijk

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

  1. AHij bewaart alleen de eerste letter van elk woord
  2. BHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
  3. CHij sorteert de kinderen van elke knoop op frequentie
  4. DHij voegt ketens van knopen met één kind samen tot één kant met een string als label

Antwoordenblad

  1. 1. B · Knopen die dezelfde ouder hebben
  2. 2. C · Beeldt een sleutel af op een index in de tabel
  3. 3. C · Stapel (stack)
  4. 4. A · 1 2 4 5 3
  5. 5. C · Op index ⌊(i − 1) / 2⌋
  6. 6. A · O(n), omdat latere elementen moeten opschuiven
  7. 7. B · Hun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
  8. 8. D · Hij voegt ketens van knopen met één kind samen tot één kant met een string als label

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