Werkblad Datastructuren met antwoorden

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

1. AHet totale aantal kanten in de graaf
2. BEen rij van V Booleaanse waarden
3. CHet kortste pad naar elke andere knoop
4. DEen lijst van de buurknopen

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

1. AWachtrij (queue)
2. BStapel (stack)
3. CHashtabel
4. DGekoppelde lijst

De diepte van een knoop in een boom is:

1. AHet aantal kinderen van die knoop
2. BHet aantal kanten van die knoop tot het diepste blad
3. CHet aantal knopen in zijn subboom
4. DHet aantal kanten van de wortel tot die knoop

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(1), omdat de index bekend is
2. BO(n²), omdat elk element n keer verschuift
3. CO(log n), vanwege binair zoeken
4. DO(n), omdat latere elementen moeten opschuiven

Hoe vind je de kleinste sleutel in een binaire zoekboom?

1. ABezoek elk blad en vergelijk ze
2. BVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
3. CKijk alleen naar de wortel
4. DVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is

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 + 1 en 2i + 2
2. B2i en 2i + 1
3. Ci + 1 en i + 2
4. Di/2 en i/2 + 1

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is precies log₂ n
2. BDe hoogte is hoogstens n / 2
3. CDe hoogte is hoogstens log₂ n + 1
4. DDe hoogte is hoogstens 2 log₂(n + 1)

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

1. AOm de hashtabel gesorteerd te maken
2. BOm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
3. COm het vergroten van de tabel overbodig te maken
4. DOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt