Werkblad Datastructuren met antwoorden

Een graaf bestaat uit:

1. AKnopen (vertices) verbonden door kanten
2. BAlleen sleutels en hashes
3. CRijen en kolommen
4. DAlleen een wortel en bladeren

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

1. AIn willekeurige volgorde
2. BKleiner dan de waarde van de knoop
3. CGroter dan de waarde van de knoop
4. DGelijk aan de waarde van de knoop

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. APush
2. BEnqueue
3. CDequeue
4. DInsert

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

1. AO(E)
2. BO(log V)
3. CO(V²)
4. DO(V + E)

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

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

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
2. BArrays gebruiken minder instructies om waarden te vergelijken
3. CGekoppelde lijsten slaan elementen altijd op schijf op
4. DArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten

Welke uitspraak over heapsort is juist?

1. AHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
2. BHet draait op elke invoer in O(n) tijd
3. CHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
4. DHet is stabiel en heeft O(n) extra geheugen nodig

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