Werkblad Datastructuren met antwoorden

Wat bevat elke knoop in een dubbel gekoppelde lijst?

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

Wat is de max-heap-eigenschap?

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

Wat is een botsing (collision) in een hashtabel?

1. ADe tabel heeft geen geheugen meer
2. BEen sleutel kan helemaal niet worden gehasht
3. CTwee verschillende sleutels worden op dezelfde index afgebeeld
4. DTwee gelijke sleutels worden twee keer opgeslagen

Wat is het doel van een sentinelknoop (dummyknoop) in een gekoppelde lijst?

1. ADe code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
2. BHet aantal elementen opslaan
3. CDe lijst gesorteerd maken
4. DVoorkomen dat de lijst groeit voorbij een vast maximumaantal knopen

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

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

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

1. AEen queue (of een willekeurige verzameling) van knopen met ingraad 0
2. BEen max-heap geordend op uitgraad
3. CEen stack van alle bezochte kanten
4. DEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

1. AOmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
2. BOm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
3. COm de array gesorteerd te houden
4. DOmdat halveren bij de helft elementen zou kwijtraken