Werkblad Datastructuren met antwoorden

Een graaf bestaat uit:

1. ARijen en kolommen
2. BAlleen een wortel en bladeren
3. CKnopen (vertices) verbonden door kanten
4. DAlleen sleutels en hashes

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

1. AInvoegen aan het begin
2. BDe lengte van een array met vaste grootte bepalen
3. CHet 5e element benaderen
4. DHet laatste element via de index lezen

Wat is in een ongerichte graaf de graad van een knoop?

1. ADe positie in de adjacency list
2. BDe lengte van het langste pad vanaf die knoop
3. CHet aantal kanten dat ermee verbonden is
4. DHet aantal knopen in de graaf

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

1. ABeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
2. BDe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
3. CElke knoop is rood of zwart gekleurd
4. DAlle bladeren liggen op precies dezelfde diepte

AVL-bomen en rood-zwartbomen garanderen:

1. ADat geen enkele knoop twee kinderen heeft
2. BZoeken in constante tijd in elk geval
3. CDat sleutels in invoegvolgorde worden opgeslagen
4. DEen hoogte van O(log n) door herbalancering

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

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

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

1. AEen enkele linksrotatie bij de ongebalanceerde knoop
2. BHet opnieuw kleuren van de knoop en zijn kind
3. CEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
4. DEen enkele rechtsrotatie bij de ongebalanceerde knoop

Welke eigenschap houdt elke B-boom perfect gebalanceerd?

1. AElke knoop heeft precies twee kinderen
2. BAlle bladeren liggen op dezelfde diepte
3. CElke knoop slaat één sleutel op
4. DDe sleutels worden alleen in de wortel opgeslagen