Werkblad Datastructuren met antwoorden

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

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

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

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

Wat is een cykel in een graaf?

1. AEen pad dat begint en eindigt in dezelfde knoop
2. BEen pad dat elke knoop bezoekt
3. CEen knoop zonder kanten
4. DEen kant met gewicht nul

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

1. A2i + 1 en 2i + 2
2. Bi + 1 en i + 2
3. C2i en 2i + 1
4. Di/2 en i/2 + 1

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

1. AKwadratisch proberen (quadratic probing)
2. BDubbel hashen (double hashing)
3. CSeparate chaining (ketenen)
4. DLineair proberen (linear probing)

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

1. AEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
2. BDe oudste sleutels worden verwijderd om ruimte te maken
3. CAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
4. DDe bestaande sleutels worden ter plaatse gesorteerd

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

1. ATel de knopen tot het aantal het lengteveld van de lijst overschrijdt
2. BSorteer de lijst en zoek naar duplicaten
3. CVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
4. DSla elke bezochte knoop op in een hash-set

Aan welke eigenschap moet een rood-zwartboom voldoen?

1. ARode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
2. BDe wortel moet rood zijn
3. CElke knoop moet rood zijn
4. DElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen