Werkblad Datastructuren met antwoorden

Wat definieert een binaire boom?

1. AElke knoop slaat een binair getal op
2. BDe boom heeft precies twee niveaus
3. CElke knoop heeft precies twee kinderen
4. DElke knoop heeft hoogstens twee kinderen

Wat is de wortel van een boom?

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

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

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

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

1. ALineair proberen (linear probing)
2. BSeparate chaining (ketenen)
3. CKwadratisch proberen (quadratic probing)
4. DDubbel hashen (double hashing)

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AElke rij heeft precies één 1
2. BZe is symmetrisch ten opzichte van de hoofddiagonaal
3. CHaar hoofddiagonaal bevat altijd enen
4. DZe is altijd bovendriehoeks

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

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

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

1. AO(n)
2. BO(m)
3. CO(1 + α), waarbij α = n / m
4. DO(log n)

Welk probleem van linear probing vermindert double hashing vooral?

1. ADe noodzaak van een hashfunctie
2. BDe noodzaak om sleutels in de tabel op te slaan
3. CDe O(n)-kosten van het lezen van de waarde van een sleutel
4. DPrimaire clustering, waarbij lange reeksen bezette plaatsen ontstaan