Werkblad Datastructuren met antwoorden

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet adres van de eerste knoop
2. BNull (geen knoop)
3. CHet aantal knopen in de lijst
4. DHet adres van de vorige knoop

De diepte van een knoop in een boom is:

1. AHet aantal kinderen van die knoop
2. BHet aantal knopen in zijn subboom
3. CHet aantal kanten van de wortel tot die knoop
4. DHet aantal kanten van die knoop tot het diepste blad

Wat is de max-heap-eigenschap?

1. ADe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer
2. BDe sleutels zijn van links naar rechts gesorteerd
3. CAlle bladeren bevatten de maximale sleutel
4. DDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen

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/2 en i/2 + 1
3. C2i en 2i + 1
4. Di + 1 en i + 2

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

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

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

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

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

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

Aan welke regel moeten hash en gelijkheid voldoen om een hashtabel correct te laten werken?

1. AGelijke hashwaarden impliceren gelijke sleutels
2. BHashwaarden moeten priemgetallen zijn
3. CVerschillende sleutels moeten verschillende hashwaarden hebben
4. DGelijke sleutels moeten gelijke hashwaarden hebben