Werkblad Datastructuren met antwoorden

De diepte van een knoop in een boom is:

1. AHet aantal knopen in zijn subboom
2. BHet aantal kanten van de wortel tot die knoop
3. CHet aantal kinderen van die knoop
4. DHet aantal kanten van die knoop tot het diepste blad

Hoe heet de stackbewerking die een element bovenaan toevoegt?

1. APush
2. BEnqueue
3. CPop
4. DPeek

Welke datastructuur is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

1. AGraaf
2. BWachtrij (queue)
3. CStapel (stack)
4. DHash-set

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

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

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. BAlle sleutels in een heap zijn gelijk
3. CHeaps bevatten nooit meer dan 100 elementen
4. DHet is een complete binaire boom, dus posities volgen eenvoudige indexformules

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

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

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

1. AEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
2. BEen gesorteerde array van alle n waarden
3. CEen FIFO-queue van de laatste k waarden
4. DEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

1. AEen max-heap geordend op uitgraad
2. BEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
3. CEen stack van alle bezochte kanten
4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0