Werkblad Datastructuren met antwoorden

Wat bevat elke knoop in een dubbel gekoppelde lijst?

1. AData, een pointer naar de volgende knoop en een pointer naar de vorige knoop
2. BTwee kopieën van de data en één pointer
3. CData en twee pointers, één naar de volgende knoop en één naar de knoop daarna
4. DData en alleen een pointer naar de volgende knoop

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

1. ADe positie in de adjacency list
2. BHet aantal knopen in de graaf
3. CDe lengte van het langste pad vanaf die knoop
4. DHet aantal kanten dat ermee verbonden is

Welke datastructuur werkt volgens het principe "first in, first out" (FIFO)?

1. ABinaire boom
2. BStapel (stack)
3. CHeap
4. DWachtrij (queue)

AVL-bomen en rood-zwartbomen garanderen:

1. ADat geen enkele knoop twee kinderen heeft
2. BEen hoogte van O(log n) door herbalancering
3. CZoeken in constante tijd in elk geval
4. DDat sleutels in invoegvolgorde worden opgeslagen

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

1. AAdjacency matrix
2. BEén gesorteerde array van knopen
3. CAdjacency list
4. DEen binaire heap van kanten

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. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

1. AEen gesorteerde array van alle n waarden
2. BEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
3. CEen FIFO-queue van de laatste k waarden
4. DEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Welke eigenschap houdt elke B-boom perfect gebalanceerd?

1. AAlle bladeren liggen op dezelfde diepte
2. BElke knoop slaat één sleutel op
3. CDe sleutels worden alleen in de wortel opgeslagen
4. DElke knoop heeft precies twee kinderen