Werkblad Datastructuren met antwoorden

Wat is een botsing (collision) in een hashtabel?

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

Wat is in een ongerichte graaf de graad van een knoop?

1. AHet aantal kanten dat ermee verbonden is
2. BHet aantal knopen in de graaf
3. CDe positie in de adjacency list
4. DDe lengte van het langste pad vanaf die knoop

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

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

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

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

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

1. A2i + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. Di + 1

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

1. AEen hashmap gecombineerd met een dubbel gekoppelde lijst
2. BAlleen een binaire zoekboom
3. CEén gesorteerde array
4. DAlleen een stack

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

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