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

Welke datastructuur is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

  1. AHash-set
  2. BStapel (stack)
  3. CWachtrij (queue)
  4. DGraaf
2.Makkelijk

Wat is een cykel in een graaf?

  1. AEen pad dat elke knoop bezoekt
  2. BEen kant met gewicht nul
  3. CEen knoop zonder kanten
  4. DEen pad dat begint en eindigt in dezelfde knoop
3.Makkelijk

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

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

Hoe wordt een nieuw element in een binaire heap ingevoegd?

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

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)
6.Gemiddeld

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

  1. AEén gesorteerde array van knopen
  2. BAdjacency list
  3. CEen binaire heap van kanten
  4. DAdjacency matrix
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. COm de array gesorteerd te houden
  4. DOmdat halveren bij de helft elementen zou kwijtraken
8.Moeilijk

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. BBloomfilters slaan de volledige elementen op, die na het hashen niet meer te vinden zijn
  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

Antwoordenblad

  1. 1. B · Stapel (stack)
  2. 2. D · Een pad dat begint en eindigt in dezelfde knoop
  3. 3. A · In de wortel
  4. 4. C · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  5. 5. C · O(log n)
  6. 6. B · Adjacency list
  7. 7. B · Om herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
  8. 8. D · Die bits kunnen ook bij andere elementen horen, wat fout-negatieven zou veroorzaken

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