Werkblad Datastructuren met antwoorden

In welke volgorde bezoekt een postorder-doorloop van een binaire boom de knopen?

1. ALinkersubboom, dan rechtersubboom, dan knoop
2. BLinkersubboom, dan knoop, dan rechtersubboom
3. CKnoop, dan linkersubboom, dan rechtersubboom
4. DRechtersubboom, dan knoop, dan linkersubboom

Wat is een deque (double-ended queue)?

1. ATwee aparte queues die één array delen
2. BEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
3. CEen queue die alleen verwijderen achteraan toestaat
4. DEen queue gesorteerd op prioriteit

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

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

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

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

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

1. AKwadratisch proberen (quadratic probing)
2. BSeparate chaining (ketenen)
3. CDubbel hashen (double hashing)
4. DLineair proberen (linear probing)

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A0,5
2. B1
3. C2
4. DEr is geen maximum

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

1. AElementen op elke positie invoegen
2. BDe mediaan vinden in O(1)
3. CPrefixsomquery's en updates van één element
4. DDe array sorteren en binair zoeken

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

1. ADe map geeft een fout op het moment dat het veld verandert
2. BDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
3. CEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
4. DHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat