Werkblad Datastructuren met antwoorden

Wat is de wortel van een boom?

1. ADe bovenste knoop zonder ouder
2. BDe knoop met de grootste waarde
3. CEen willekeurige knoop in het midden
4. DEen knoop zonder kinderen

Wat is in een ongerichte graaf de graad van een knoop?

1. AHet aantal knopen in de graaf
2. BDe lengte van het langste pad vanaf die knoop
3. CHet aantal kanten dat ermee verbonden is
4. DDe positie in de adjacency list

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

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

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

1. AIndex 4
2. BIndex 0
3. CIndex 6
4. DIndex 3

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

1. A(i − 1) mod n
2. B(i + 1) mod n
3. Ci + 1
4. D2i + 1

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

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

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

1. ADie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
2. BBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
3. CVerwijderen zou het percentage fout-positieven naar 100% verhogen
4. DBloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn

Waarom worden B-bomen gebruikt in databases en bestandssystemen?

1. AHun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
2. BZe hebben geen herbalancering nodig
3. CZe slaan data ongesorteerd op
4. DZe gebruiken minder geheugen dan welke array dan ook, dus de hele index past altijd in het werkgeheugen