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 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
2.Makkelijk

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

  1. AHet totale aantal knopen in de boom, inclusief de wortel en elk blad
  2. BHet aantal bladeren in de boom
  3. CHet aantal kinderen van de wortel
  4. DHet aantal kanten op het langste pad van de wortel naar een blad
3.Makkelijk

Hoe heet de queuebewerking die het element vooraan verwijdert?

  1. AInsert
  2. BPush
  3. CDequeue
  4. DEnqueue
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 postorder-doorloop?

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

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

  1. ADe oudste sleutels worden verwijderd om ruimte te maken
  2. BAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
  3. CEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  4. DDe bestaande sleutels worden ter plaatse gesorteerd
6.Gemiddeld

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

  1. AO(V × E)
  2. BO(V²)
  3. CO(E²)
  4. DO(V + E)
7.Moeilijk

Aan welke eigenschap moet een rood-zwartboom voldoen?

  1. AElke knoop moet rood zijn
  2. BDe wortel moet rood zijn
  3. CRode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
  4. DElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
8.Moeilijk

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

  1. ADe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
  2. BHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
  3. CDe hele subboom te verwijderen
  4. DHem te verwisselen met de wortel

Antwoordenblad

  1. 1. D · De sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  2. 2. D · Het aantal kanten op het langste pad van de wortel naar een blad
  3. 3. C · Dequeue
  4. 4. D · 4 5 2 3 1
  5. 5. C · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  6. 6. D · O(V + E)
  7. 7. D · Elk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  8. 8. B · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen

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