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

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

1. AKleiner dan de waarde van de knoop
2. BGelijk aan de waarde van de knoop
3. CGroter dan de waarde van de knoop
4. DIn willekeurige volgorde

Wat doet de bewerking peek (of top) op een stack?

1. AVerwijdert alle elementen van de stack
2. BVerwijdert het bovenste element en geeft het terug
3. CGeeft het onderste element van de stack terug
4. DGeeft het bovenste element terug zonder het te verwijderen

Wat geldt voor de adjacency matrix van een ongerichte graaf?

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

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

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

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

1. AO(L × n)
2. BO(log n), waarbij n het aantal woorden is
3. CO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
4. DO(n), waarbij n het aantal woorden is

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
2. BHij sorteert de kinderen van elke knoop op frequentie
3. CHij bewaart alleen de eerste letter van elk woord
4. DHij voegt ketens van knopen met één kind samen tot één kant met een string als label

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