Werkblad Datastructuren met antwoorden

Wat is een gerichte graaf?

1. AEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
2. BEen graaf waarin elk paar verschillende knopen door een kant verbonden is
3. CEen graaf waarvan alle kanten een gewicht hebben
4. DEen graaf zonder cykels

Waar vind je het kleinste element van een binaire min-heap?

1. AIn een willekeurig blad, dat moet worden gezocht
2. BIn de wortel
3. CIn het meest linkse blad
4. DOp de laatste positie in de array

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

1. AGroter dan de waarde van de knoop
2. BKleiner dan de waarde van de knoop
3. CGelijk aan de waarde van de knoop
4. DIn willekeurige volgorde

Hoe wordt een nieuw element in een binaire heap ingevoegd?

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

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

1. ADe oudste sleutels worden verwijderd om ruimte te maken
2. BAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
3. CDe bestaande sleutels worden ter plaatse gesorteerd
4. DEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(n²), omdat elk element n keer verschuift
2. BO(n), omdat latere elementen moeten opschuiven
3. CO(log n), vanwege binair zoeken
4. DO(1), omdat de index bekend is

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²)
3. CO(n)
4. DO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

1. AEen queue (of een willekeurige verzameling) van knopen met ingraad 0
2. BEen max-heap geordend op uitgraad
3. CEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
4. DEen stack van alle bezochte kanten