Werkblad Datastructuren met antwoorden

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

1. AZe slaat elementen gesorteerd op
2. BZe staat alleen toegang aan één uiteinde toe
3. CZe slaat elementen op zonder duplicaten
4. DZe slaat sleutel-waardeparen op

Wat is een botsing (collision) in een hashtabel?

1. ATwee gelijke sleutels worden twee keer opgeslagen
2. BEen sleutel kan helemaal niet worden gehasht
3. CDe tabel heeft geen geheugen meer
4. DTwee verschillende sleutels worden op dezelfde index afgebeeld

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

1. AEen statische array geeft tragere toegang via de index
2. BEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
3. CEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
4. DEen statische array kan alleen getallen opslaan

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

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

1. ALineair proberen (linear probing)
2. BDubbel hashen (double hashing)
3. CKwadratisch proberen (quadratic probing)
4. DSeparate chaining (ketenen)

Een trie (prefixboom) is bijzonder efficiënt voor:

1. AKortste paden vinden
2. BGetallen sorteren
3. CMatrices opslaan
4. DZoeken op prefix, zoals automatisch aanvullen

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

1. AO(n)
2. BO(m)
3. CO(1 + α), waarbij α = n / m
4. DO(log n)

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

1. AVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
2. BTel de knopen tot het aantal het lengteveld van de lijst overschrijdt
3. CSla elke bezochte knoop op in een hash-set
4. DSorteer de lijst en zoek naar duplicaten