Werkblad Datastructuren met antwoorden

Wat is een cykel in een graaf?

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

Een hashtabel slaat data op als:

1. AUitsluitend een gesorteerde lijst
2. BEen string met vaste lengte
3. CEen boom met geordende sleutels
4. DSleutel-waardeparen die via een hashfunctie worden gevonden

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

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

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D4 2 5 1 3

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

1. A1
2. Blog₂ n
3. C√n
4. Dn (hij wordt een gekoppelde lijst)

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

1. AO(V × E)
2. BO(V²)
3. CO(E²)
4. DO(V + E)

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

Waarom wordt verwijderen in een hashtabel met open adressering vaak gedaan met een "tombstone"-markering?

1. ATombstones versnellen het hashen
2. BHet maakt de tabel gesorteerd
3. CHet leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken
4. DVerwijderde sleutels moeten om veiligheidsredenen voor altijd bewaard blijven, dus plekken kunnen nooit hergebruikt worden