Werkblad Datastructuren met antwoorden

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

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

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

1. AZe slaat elementen gesorteerd op
2. BZe staat alleen toegang aan één uiteinde toe
3. CZe slaat elementen op zonder duplicaten
4. DZe slaat sleutel-waardeparen op

Wat slaat een map (dictionary) op?

1. AAlleen waarden in volgorde van invoegen
2. BParen van gelijke sleutels
3. CWaarden gesorteerd op grootte
4. DSleutel-waardeparen met unieke sleutels

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(1), omdat de index bekend is
2. BO(log n), vanwege binair zoeken
3. CO(n²), omdat elk element n keer verschuift
4. DO(n), omdat latere elementen moeten opschuiven

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

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

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

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

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

1. AEén gesorteerde array
2. BAlleen een stack
3. CAlleen een binaire zoekboom
4. DEen hashmap gecombineerd met een dubbel gekoppelde lijst

Je wilt voor elk element van een array het volgende grotere element rechts ervan vinden, in totaal O(n) tijd. Welke structuur helpt?

1. AEen binaire zoekboom die voor elk element opnieuw wordt opgebouwd
2. BEen queue die elk paar elementen bevat
3. CEen stack die elementen bewaart die op hun antwoord wachten
4. DEen hashtabel van alle elementen