Werkblad Datastructuren met antwoorden

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

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

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

1. AStapel (stack)
2. BWachtrij (queue)
3. CHashtabel
4. DGekoppelde lijst

Hoeveel kanten heeft een boom met n knopen?

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

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A1
2. B0,5
3. CEr is geen maximum
4. D2

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2^h
2. B2^h+1 − 1
3. C2h + 1
4. Dh²

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

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

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

1. ABloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
2. BDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
3. CVerwijderen zou het percentage fout-positieven naar 100% verhogen
4. DBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(n²)
2. BO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
3. CPrecies O(log n)
4. DO(n)