Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Welke datastructuur wordt gebruikt voor een level-order-doorloop van een boom?

1. AStack
2. BHashtabel
3. CQueue
4. DPrioriteitswachtrij

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. APush
2. BInsert
3. CEnqueue
4. DDequeue

Welke datastructuur wordt gebruikt om te controleren of de haakjes in "{[()]}" in balans zijn?

1. AEen stack
2. BEen hashtabel
3. CEen binaire zoekboom
4. DEen queue

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AHaar hoofddiagonaal bevat altijd enen
2. BZe is symmetrisch ten opzichte van de hoofddiagonaal
3. CZe is altijd bovendriehoeks
4. DElke rij heeft precies één 1

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

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

Welke uitspraak over heapsort is juist?

1. AHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet draait op elke invoer in O(n) tijd
4. DHet is stabiel en heeft O(n) extra geheugen nodig

Aan welke eigenschap moet een rood-zwartboom voldoen?

1. ADe wortel moet rood zijn
2. BElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
3. CElke knoop moet rood zijn
4. DRode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren