Werkblad Datastructuren met antwoorden

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

1. AStapel (stack)
2. BGekoppelde lijst
3. CHashtabel
4. DWachtrij (queue)

Hoeveel kanten heeft een boom met n knopen?

1. An
2. Bn − 1
3. Cn + 1
4. D2n

Wat is de max-heap-eigenschap?

1. ADe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
2. BAlle bladeren bevatten de maximale sleutel
3. CDe sleutels zijn van links naar rechts gesorteerd
4. DDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

1. ADubbel hashen (double hashing)
2. BLineair proberen (linear probing)
3. CSeparate chaining (ketenen)
4. DKwadratisch proberen (quadratic probing)

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AZe is altijd bovendriehoeks
2. BHaar hoofddiagonaal bevat altijd enen
3. CElke rij heeft precies één 1
4. DZe is symmetrisch ten opzichte van de hoofddiagonaal

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

1. AAdjacency matrix
2. BAdjacency list
3. CEén gesorteerde array van knopen
4. DEen binaire heap van kanten

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

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

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

1. AHij slaat sleutels ongeordend op
2. BHij gebruikt geen extra geheugen
3. CGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart
4. DVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers