Werkblad Datastructuren met antwoorden

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

1. ALinkersubboom, dan rechtersubboom, dan knoop
2. BLinkersubboom, dan knoop, dan rechtersubboom
3. CKnoop, dan linkersubboom, dan rechtersubboom
4. DRechtersubboom, dan knoop, dan linkersubboom

Wat is een deque (double-ended queue)?

1. AEen queue die alleen verwijderen achteraan toestaat
2. BTwee aparte queues die één array delen
3. CEen queue gesorteerd op prioriteit
4. DEen structuur die invoegen en verwijderen aan beide uiteinden toestaat

Wat zijn broer- of zusknopen (siblings) in een boom?

1. AKnopen zonder kinderen
2. BKnopen op dezelfde diepte in verschillende subbomen
3. CKnopen die dezelfde ouder hebben
4. DEen knoop en zijn ouder

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

1. AOp index ⌊(i − 1) / 2⌋
2. BOp index 2i + 1
3. COp index ⌊i / 2⌋ + 1
4. DOp index i − 1

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

1. AAltijd zijn rechterkind
2. BAltijd zijn ouder
3. CDe meest rechtse knoop van zijn linkersubboom
4. DDe meest linkse knoop van zijn rechtersubboom

Welke datastructuur gebruikt een draaiend programma om actieve functieaanroepen en hun lokale variabelen bij te houden?

1. AEen hashtabel van functies
2. BDe call stack
3. CDe wachtrij van het heapgeheugen
4. DEen binaire zoekboom van frames

Waarom wordt verwijderen in een hashtabel met open adressering vaak gedaan met een "tombstone"-markering?

1. ATombstones versnellen het hashen
2. BVerwijderde sleutels moeten om veiligheidsredenen voor altijd bewaard blijven, dus plekken kunnen nooit hergebruikt worden
3. CHet maakt de tabel gesorteerd
4. DHet leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken

Hoe lang duurt het zoeken naar een willekeurige sleutel in een binaire min-heap van n elementen?

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