Werkblad Datastructuren met antwoorden

Een graaf bestaat uit:

1. AKnopen (vertices) verbonden door kanten
2. BRijen en kolommen
3. CAlleen een wortel en bladeren
4. DAlleen sleutels en hashes

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. AEnqueue
2. BDequeue
3. CInsert
4. DPush

Wat is de max-heap-eigenschap?

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

Hoe vind je de kleinste sleutel in een binaire zoekboom?

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

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AArrays gebruiken minder instructies om waarden te vergelijken
2. BGekoppelde lijsten slaan elementen altijd op schijf op
3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
4. DEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

1. A(i − 1) mod n
2. Bi + 1
3. C(i + 1) mod n
4. D2i + 1

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

1. AMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is
2. BSla front en rear op in dezelfde variabele
3. CMaak de buffergrootte een macht van twee
4. DHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt

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. AEen enkele rechtsrotatie bij de ongebalanceerde knoop
2. BHet opnieuw kleuren van de knoop en zijn kind
3. CEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
4. DEen enkele linksrotatie bij de ongebalanceerde knoop