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

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

1. AEen ongeordende enkelvoudig gekoppelde lijst
2. BEen heap
3. CEen string
4. DEen stack

Wat is een botsing (collision) in een hashtabel?

1. ADe tabel heeft geen geheugen meer
2. BTwee verschillende sleutels worden op dezelfde index afgebeeld
3. CEen sleutel kan helemaal niet worden gehasht
4. DTwee gelijke sleutels worden twee keer opgeslagen

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

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

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

1. AOp index 2i + 1
2. BOp index i − 1
3. COp index ⌊i / 2⌋ + 1
4. DOp index ⌊(i − 1) / 2⌋

Welke datastructuur wordt gebruikt om te controleren of de haakjes in "{[()]}" in balans zijn?

1. AEen stack
2. BEen binaire zoekboom
3. CEen queue
4. DEen hashtabel

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

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

Welke uitspraak over heapsort is juist?

1. AHet draait op elke invoer in O(n) tijd
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
4. DHet is stabiel en heeft O(n) extra geheugen nodig