Werkblad Datastructuren met antwoorden

Wat doet een hashfunctie in een hashtabel?

1. ASorteert de sleutels in de tabel
2. BBeeldt een sleutel af op een index in de tabel
3. CVersleutelt de waarden in de tabel
4. DTelt hoeveel sleutels er zijn opgeslagen

Wat is een deque (double-ended queue)?

1. AEen queue gesorteerd op prioriteit
2. BEen queue die alleen verwijderen achteraan toestaat
3. CTwee aparte queues die één array delen
4. DEen structuur die invoegen en verwijderen aan beide uiteinden toestaat

Een graaf bestaat uit:

1. AAlleen sleutels en hashes
2. BAlleen een wortel en bladeren
3. CKnopen (vertices) verbonden door kanten
4. DRijen en kolommen

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

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

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)

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log n)

Waarvoor wordt de union-findstructuur gebruikt in het algoritme van Kruskal voor de minimale opspannende boom?

1. ATijdens het zoeken de huidige afstand van elke knoop tot de bron opslaan
2. BControleren of de twee eindpunten van een kant al verbonden zijn
3. CDe beginknoop kiezen
4. DDe kanten op gewicht sorteren

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
2. BPrecies O(log n)
3. CO(n²)
4. DO(n)