Werkblad Datastructuren met antwoorden

Wat is de max-heap-eigenschap?

1. ADe sleutels zijn van links naar rechts gesorteerd
2. BDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
3. CAlle bladeren bevatten de maximale sleutel
4. DDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer

Hoe worden de elementen van een array in het geheugen opgeslagen?

1. AOp willekeurige plaatsen gekozen door een hash
2. BIn één aaneengesloten blok, na elkaar
3. CIn een boom van geheugenpagina's
4. DVerspreid, verbonden door pointers

Een graaf bestaat uit:

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

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

1. AEen stack
2. BEen ongesorteerde gekoppelde lijst
3. CEen gebalanceerde binaire zoekboom
4. DEen hashtabel

Hoe wordt een nieuw element in een binaire heap ingevoegd?

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

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

1. Ai/2 en i/2 + 1
2. Bi + 1 en i + 2
3. C2i en 2i + 1
4. D2i + 1 en 2i + 2

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 binaire zoekboom die voor elk element opnieuw wordt opgebouwd
2. BEen queue die elk paar elementen bevat
3. CEen stack die elementen bewaart die op hun antwoord wachten
4. DEen hashtabel van alle elementen

Waarom gebruiken databases voor indexen vaak B+-bomen in plaats van gewone B-bomen?

1. AB+-bomen hoeven niet gebalanceerd te zijn
2. BAlle records staan in gekoppelde bladeren, wat bereikscans efficiënt maakt
3. CB+-bomen slaan data alleen in de wortel op
4. DB+-bomen gebruiken binaire interne knopen, wat het aantal schijflezingen vermindert