Werkblad Datastructuren met antwoorden

Een graaf bestaat uit:

1. AKnopen (vertices) verbonden door kanten
2. BRijen en kolommen
3. CAlleen een wortel en bladeren
4. DAlleen sleutels en hashes

Wat doet een hashfunctie in een hashtabel?

1. ATelt hoeveel sleutels er zijn opgeslagen
2. BBeeldt een sleutel af op een index in de tabel
3. CSorteert de sleutels in de tabel
4. DVersleutelt de waarden in de tabel

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AData en een index
2. BData en een verwijzing naar de volgende knoop
3. CAlleen data
4. DData en verwijzingen naar alle andere knopen

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

1. AEen set zonder ordening
2. BEen FIFO-queue
3. CEen min-prioriteitswachtrij
4. DEen stack

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A1
2. B0,5
3. CEr is geen maximum
4. D2

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

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

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

1. AEen deque met indices in afnemende volgorde van waarde
2. BEen gesorteerde array die door verschuiven wordt bijgewerkt
3. CEen enkelvoudig gekoppelde lijst van de elementen in het venster
4. DEen min-heap die voor elk venster opnieuw wordt opgebouwd

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

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