Werkblad Datastructuren met antwoorden

Hoeveel kanten heeft een boom met n knopen?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

In welke volgorde bezoekt een preorder-doorloop van een binaire boom de knopen?

1. ANiveau voor niveau vanaf de bovenkant
2. BKnoop, dan linkersubboom, dan rechtersubboom
3. CLinkersubboom, dan rechtersubboom, dan knoop
4. DLinkersubboom, dan knoop, dan rechtersubboom

Wat is de wortel van een boom?

1. AEen willekeurige knoop in het midden
2. BDe knoop met de grootste waarde
3. CDe bovenste knoop zonder ouder
4. DEen knoop zonder kinderen

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

1. AO(log n)
2. BO(n²)
3. CO(1)
4. DO(n)

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

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

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

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

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

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij voegt ketens van knopen met één kind samen tot één kant met een string als label
2. BHij sorteert de kinderen van elke knoop op frequentie
3. CHij bewaart alleen de eerste letter van elk woord
4. DHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen