Werkblad Datastructuren met antwoorden

Wat is een gerichte graaf?

1. AEen graaf zonder cykels
2. BEen graaf waarin elk paar verschillende knopen door een kant verbonden is
3. CEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
4. DEen graaf waarvan alle kanten een gewicht hebben

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

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

Wat definieert een binaire boom?

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

Welke datastructuur gebruikt diepte-eerst zoeken (DFS) in de iteratieve versie?

1. AAlleen een hashtabel
2. BEen stack
3. CEen queue
4. DEen heap

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AElke rij heeft precies één 1
2. BZe is altijd bovendriehoeks
3. CZe is symmetrisch ten opzichte van de hoofddiagonaal
4. DHaar hoofddiagonaal bevat altijd enen

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

1. A(i + 1) mod n
2. B2i + 1
3. Ci + 1
4. D(i − 1) mod n

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

1. AO(1) tijd en O(1) extra geheugen
2. BO(n log n) tijd en O(1) extra geheugen
3. CO(n) tijd en O(n) extra geheugen
4. DO(n) tijd en O(1) extra geheugen

Hoe lang duurt het zoeken naar een willekeurige sleutel in een binaire min-heap van n elementen?

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