Werkblad Datastructuren met antwoorden

Wat is een gewogen graaf?

1. AEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
2. BEen graaf met meer kanten dan knopen
3. CEen graaf die op schijf is opgeslagen
4. DEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand

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

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

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

1. AZe slaat elementen gesorteerd op
2. BZe slaat sleutel-waardeparen op
3. CZe slaat elementen op zonder duplicaten
4. DZe staat alleen toegang aan één uiteinde toe

Een circulaire buffer (ring buffer) wordt vaak gebruikt om het volgende te implementeren:

1. AEen hashfunctie
2. BEen binaire zoekboom
3. CEen graafdoorloop
4. DEen wachtrij met vaste grootte

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2^h+1 − 1
2. Bh²
3. C2h + 1
4. D2^h

Hoe vind je de kleinste sleutel in een binaire zoekboom?

1. AVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is
2. BBezoek elk blad en vergelijk ze
3. CVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
4. DKijk alleen naar de wortel

De sleutels 5, 3, 8, 1 worden in deze volgorde in een lege, op een array gebaseerde binaire min-heap ingevoegd. Wat is de uiteindelijke array?

1. A[3, 1, 8, 5]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

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