Werkblad Datastructuren met antwoorden

Wat doet een hashfunctie in een hashtabel?

1. AVersleutelt de waarden in de tabel
2. BSorteert de sleutels in de tabel
3. CTelt hoeveel sleutels er zijn opgeslagen
4. DBeeldt een sleutel af op een index in de tabel

Wat slaat een map (dictionary) op?

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

Hoeveel kanten heeft een boom met n knopen?

1. A2n
2. Bn + 1
3. Cn
4. Dn − 1

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

Welke datastructuur wordt gebruikt om te controleren of de haakjes in "{[()]}" in balans zijn?

1. AEen hashtabel
2. BEen binaire zoekboom
3. CEen queue
4. DEen stack

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

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

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

1. AOm het vergroten van de tabel overbodig te maken
2. BOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt
3. COm de hashtabel gesorteerd te maken
4. DOm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

1. AEen deque met indices in afnemende volgorde van waarde
2. BEen min-heap die voor elk venster opnieuw wordt opgebouwd
3. CEen gesorteerde array die door verschuiven wordt bijgewerkt
4. DEen enkelvoudig gekoppelde lijst van de elementen in het venster