Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

1. AHet aantal kinderen van de wortel
2. BHet aantal bladeren in de boom
3. CHet aantal kanten op het langste pad van de wortel naar een blad
4. DHet totale aantal knopen in de boom, inclusief de wortel en elk blad

Wat definieert een binaire boom?

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

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

1. AEen ongeordende enkelvoudig gekoppelde lijst
2. BEen stack
3. CEen heap
4. DEen string

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

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

Hoe wordt een nieuw element in een binaire heap ingevoegd?

1. APlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
2. BVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
3. CBouw de hele heap opnieuw op
4. DPlaats het in de wortel en laat het omlaag zakken (sift down)

Hoe vind je de kleinste sleutel in een binaire zoekboom?

1. AKijk alleen naar de wortel
2. BVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
3. CBezoek elk blad en vergelijk ze
4. DVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is

Je wilt voor elk element van een array het volgende grotere element rechts ervan vinden, in totaal O(n) tijd. Welke structuur helpt?

1. AEen hashtabel van alle elementen
2. BEen stack die elementen bewaart die op hun antwoord wachten
3. CEen queue die elk paar elementen bevat
4. DEen binaire zoekboom die voor elk element opnieuw wordt opgebouwd

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. APrecies O(log n)
2. BO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
3. CO(n²)
4. DO(n)