Werkblad Datastructuren met antwoorden

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

1. ALinkersubboom, dan knoop, dan rechtersubboom
2. BRechtersubboom, dan knoop, dan linkersubboom
3. CKnoop, dan linkersubboom, dan rechtersubboom
4. DLinkersubboom, dan rechtersubboom, dan knoop

Wat definieert een binaire boom?

1. AElke knoop slaat een binair getal op
2. BElke knoop heeft hoogstens twee kinderen
3. CElke knoop heeft precies twee kinderen
4. DDe boom heeft precies twee niveaus

Wat is een gerichte graaf?

1. AEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
2. BEen graaf zonder cykels
3. CEen graaf waarin elk paar verschillende knopen door een kant verbonden is
4. DEen graaf waarvan alle kanten een gewicht hebben

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

1. AEen gebalanceerde binaire zoekboom
2. BEen stack
3. CEen ongesorteerde gekoppelde lijst
4. DEen hashtabel

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de preorder-doorloop?

1. A1 2 3 4 5
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Hoe vind je de kleinste sleutel in een binaire zoekboom?

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

Je wilt voor elk element van een array het volgende grotere element rechts ervan vinden, in totaal O(n) tijd. Welke structuur helpt?

1. AEen binaire zoekboom die voor elk element opnieuw wordt opgebouwd
2. BEen stack die elementen bewaart die op hun antwoord wachten
3. CEen queue die elk paar elementen bevat
4. DEen hashtabel van alle elementen

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

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