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

Hoeveel kanten heeft een boom met n knopen?

  1. An
  2. Bn + 1
  3. Cn − 1
  4. D2n
2.Makkelijk

Wat is een deque (double-ended queue)?

  1. AEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
  2. BTwee aparte queues die één array delen
  3. CEen queue die alleen verwijderen achteraan toestaat
  4. DEen queue gesorteerd op prioriteit
3.Makkelijk

Wat is de wortel van een boom?

  1. ADe knoop met de grootste waarde
  2. BEen willekeurige knoop in het midden
  3. CDe bovenste knoop zonder ouder
  4. DEen knoop zonder kinderen
4.Gemiddeld

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

  1. AAltijd zijn ouder
  2. BDe meest linkse knoop van zijn rechtersubboom
  3. CDe meest rechtse knoop van zijn linkersubboom
  4. DAltijd zijn rechterkind
5.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

  1. ADe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  2. BBeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
  3. CElke knoop is rood of zwart gekleurd
  4. DAlle bladeren liggen op precies dezelfde diepte
6.Gemiddeld

Welke datastructuur gebruikt diepte-eerst zoeken (DFS) in de iteratieve versie?

  1. AAlleen een hashtabel
  2. BEen stack
  3. CEen queue
  4. DEen heap
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. BBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
  3. CVerwijderen zou het percentage fout-positieven naar 100% verhogen
  4. DDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
8.Moeilijk

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

  1. AEen gesorteerde array van alle n waarden
  2. BEen FIFO-queue van de laatste k waarden
  3. CEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  4. DEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Antwoordenblad

  1. 1. C · n − 1
  2. 2. A · Een structuur die invoegen en verwijderen aan beide uiteinden toestaat
  3. 3. C · De bovenste knoop zonder ouder
  4. 4. B · De meest linkse knoop van zijn rechtersubboom
  5. 5. A · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  6. 6. B · Een stack
  7. 7. D · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  8. 8. D · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

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