Werkblad Datastructuren met antwoorden

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

1. AEen rij van V Booleaanse waarden
2. BHet totale aantal kanten in de graaf
3. CEen lijst van de buurknopen
4. DHet kortste pad naar elke andere knoop

Wat doet een hashfunctie in een hashtabel?

1. ATelt hoeveel sleutels er zijn opgeslagen
2. BVersleutelt de waarden in de tabel
3. CBeeldt een sleutel af op een index in de tabel
4. DSorteert de sleutels in de tabel

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

1. AZe staat alleen toegang aan één uiteinde toe
2. BZe slaat elementen gesorteerd op
3. CZe slaat elementen op zonder duplicaten
4. DZe slaat sleutel-waardeparen op

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

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

Hoe wordt een nieuw element in een binaire heap ingevoegd?

1. APlaats het in de wortel en laat het omlaag zakken (sift down)
2. BPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
3. CBouw de hele heap opnieuw op
4. DVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
2. BArrays gebruiken minder instructies om waarden te vergelijken
3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
4. DGekoppelde lijsten slaan elementen altijd op schijf op

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 gesorteerde array van alle n waarden
2. BEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
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

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

1. AMaak de buffergrootte een macht van twee
2. BHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt
3. CSla front en rear op in dezelfde variabele
4. DMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is