Werkblad Datastructuren met antwoorden

In een binaire zoekboom zijn de waarden in de linkersubboom van een knoop:

1. AKleiner dan de waarde van de knoop
2. BGroter dan de waarde van de knoop
3. CIn willekeurige volgorde
4. DGelijk aan de waarde van de knoop

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

1. AWachtrij (queue)
2. BHeap
3. CBinaire boom
4. DStapel (stack)

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. ADe tijd die nodig is om de tabel van schijf te laden
2. BHet aantal opgeslagen elementen gedeeld door het aantal buckets
3. CHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
4. DHet aantal botsingen tot nu toe

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AOplopend gesorteerde volgorde
2. BVolgorde per niveau
3. CInvoegvolgorde
4. DAltijd aflopende volgorde

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

1. A2i + 1 en 2i + 2
2. Bi + 1 en i + 2
3. C2i en 2i + 1
4. Di/2 en i/2 + 1

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

1. AEén gesorteerde array van knopen
2. BEen binaire heap van kanten
3. CAdjacency list
4. DAdjacency matrix

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

1. ADie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
2. BBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
3. CBloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
4. DVerwijderen zou het percentage fout-positieven naar 100% verhogen

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

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