Werkblad Datastructuren met antwoorden

Wat is een deque (double-ended queue)?

1. AEen queue die alleen verwijderen achteraan toestaat
2. BEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
3. CEen queue gesorteerd op prioriteit
4. DTwee aparte queues die één array delen

Wat definieert een binaire boom?

1. AElke knoop heeft precies twee kinderen
2. BElke knoop heeft hoogstens twee kinderen
3. CElke knoop slaat een binair getal op
4. DDe boom heeft precies twee niveaus

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

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

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AHeaps bevatten nooit meer dan 100 elementen
2. BArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
3. CHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
4. DAlle sleutels in een heap zijn gelijk

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AZe is altijd bovendriehoeks
2. BZe is symmetrisch ten opzichte van de hoofddiagonaal
3. CHaar hoofddiagonaal bevat altijd enen
4. DElke rij heeft precies één 1

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

1. Ai + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. D2i + 1

Waarom kun je elementen niet zomaar uit een standaard-Bloomfilter verwijderen door hun bits te wissen?

1. ABits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
2. BBloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
3. CVerwijderen zou het percentage fout-positieven naar 100% verhogen
4. DDie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken

Welke uitspraak over heapsort is juist?

1. AHet draait op elke invoer in O(n) tijd
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
4. DHet is stabiel en heeft O(n) extra geheugen nodig