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 is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

  1. AGraaf
  2. BWachtrij (queue)
  3. CStapel (stack)
  4. DHash-set
2.Makkelijk

Wat is de max-heap-eigenschap?

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

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

  1. AHet element op index i benaderen
  2. BInvoegen aan de kop
  3. CHet eerste element lezen
  4. DHet kopelement verwijderen
4.Gemiddeld

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

  1. AO(n²)
  2. BO(log n)
  3. CO(1)
  4. DO(n)
5.Gemiddeld

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

  1. AEen gesorteerde array
  2. BEen dubbel gekoppelde lijst
  3. CEen dynamische array
  4. DEen enkelvoudig gekoppelde lijst
6.Gemiddeld

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

  1. AAltijd zijn ouder
  2. BDe meest rechtse knoop van zijn linkersubboom
  3. CAltijd zijn rechterkind
  4. DDe meest linkse knoop van zijn rechtersubboom
7.Moeilijk

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

  1. AEen stack van alle bezochte kanten
  2. BEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
  3. CEen max-heap geordend op uitgraad
  4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0
8.Moeilijk

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

  1. AElementen op elke positie invoegen
  2. BDe array sorteren en binair zoeken
  3. CDe mediaan vinden in O(1)
  4. DPrefixsomquery's en updates van één element

Antwoordenblad

  1. 1. C · Stapel (stack)
  2. 2. D · De sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  3. 3. A · Het element op index i benaderen
  4. 4. C · O(1)
  5. 5. B · Een dubbel gekoppelde lijst
  6. 6. D · De meest linkse knoop van zijn rechtersubboom
  7. 7. D · Een queue (of een willekeurige verzameling) van knopen met ingraad 0
  8. 8. D · Prefixsomquery's en updates van één element

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