Werkblad Datastructuren met antwoorden

Wat slaat een map (dictionary) op?

1. ASleutel-waardeparen met unieke sleutels
2. BParen van gelijke sleutels
3. CWaarden gesorteerd op grootte
4. DAlleen waarden in volgorde van invoegen

Wat doet de bewerking peek (of top) op een stack?

1. AGeeft het onderste element van de stack terug
2. BVerwijdert het bovenste element en geeft het terug
3. CVerwijdert alle elementen van de stack
4. DGeeft het bovenste element terug zonder het te verwijderen

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet aantal knopen in de lijst
2. BNull (geen knoop)
3. CHet adres van de vorige knoop
4. DHet adres van de eerste knoop

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

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D4 5 2 3 1

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

1. ADe meest linkse knoop van zijn rechtersubboom
2. BDe meest rechtse knoop van zijn linkersubboom
3. CAltijd zijn ouder
4. DAltijd zijn rechterkind

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AInvoegvolgorde
2. BAltijd aflopende volgorde
3. CVolgorde per niveau
4. DOplopend gesorteerde volgorde

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

1. AHij gebruikt geen extra geheugen
2. BGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart
3. CVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
4. DHij slaat sleutels ongeordend op

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

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