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 zonder cykels
3. CEen graaf waarin elk paar verschillende knopen door een kant verbonden is
4. DEen graaf waarvan alle kanten een gewicht hebben

Welke datastructuur wordt gebruikt voor een level-order-doorloop van een boom?

1. AHashtabel
2. BPrioriteitswachtrij
3. CStack
4. DQueue

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. AHet aantal opgeslagen elementen gedeeld door het aantal buckets
2. BHet aantal botsingen tot nu toe
3. CHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
4. DDe tijd die nodig is om de tabel van schijf te laden

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

1. AIndex 3
2. BIndex 6
3. CIndex 4
4. DIndex 0

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

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

Wat is de looptijd van breadth-first search op een graaf met V knopen die als adjacency matrix is opgeslagen?

1. AO(E log V)
2. BO(V²)
3. CO(V)
4. DO(V + E)

Welke uitspraak over heapsort is juist?

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