Werkblad Datastructuren met antwoorden

Wat is een cykel in een graaf?

1. AEen pad dat begint en eindigt in dezelfde knoop
2. BEen pad dat elke knoop bezoekt
3. CEen knoop zonder kanten
4. DEen kant met gewicht nul

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AInvoegen aan de kop
2. BHet element op index i benaderen
3. CHet kopelement verwijderen
4. DHet eerste element lezen

Wat is een botsing (collision) in een hashtabel?

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

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
2. BHeaps bevatten nooit meer dan 100 elementen
3. CArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
4. DAlle sleutels in een heap zijn gelijk

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A0,5
2. B1
3. CEr is geen maximum
4. D2

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

1. AOp index 2i + 1
2. BOp index ⌊i / 2⌋ + 1
3. COp index i − 1
4. DOp index ⌊(i − 1) / 2⌋

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. AOm de array gesorteerd te houden
2. BOmdat halveren bij de helft elementen zou kwijtraken
3. COm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
4. DOmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven

Welk paar doorlopen bepaalt altijd een unieke binaire boom met verschillende sleutels?

1. AAlleen preorder
2. BPreorder en postorder
3. CAlleen level-order
4. DPreorder en inorder