Werkblad Datastructuren met antwoorden

Wat doet een hashfunctie in een hashtabel?

1. AVersleutelt de waarden in de tabel
2. BTelt hoeveel sleutels er zijn opgeslagen
3. CBeeldt een sleutel af op een index in de tabel
4. DSorteert de sleutels in de tabel

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

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

Wat is een deque (double-ended queue)?

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

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

1. ASeparate chaining (ketenen)
2. BDubbel hashen (double hashing)
3. CLineair proberen (linear probing)
4. DKwadratisch proberen (quadratic probing)

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

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

AVL-bomen en rood-zwartbomen garanderen:

1. AEen hoogte van O(log n) door herbalancering
2. BZoeken in constante tijd in elk geval
3. CDat geen enkele knoop twee kinderen heeft
4. DDat sleutels in invoegvolgorde worden opgeslagen

Waarom gebruiken databases voor indexen vaak B+-bomen in plaats van gewone B-bomen?

1. AB+-bomen hoeven niet gebalanceerd te zijn
2. BB+-bomen slaan data alleen in de wortel op
3. CB+-bomen gebruiken binaire interne knopen, wat het aantal schijflezingen vermindert
4. DAlle records staan in gekoppelde bladeren, wat bereikscans efficiënt maakt

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

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