Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

1. AEen stack
2. BEen string
3. CEen ongeordende enkelvoudig gekoppelde lijst
4. DEen heap

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

1. AGelijk aan de waarde van de knoop
2. BKleiner dan de waarde van de knoop
3. CIn willekeurige volgorde
4. DGroter dan de waarde van de knoop

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

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

Wat is de waarde van de postfixexpressie 3 4 + 2 * ?

1. A14
2. B10
3. C11
4. D24

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

1. AO(n), waarbij n het aantal woorden is
2. BO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
3. CO(log n), waarbij n het aantal woorden is
4. DO(L × n)

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

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

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

1. AEen hashmap gecombineerd met een dubbel gekoppelde lijst
2. BEén gesorteerde array
3. CAlleen een stack
4. DAlleen een binaire zoekboom