Werkblad Datastructuren met antwoorden

Gratis printbaar werkblad Datastructuren: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

  1. AEen statische array kan alleen getallen opslaan
  2. BEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  3. CEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
  4. DEen statische array geeft tragere toegang via de index
2.Makkelijk

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

  1. AEen string
  2. BEen ongeordende enkelvoudig gekoppelde lijst
  3. CEen heap
  4. DEen stack
3.Makkelijk

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AKnopen zonder kinderen
  2. BEen knoop en zijn ouder
  3. CKnopen op dezelfde diepte in verschillende subbomen
  4. DKnopen die dezelfde ouder hebben
4.Gemiddeld

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

  1. AO(1)
  2. BO(E)
  3. CO(V)
  4. DO(log V)
5.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. ABouw de hele heap opnieuw op
  2. BPlaats het in de wortel en laat het omlaag zakken (sift down)
  3. CPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  4. DVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
6.Gemiddeld

Hoe werkt extract-min in een binaire min-heap?

  1. AVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  2. BVerwijder de wortel en schuif alle elementen één plaats naar links
  3. CVerwijder het laatste element van de array
  4. DZoek in alle bladeren naar het nieuwe minimum
7.Moeilijk

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 de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
  2. BOm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  3. COmdat halveren bij de helft elementen zou kwijtraken
  4. DOm de array gesorteerd te houden
8.Moeilijk

Welk probleem van linear probing vermindert double hashing vooral?

  1. ADe noodzaak om sleutels in de tabel op te slaan
  2. BDe noodzaak van een hashfunctie
  3. CDe O(n)-kosten van het lezen van de waarde van een sleutel
  4. DPrimaire clustering, waarbij lange reeksen bezette plaatsen ontstaan

Antwoordenblad

  1. 1. B · Een dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  2. 2. C · Een heap
  3. 3. D · Knopen die dezelfde ouder hebben
  4. 4. A · O(1)
  5. 5. C · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  6. 6. A · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  7. 7. B · Om herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  8. 8. D · Primaire clustering, waarbij lange reeksen bezette plaatsen ontstaan

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.