Werkblad Datastructuren met antwoorden

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

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

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

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

In welke volgorde bezoekt een postorder-doorloop van een binaire boom de knopen?

1. AKnoop, dan linkersubboom, dan rechtersubboom
2. BRechtersubboom, dan knoop, dan linkersubboom
3. CLinkersubboom, dan rechtersubboom, dan knoop
4. DLinkersubboom, dan knoop, dan rechtersubboom

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

1. AAltijd zijn ouder
2. BAltijd zijn rechterkind
3. CDe meest linkse knoop van zijn rechtersubboom
4. DDe meest rechtse knoop van zijn linkersubboom

Hoe werkt extract-min in een binaire min-heap?

1. AVerwijder het laatste element van de array
2. BZoek in alle bladeren naar het nieuwe minimum
3. CVerwijder de wortel en schuif alle elementen één plaats naar links
4. DVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

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

Welk paar doorlopen bepaalt altijd een unieke binaire boom met verschillende sleutels?

1. AAlleen level-order
2. BPreorder en inorder
3. CPreorder en postorder
4. DAlleen preorder