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

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

  1. ADe lengte van een array met vaste grootte bepalen
  2. BHet 5e element benaderen
  3. CHet laatste element via de index lezen
  4. DInvoegen aan het begin
3.Makkelijk

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

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

Welke datastructuur gebruikt een draaiend programma om actieve functieaanroepen en hun lokale variabelen bij te houden?

  1. AEen hashtabel van functies
  2. BDe call stack
  3. CEen binaire zoekboom van frames
  4. DDe wachtrij van het heapgeheugen
5.Gemiddeld

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

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

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

  1. AEen ongesorteerde gekoppelde lijst
  2. BEen gebalanceerde binaire zoekboom
  3. CEen stack
  4. DEen hashtabel
7.Moeilijk

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

  1. ADie bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  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. DBits in een Bloomfilter kunnen na het aanmaken niet worden veranderd
8.Moeilijk

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

  1. AO(m)
  2. BO(n)
  3. CO(log n)
  4. DO(1 + α), waarbij α = n / m

Antwoordenblad

  1. 1. C · Het aantal kanten op het langste pad van de wortel naar een blad
  2. 2. D · Invoegen aan het begin
  3. 3. A · In de wortel
  4. 4. B · De call stack
  5. 5. C · O(n), omdat latere elementen moeten opschuiven
  6. 6. B · Een gebalanceerde binaire zoekboom
  7. 7. A · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken
  8. 8. D · O(1 + α), waarbij α = n / m

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