Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AData en een index
2. BData en een verwijzing naar de volgende knoop
3. CData en verwijzingen naar alle andere knopen
4. DAlleen data

Hoe worden de elementen van een array in het geheugen opgeslagen?

1. AVerspreid, verbonden door pointers
2. BIn één aaneengesloten blok, na elkaar
3. COp willekeurige plaatsen gekozen door een hash
4. DIn een boom van geheugenpagina's

Wat is de wortel van een boom?

1. AEen knoop zonder kinderen
2. BEen willekeurige knoop in het midden
3. CDe bovenste knoop zonder ouder
4. DDe knoop met de grootste waarde

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

1. AEen binaire heap van kanten
2. BAdjacency list
3. CAdjacency matrix
4. DEén gesorteerde array van knopen

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

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

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 dubbel gekoppelde lijst
2. BEen enkelvoudig gekoppelde lijst
3. CEen gesorteerde array
4. DEen dynamische array

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is hoogstens 2 log₂(n + 1)
2. BDe hoogte is hoogstens log₂ n + 1
3. CDe hoogte is hoogstens n / 2
4. DDe hoogte is precies log₂ n

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 draait op elke invoer in O(n) tijd
3. CHet is stabiel en heeft O(n) extra geheugen nodig
4. DHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel