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 een botsing (collision) in een hashtabel?

  1. AEen sleutel kan helemaal niet worden gehasht
  2. BDe tabel heeft geen geheugen meer
  3. CTwee gelijke sleutels worden twee keer opgeslagen
  4. DTwee verschillende sleutels worden op dezelfde index afgebeeld
2.Makkelijk

Wat definieert een binaire boom?

  1. AElke knoop slaat een binair getal op
  2. BElke knoop heeft precies twee kinderen
  3. CElke knoop heeft hoogstens twee kinderen
  4. DDe boom heeft precies twee niveaus
3.Makkelijk

Wat doet de bewerking peek (of top) op een stack?

  1. AVerwijdert alle elementen van de stack
  2. BGeeft het onderste element van de stack terug
  3. CGeeft het bovenste element terug zonder het te verwijderen
  4. DVerwijdert het bovenste element en geeft het terug
4.Gemiddeld

Een trie (prefixboom) is bijzonder efficiënt voor:

  1. AMatrices opslaan
  2. BGetallen sorteren
  3. CZoeken op prefix, zoals automatisch aanvullen
  4. DKortste paden vinden
5.Gemiddeld

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

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

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

  1. AAlle sleutels in een heap zijn gelijk
  2. BHeaps bevatten nooit meer dan 100 elementen
  3. CHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
  4. DArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
7.Moeilijk

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

  1. AOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt
  2. BOm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
  3. COm het vergroten van de tabel overbodig te maken
  4. DOm de hashtabel gesorteerd te maken
8.Moeilijk

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

  1. ADe mediaan vinden in O(1)
  2. BElementen op elke positie invoegen
  3. CPrefixsomquery's en updates van één element
  4. DDe array sorteren en binair zoeken

Antwoordenblad

  1. 1. D · Twee verschillende sleutels worden op dezelfde index afgebeeld
  2. 2. C · Elke knoop heeft hoogstens twee kinderen
  3. 3. C · Geeft het bovenste element terug zonder het te verwijderen
  4. 4. C · Zoeken op prefix, zoals automatisch aanvullen
  5. 5. B · Een min-prioriteitswachtrij
  6. 6. C · Het is een complete binaire boom, dus posities volgen eenvoudige indexformules
  7. 7. B · Om het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
  8. 8. C · Prefixsomquery's en updates van één element

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