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 wordt gebruikt voor een level-order-doorloop van een boom?

  1. AStack
  2. BHashtabel
  3. CPrioriteitswachtrij
  4. DQueue
2.Makkelijk

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

  1. AVerwijdert het bovenste element en geeft het terug
  2. BVerwijdert alle elementen van de stack
  3. CGeeft het onderste element van de stack terug
  4. DGeeft het bovenste element terug zonder het te verwijderen
3.Makkelijk

In welke volgorde bezoekt een postorder-doorloop van een binaire boom de knopen?

  1. ARechtersubboom, dan knoop, dan linkersubboom
  2. BLinkersubboom, dan rechtersubboom, dan knoop
  3. CKnoop, dan linkersubboom, dan rechtersubboom
  4. DLinkersubboom, dan knoop, dan rechtersubboom
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. Alog₂ n
  2. B1
  3. Cn (hij wordt een gekoppelde lijst)
  4. D√n
5.Gemiddeld

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

  1. AAltijd aflopende volgorde
  2. BInvoegvolgorde
  3. CVolgorde per niveau
  4. DOplopend gesorteerde volgorde
6.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 ongesorteerde gekoppelde lijst
  2. BEen gebalanceerde binaire zoekboom
  3. CEen hashtabel
  4. DEen stack
7.Moeilijk

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

  1. ABloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
  2. BVerwijderen zou het percentage fout-positieven naar 100% verhogen
  3. CDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  4. DBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
8.Moeilijk

Welke uitspraak over heapsort is juist?

  1. AHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
  2. BHet is stabiel en heeft O(n) extra geheugen nodig
  3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
  4. DHet draait op elke invoer in O(n) tijd

Antwoordenblad

  1. 1. D · Queue
  2. 2. D · Geeft het bovenste element terug zonder het te verwijderen
  3. 3. B · Linkersubboom, dan rechtersubboom, dan knoop
  4. 4. C · n (hij wordt een gekoppelde lijst)
  5. 5. D · Oplopend gesorteerde volgorde
  6. 6. B · Een gebalanceerde binaire zoekboom
  7. 7. C · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  8. 8. C · Het sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel

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