Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AHet eerste element lezen
2. BHet element op index i benaderen
3. CInvoegen aan de kop
4. DHet kopelement verwijderen

Een graaf bestaat uit:

1. AAlleen sleutels en hashes
2. BKnopen (vertices) verbonden door kanten
3. CAlleen een wortel en bladeren
4. DRijen en kolommen

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

1. A(i − 1) mod n
2. B2i + 1
3. Ci + 1
4. D(i + 1) mod n

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

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

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

Wat is de looptijd van breadth-first search op een graaf met V knopen die als adjacency matrix is opgeslagen?

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

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

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