Werkblad Datastructuren met antwoorden

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

1. AGroter dan de waarde van de knoop
2. BKleiner dan de waarde van de knoop
3. CGelijk aan de waarde van de knoop
4. DIn willekeurige volgorde

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

Een hashtabel slaat data op als:

1. ASleutel-waardeparen die via een hashfunctie worden gevonden
2. BEen string met vaste lengte
3. CUitsluitend een gesorteerde lijst
4. DEen boom met geordende sleutels

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

1. AEen stack
2. BEen FIFO-queue
3. CEen min-prioriteitswachtrij
4. DEen set zonder ordening

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

1. An (hij wordt een gekoppelde lijst)
2. B1
3. C√n
4. Dlog₂ n

AVL-bomen en rood-zwartbomen garanderen:

1. AEen hoogte van O(log n) door herbalancering
2. BDat sleutels in invoegvolgorde worden opgeslagen
3. CZoeken in constante tijd in elk geval
4. DDat geen enkele knoop twee kinderen heeft

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

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

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

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