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 bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

  1. AHet laatste element via de index lezen
  2. BHet 5e element benaderen
  3. CDe lengte van een array met vaste grootte bepalen
  4. DInvoegen aan het begin
2.Makkelijk

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

  1. AHet kopelement verwijderen
  2. BHet eerste element lezen
  3. CInvoegen aan de kop
  4. DHet element op index i benaderen
3.Makkelijk

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

  1. AEen heap
  2. BEen stack
  3. CEen ongeordende enkelvoudig gekoppelde lijst
  4. DEen string
4.Gemiddeld

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

  1. A2i en 2i + 1
  2. B2i + 1 en 2i + 2
  3. Ci + 1 en i + 2
  4. Di/2 en i/2 + 1
5.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. AVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
  2. BPlaats het in de wortel en laat het omlaag zakken (sift down)
  3. CBouw de hele heap opnieuw op
  4. DPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
6.Gemiddeld

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

  1. AHeaps bevatten nooit meer dan 100 elementen
  2. BHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
  3. CAlle sleutels in een heap zijn gelijk
  4. DArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
7.Moeilijk

Een AVL-knoop is ongebalanceerd omdat de rechtersubboom van zijn linkerkind te hoog werd (left-right-geval). Welke correctie wordt toegepast?

  1. AEen enkele rechtsrotatie bij de knoop
  2. BEen enkele linksrotatie bij de knoop
  3. CEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  4. DEen rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
8.Moeilijk

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

  1. AHet opnieuw kleuren van de knoop en zijn kind
  2. BEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
  3. CEen enkele linksrotatie bij de ongebalanceerde knoop
  4. DEen enkele rechtsrotatie bij de ongebalanceerde knoop

Antwoordenblad

  1. 1. D · Invoegen aan het begin
  2. 2. D · Het element op index i benaderen
  3. 3. A · Een heap
  4. 4. B · 2i + 1 en 2i + 2
  5. 5. D · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  6. 6. B · Het is een complete binaire boom, dus posities volgen eenvoudige indexformules
  7. 7. C · Een linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
  8. 8. D · Een enkele rechtsrotatie bij de ongebalanceerde knoop

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