Werkblad Datastructuren met antwoorden

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. ADe tijd die nodig is om de tabel van schijf te laden
2. BHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
3. CHet aantal opgeslagen elementen gedeeld door het aantal buckets
4. DHet aantal botsingen tot nu toe

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

1. AInvoegen aan het begin
2. BHet 5e element benaderen
3. CDe lengte van een array met vaste grootte bepalen
4. DHet laatste element via de index lezen

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

1. AEen statische array kan alleen getallen opslaan
2. BEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
3. CEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
4. DEen statische array geeft tragere toegang via de index

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
2. BAlle sleutels in een heap zijn gelijk
3. CHeaps bevatten nooit meer dan 100 elementen
4. DHet is een complete binaire boom, dus posities volgen eenvoudige indexformules

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

1. A√n
2. B1
3. Clog₂ n
4. Dn (hij wordt een gekoppelde lijst)

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

1. AEen gesorteerde array
2. BEen dynamische array
3. CEen enkelvoudig gekoppelde lijst
4. DEen dubbel gekoppelde lijst

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

1. AHij slaat sleutels ongeordend op
2. BHij gebruikt geen extra geheugen
3. CGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart
4. DVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

1. AAlleen een stack
2. BAlleen een binaire zoekboom
3. CEen hashmap gecombineerd met een dubbel gekoppelde lijst
4. DEén gesorteerde array