Werkblad Datastructuren met antwoorden

Wat is een botsing (collision) in een hashtabel?

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

Waar vind je het kleinste element van een binaire min-heap?

1. AOp de laatste positie in de array
2. BIn een willekeurig blad, dat moet worden gezocht
3. CIn het meest linkse blad
4. DIn de wortel

Hoe heet de stackbewerking die een element bovenaan toevoegt?

1. APop
2. BPeek
3. CPush
4. DEnqueue

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D4 2 5 1 3

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

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

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

1. AGetallen sorteren
2. BZoeken op prefix, zoals automatisch aanvullen
3. CKortste paden vinden
4. DMatrices opslaan

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij sorteert de kinderen van elke knoop op frequentie
2. BHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
3. CHij bewaart alleen de eerste letter van elk woord
4. DHij voegt ketens van knopen met één kind samen tot één kant met een string als label

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

1. AOmdat halveren bij de helft elementen zou kwijtraken
2. BOm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
3. COmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
4. DOm de array gesorteerd te houden