Werkblad Datastructuren met antwoorden

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

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

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

1. AHet laatste element via de index lezen
2. BInvoegen aan het begin
3. CHet 5e element benaderen
4. DDe lengte van een array met vaste grootte bepalen

Wat is een cykel in een graaf?

1. AEen pad dat begint en eindigt in dezelfde knoop
2. BEen pad dat elke knoop bezoekt
3. CEen knoop zonder kanten
4. DEen kant met gewicht nul

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 gesorteerde array
2. BEen dubbel gekoppelde lijst
3. CEen dynamische array
4. DEen enkelvoudig gekoppelde lijst

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)

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

1. AEen hashtabel
2. BEen ongesorteerde gekoppelde lijst
3. CEen gebalanceerde binaire zoekboom
4. DEen stack

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

1. AHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
2. BDe hele subboom te verwijderen
3. CDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
4. DHem te verwisselen met de wortel

Welke uitspraak over heapsort is juist?

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