Werkblad Datastructuren met antwoorden

Wat is de max-heap-eigenschap?

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

Wat is een gerichte graaf?

1. AEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
2. BEen graaf zonder cykels
3. CEen graaf waarin elk paar verschillende knopen door een kant verbonden is
4. DEen graaf waarvan alle kanten een gewicht hebben

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

1. AGroter dan de waarde van de knoop
2. BKleiner dan de waarde van de knoop
3. CGelijk aan de waarde van de knoop
4. DIn willekeurige volgorde

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

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

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

1. AEen binaire heap van kanten
2. BAdjacency matrix
3. CAdjacency list
4. DEén gesorteerde array van knopen

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
2. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
3. CGekoppelde lijsten slaan elementen altijd op schijf op
4. DArrays gebruiken minder instructies om waarden te vergelijken

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

1. ASla front en rear op in dezelfde variabele
2. BMaak de buffergrootte een macht van twee
3. CHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt
4. DMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is

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

1. AAlleen preorder
2. BPreorder en postorder
3. CPreorder en inorder
4. DAlleen level-order