Werkblad Datastructuren met antwoorden

Hoe worden de elementen van een array in het geheugen opgeslagen?

1. AIn een boom van geheugenpagina's
2. BOp willekeurige plaatsen gekozen door een hash
3. CVerspreid, verbonden door pointers
4. DIn één aaneengesloten blok, na elkaar

In een binaire zoekboom zijn de waarden in de linkersubboom van een knoop:

1. AIn willekeurige volgorde
2. BKleiner dan de waarde van de knoop
3. CGroter dan de waarde van de knoop
4. DGelijk aan de waarde van de knoop

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

1. AWachtrij (queue)
2. BStapel (stack)
3. CHash-set
4. DGraaf

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

1. AEen dynamische array
2. BEen gesorteerde array
3. CEen enkelvoudig gekoppelde lijst
4. DEen dubbel gekoppelde lijst

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

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

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

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

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

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(n)
2. BO(n²)
3. CPrecies O(log n)
4. DO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is