Werkblad Datastructuren met antwoorden

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

1. AHet totale aantal kanten in de graaf
2. BHet kortste pad naar elke andere knoop
3. CEen rij van V Booleaanse waarden
4. DEen lijst van de buurknopen

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

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

In een binaire zoekboom zijn de waarden in de linkersubboom van een knoop:

1. AIn willekeurige volgorde
2. BGelijk aan de waarde van de knoop
3. CKleiner dan de waarde van de knoop
4. DGroter dan de waarde van de knoop

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

1. AAlle bladeren liggen op precies dezelfde diepte
2. BBeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
3. CElke knoop is rood of zwart gekleurd
4. DDe hoogten van de linker- en rechtersubboom verschillen hoogstens 1

Hoe werkt extract-min in een binaire min-heap?

1. AVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
2. BVerwijder de wortel en schuif alle elementen één plaats naar links
3. CVerwijder het laatste element van de array
4. DZoek in alle bladeren naar het nieuwe minimum

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

Waarom wordt verwijderen in een hashtabel met open adressering vaak gedaan met een "tombstone"-markering?

1. AHet leegmaken van de plek kan de probeerreeks voor andere sleutels onderbreken
2. BHet maakt de tabel gesorteerd
3. CTombstones versnellen het hashen
4. DVerwijderde sleutels moeten om veiligheidsredenen voor altijd bewaard blijven, dus plekken kunnen nooit hergebruikt worden

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(α(n))
2. BO(log n)
3. CO(1)
4. DO(n)