Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

1. AHet totale aantal knopen in de boom, inclusief de wortel en elk blad
2. BHet aantal bladeren in de boom
3. CHet aantal kinderen van de wortel
4. DHet aantal kanten op het langste pad van de wortel naar een blad

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AInvoegen aan de kop
2. BHet eerste element lezen
3. CHet kopelement verwijderen
4. DHet element op index i benaderen

Wat is in een ongerichte graaf de graad van een knoop?

1. AHet aantal knopen in de graaf
2. BDe positie in de adjacency list
3. CHet aantal kanten dat ermee verbonden is
4. DDe lengte van het langste pad vanaf die knoop

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(log n), vanwege binair zoeken
2. BO(1), omdat de index bekend is
3. CO(n²), omdat elk element n keer verschuift
4. DO(n), omdat latere elementen moeten opschuiven

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

1. A1 2 3 4 5
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

1. AEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
2. BDe bestaande sleutels worden ter plaatse gesorteerd
3. CAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
4. DDe oudste sleutels worden verwijderd om ruimte te maken

In de BST met wortel 50, linkersubboom 30 (kinderen 20, 40) en rechtersubboom 70 (kinderen 60, 80) wordt de wortel verwijderd met behulp van de inorder-opvolger. Welke sleutel wordt de nieuwe wortel?

1. A80
2. B40
3. C70
4. D60

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

1. AO(n)
2. BO(log n)
3. CO(1 + α), waarbij α = n / m
4. DO(m)