Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

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

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet adres van de eerste knoop
2. BHet adres van de vorige knoop
3. CNull (geen knoop)
4. DHet aantal knopen in de lijst

Wat is een botsing (collision) in een hashtabel?

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

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AZe is altijd bovendriehoeks
2. BHaar hoofddiagonaal bevat altijd enen
3. CZe is symmetrisch ten opzichte van de hoofddiagonaal
4. DElke rij heeft precies één 1

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

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

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

De sleutels 5, 3, 8, 1 worden in deze volgorde in een lege, op een array gebaseerde binaire min-heap ingevoegd. Wat is de uiteindelijke array?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[3, 1, 8, 5]
4. D[1, 5, 8, 3]

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

1. AO(log n)
2. BO(1)
3. CO(n log n)
4. DO(n)