Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AData en een index
2. BData en verwijzingen naar alle andere knopen
3. CAlleen data
4. DData en een verwijzing naar de volgende knoop

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

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

Wat is een botsing (collision) in een hashtabel?

1. ADe tabel heeft geen geheugen meer
2. BTwee verschillende sleutels worden op dezelfde index afgebeeld
3. CEen sleutel kan helemaal niet worden gehasht
4. DTwee gelijke sleutels worden twee keer opgeslagen

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AOplopend gesorteerde volgorde
2. BVolgorde per niveau
3. CAltijd aflopende volgorde
4. DInvoegvolgorde

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

1. AEen binaire heap van kanten
2. BAdjacency matrix
3. CEén gesorteerde array van knopen
4. DAdjacency list

De sleutels 50, 30, 70, 20, 40 worden in deze volgorde in een lege binaire zoekboom ingevoegd. Wat is het linkerkind van 30?

1. A70
2. B40
3. C20
4. D50

Een Bloom-filter kan de vraag "zit dit element in de verzameling?" beantwoorden met:

1. AAlleen antwoorden voor getallen
2. BMogelijke fout-positieven maar geen fout-negatieven
3. CMogelijke fout-negatieven maar geen fout-positieven
4. DAltijd exacte antwoorden

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

1. ADe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
2. BDe hele subboom te verwijderen
3. CHem te verwisselen met de wortel
4. DHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen