Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

1. AHet totale aantal knopen in de boom, inclusief de wortel en elk blad
2. BHet aantal kinderen van de wortel
3. CHet aantal bladeren in de boom
4. DHet aantal kanten op het langste pad van de wortel naar een blad

Wat zijn broer- of zusknopen (siblings) in een boom?

1. AEen knoop en zijn ouder
2. BKnopen op dezelfde diepte in verschillende subbomen
3. CKnopen die dezelfde ouder hebben
4. DKnopen zonder kinderen

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

1. AEen ongeordende enkelvoudig gekoppelde lijst
2. BEen heap
3. CEen stack
4. DEen string

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AHeaps bevatten nooit meer dan 100 elementen
2. BHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
3. CArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
4. DAlle sleutels in een heap zijn gelijk

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

1. AEen gesorteerde array
2. BEen enkelvoudig gekoppelde lijst
3. CEen dubbel gekoppelde lijst
4. DEen dynamische array

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

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

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

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

Waarvoor wordt de union-findstructuur gebruikt in het algoritme van Kruskal voor de minimale opspannende boom?

1. AControleren of de twee eindpunten van een kant al verbonden zijn
2. BDe kanten op gewicht sorteren
3. CTijdens het zoeken de huidige afstand van elke knoop tot de bron opslaan
4. DDe beginknoop kiezen