Werkblad Datastructuren met antwoorden

Wat doet de bewerking peek (of top) op een stack?

1. AVerwijdert het bovenste element en geeft het terug
2. BVerwijdert alle elementen van de stack
3. CGeeft het bovenste element terug zonder het te verwijderen
4. DGeeft het onderste element van de stack terug

Hoe heet de stackbewerking die een element bovenaan toevoegt?

1. APush
2. BEnqueue
3. CPop
4. DPeek

Wat slaat een map (dictionary) op?

1. AParen van gelijke sleutels
2. BWaarden gesorteerd op grootte
3. CSleutel-waardeparen met unieke sleutels
4. DAlleen waarden in volgorde van invoegen

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

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

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)

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

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

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

1. ASla elke bezochte knoop op in een hash-set
2. BSorteer de lijst en zoek naar duplicaten
3. CVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
4. DTel de knopen tot het aantal het lengteveld van de lijst overschrijdt