Werkblad Datastructuren met antwoorden

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

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

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

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

Wat definieert een binaire boom?

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

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AInvoegvolgorde
2. BOplopend gesorteerde volgorde
3. CVolgorde per niveau
4. DAltijd aflopende volgorde

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

1. AO(n log n)
2. BO(n)
3. CO(1)
4. DO(log n)

Een AVL-knoop is ongebalanceerd omdat de rechtersubboom van zijn linkerkind te hoog werd (left-right-geval). Welke correctie wordt toegepast?

1. AEen rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
2. BEen enkele linksrotatie bij de knoop
3. CEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
4. DEen enkele rechtsrotatie bij de knoop

Welke uitspraak over heapsort is juist?

1. AHet draait op elke invoer in O(n) tijd
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
4. DHet is stabiel en heeft O(n) extra geheugen nodig